Subdimensional expansion for multirobot path planning

By Glenn Wagner, Howie Choset. Artificial Intelligence, 2015

389 citations recorded by the source corpus.

Abstract Planning optimal paths for large numbers of robots is computationally expensive. In this paper, we introduce a new framework for multirobot path planning called subdimensional expansion, which initially plans for each robot individually, and then coordinates motion among the robots as needed. More specifically, subdimensional expansion initially creates a one-dimensional search space embedded in the joint configuration space of the multirobot system. When the search space is found to be blocked during planning by a robot–robot collision, the dimensionality of the search space is locally increased to ensure that an alternative path can be found. As a result, robots are only coordinated when necessary, which reduces the computational cost of finding a path. We present the M ⁎ algorithm, an implementation of subdimensional expansion that adapts the A ⁎ planner to perform efficient multirobot planning. M ⁎ is proven to be complete and to find minimal cost paths. Simulation results are presented that show that M ⁎ outperforms existing optimal multirobot path planning algorithms.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Control and Systems Engineering

View Paper: https://www.semanticscholar.org/paper/1da1d0238aae185af623a06e52e2ff293a97dccb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Control and Systems Engineering

Citations in the corpus

PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning (2018, methodology): “Extending our previous work on distributed reinforcement learning (RL) for multiple agents in shared environments [11], [12], the main contribution of this paper introduces PRIMAL, a novel hybrid framework for decentralized MAPF that combines RL [13] and imitation learning (IL) from an expert centra”
Searching with Consistent Prioritization for Multi-Agent Path Finding (2018, methodology): “…(Surynek 2015; Yu and LaValle 2013a; Erdem et al. 2013) and dedicated MAPF algorithms (Standley and Korf 2011; Luna and Bekris 2011; Goldenberg et al. 2014; Sharon et al. 2013; Wagner and Choset 2015; Sharon et al. 2015), as described in several surveys (Ma et al. 2016a; Felner et al. 2017).”
A review of cooperative multi-agent deep reinforcement learning (2019, background): “Also, allowing on-demand growth in the search space during planning [219] is another approach.”