More Like this

1. Contingency Games for Multi-Agent Interaction

   https://doi.org/10.1109/LRA.2024.3354548  

   Peters, Lasse; Bajcsy, Andrea; Chiu, Chih-Yuan; Fridovich-Keil, David; Laine, Forrest; Ferranti, Laura; Alonso-Mora, Javier (March 2024, IEEE Robotics and Automation Letters)

   Contingency planning, wherein an agent generates a set of possible plans conditioned on the outcome of an uncertain event, is an increasingly popular way for robots to act under uncertainty. In this work we take a game-theoretic perspective on contingency planning, tailored to multi-agent scenarios in which a robot’s actions impact the decisions of other agents and vice versa. The resulting contingency game allows the robot to efficiently interact with other agents by generating strategic motion plans conditioned on multiple possible intents for other actors in the scene. Contingency games are parameterized via a scalar variable which represents a future time when intent uncertainty will be resolved. By estimating this parameter online, we construct a game-theoretic motion planner that adapts to changing beliefs while anticipating future certainty. We show that existing variants of game-theoretic planning under uncertainty are readily obtained as special cases of contingency games. Through a series of simulated autonomous driving scenarios, we demonstrate that contingency games close the gap between certainty-equivalent games that commit to a single hypothesis and non-contingent multi-hypothesis games that do not account for future uncertainty reduction. 

   more » « less
2. Energy-Efficient Motion Planning for Multi-Modal Hybrid Locomotion

   https://doi.org/10.1109/IROS45743.2020.9340761  

   Terry Suh, H. J.; Xiong, Xiaobin; Singletary, Andrew; Ames, Aaron D.; Burdick, Joel W. (October 2020, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS))

   null (Ed.)

   Hybrid locomotion, which combines multiple modalities of locomotion within a single robot, enables robots to carry out complex tasks in diverse environments. This paper presents a novel method for planning multi-modal locomotion trajectories using approximate dynamic programming. We formulate this problem as a shortest-path search through a state-space graph, where the edge cost is assigned as optimal transport cost along each segment. This cost is approximated from batches of offline trajectory optimizations, which allows the complex effects of vehicle under-actuation and dynamic constraints to be approximately captured in a tractable way. Our method is illustrated on a hybrid double-integrator, an amphibious robot, and a flying-driving drone, showing the practicality of the approach. 

   more » « less
3. Energy-Efficient Motion Planning for Multi-Modal Hybrid Locomotion

   Suh, H.J. Terry; Xiong, Xiaobin; Singletary, Andrew; Ames, Aaron D; Burdick, Joel W (October 2020, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS))

   Hybrid locomotion, which combines multiple modalities of locomotion within a single robot, enables robots to carry out complex tasks in diverse environments. This paper presents a novel method for planning multi-modal locomotion trajectories using approximate dynamic programming. We formulate this problem as a shortest-path search through a state-space graph, where the edge cost is assigned as optimal transport cost along each segment. This cost is approximated from batches of offline trajectory optimizations, which allows the complex effects of vehicle under-actuation and dynamic constraints to be approximately captured in a tractable way. Our method is illustrated on a hybrid double-integrator, an amphibious robot, and a flying-driving drone, showing the practicality of the approach. 

   more » « less
4. Informing Multi-Modal Planning with Synergistic Discrete Leads

   https://doi.org/10.1109/ICRA40945.2020.9197545  

   Kingston, Zachary; Wells, Andrew M.; Moll, Mark; Kavraki, Lydia E. (April 2020, 2020 IEEE International Conference on Robotics and Automation)

   Robotic manipulation problems are inherently continuous, but typically have underlying discrete structure, e.g., whether or not an object is grasped. This means many problems are multi-modal and in particular have a continuous infinity of modes. For example, in a pick-and-place manipulation domain, every grasp and placement of an object is a mode. Usually manipulation problems require the robot to transition into different modes, e.g., going from a mode with an object placed to another mode with the object grasped. To successfully find a manipulation plan, a planner must find a sequence of valid single-mode motions as well as valid transitions between these modes. Many manipulation planners have been proposed to solve tasks with multi-modal structure. However, these methods require mode-specific planners and fail to scale to very cluttered environments or to tasks that require long sequences of transitions. This paper presents a general layered planning approach to multi-modal planning that uses a discrete “lead” to bias search towards useful mode transitions. The difficulty of achieving specific mode transitions is captured online and used to bias search towards more promising sequences of modes. We demonstrate our planner on complex scenes and show that significant performance improvements are tied to both our discrete “lead” and our continuous representation. 

   more » « less
5. Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge

   Li, Jiaoyang; Chen, Zhe; Zheng, Yi; Chan, Shao-Hung; Harabor, Daniel; Stuckey, Peter J; Ma, Hang; Koenig, Sven (January 2021, Proceedings of the International Conference on Automated Planning and Scheduling)

   null (Ed.)

   Multi-Agent Path Finding (MAPF) is the combinatorial problem of finding collision-free paths for multiple agents on a graph. This paper describes MAPF-based software for solving train planning and replanning problems on large-scale rail networks under uncertainty. The software recently won the 2020 Flatland Challenge, a NeurIPS competition trying to determine how to efficiently manage dense traffic on rail networks. The software incorporates many state-of-the-art MAPF or, in general, optimization technologies, such as prioritized planning, large neighborhood search, safe interval path planning, minimum communication policies, parallel computing, and simulated annealing. It can plan collision-free paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution. 

   more » « less