Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective start locations to their respective goal locations while minimizing path costs.
Many MAPF studies rely on a common assumption of synchronized actions, where the actions of all agents start at the same time and always take a time unit, which may limit the applicability of MAPF planners in practice.
To bypass this assumption, various algorithms have been developed to handle asynchronous, non-unit-time actions, ranging from optimal to unbounded sub-optimal algorithms.
This paper focuses on bounded sub-optimal algorithms for MAPF with asynchronous actions (MAPF-AA) due to their ability to balance solution quality and runtime efficiency.
For MAPF, the recent bounded sub-optimal algorithms can intelligently distribute the sub-optimality bound among the agents based on agent-agent collision to achieve fast planning even with tight bounds.
We find that directly adapting these techniques to MAPF-AA can degrade their performance due to asynchronous actions.
This paper thus develops new techniques to consider asynchronous actions when distributing the sub-optimality bound among the agents and when selecting nodes for expansion during planning.
Results show that our approach achieves up to 60% higher success rates and reduces the number of expansions during planning by up to an order of magnitude compared to existing methods.
Xuemian Wu, Shizhe Zhao, Zhongqiang Ren· Proceedings of the Internati...· 0 citations
Motion planning in dynamic environments is a fundamental problem in robotics, aiming to generate safe and efficient paths, trajectories, or control actions in the presence of moving obstacles, uncertain predictions, and multi-agent interactions. It has broad applications in autonomous driving, service robotics, warehouse logistics, human-robot collaboration, crowd navigation, and multi-robot systems. This survey reviews representative works published primarily between 2015 and 2025, with a particular focus on how recent learning-based advances extend, complement, or interact with classical planning foundations. We first revisit classical planning methods as algorithmic foundations and reference frameworks for learning-based extensions. We then propose a role-of-learning taxonomy that categorizes existing methods according to how learning participates in the planning pipeline, including direct policy learning, learning-augmented classical planning, hybrid planning, and training enhancement methods. For each category, we summarize the main problem settings, representative algorithms, key ideas, integration mechanisms, strengths, and limitations. We further analyze how observation representations, prediction uncertainty, interaction modeling, planner integration, safety constraints, and training strategies shape learning-based motion planning in dynamic environments. Finally, we discuss open challenges and future directions, including sim-to-real gap, safe and certifiable planning, dense crowd navigation, perception-planning coupling, and embodied AI.
Zongyuan Shen, Shalabh Gupta, Shancheng Zhao et al.· 0 citations