More Like this

1. Average case constant factor time and distance optimal multi-robot path planning in well-connected environments

   https://doi.org/10.1007/s10514-019-09858-z  

   Yu, Jingjin (May 2019, Autonomous Robots)

   Fast algorithms for optimal multi-robot path planning are sought after in real-world applications. Known methods, however, generally do not simultaneously guar- antee good solution optimality and good (e.g., polynomial) running time. In this work, we develop a first low-polynomial running time algorithm, called SplitAndGroup (SaG), that solves the multi-robot path planning problem on grids and grid-like environments, and produces constant factor makespan optimal solutions on average over all problem in- stances. That is, SaG is an average case O(1)-approximation algorithm and computes solutions with sub-linear makespan. SaG is capable of handling cases when the density of robots is extremely high - in a graph-theoretic setting, the al- gorithm supports cases where all vertices of the underly- ing graph are occupied. SaG attains its desirable proper- ties through a careful combination of a novel divide-and- conquer technique, which we denote as global decoupling, and network flow based methods for routing the robots. Solutions from SaG, in a weaker sense, are also a constant factor approximation on total distance optimality. 

   more » « less
2. Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids

   https://doi.org/10.15607/RSS.2018.XIV.013  

   Yu, Jingjin (June 2018, 2018 Robotics: Science and Systems)

   Let G = (V, E) be an m_1 \times \ldots \times m_k grid for some arbitrary constant k. We establish that O(\sum_{i=1}^km_i) (makespan) time-optimal labeled (i.e., each robot has a specific goal) multi-robot path planning can be realized on G in O(|V|^2) running time, even when vertices of G are fully occupied by robots. When all dimensions are of equal sizes, the running time approaches O(|V|). Using this base line algorithm, which provides average case O(1)-approximate (i.e., constant-factor) time-optimal solutions, we further develop a first worst case O(1)-approximate algorithm that again runs in O(|V|^2) time for two and three dimensions. We note that the problem has a worst case running time lower bound of \Omega(|V|^2). 

   more » « less
3. SEAR: A Polynomial-Time Multi-Robot Path Planning Algorithm with Expected Constant-Factor Optimality Guarantee

   Han, Shuai D.; Rodriguez, Edgar J.; Yu, Jingjin (January 2018, 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems)

   We study the labeled multi-robot path planning problem in continuous 2D and 3D domains in the absence of obstacles where robots must not collide with each other. For an arbitrary number of robots in arbitrary initial and goal arrangements, we derive a polynomial time, complete algorithm that produces solutions with constant-factor optimality guarantees on both makespan and distance optimality, in expectation, under the assumption that the robot labels are uniformly randomly distributed. Our algorithm only requires a small constant-factor expansion of the initial and goal configuration footprints for solving the problem, i.e., the problem can be solved in a fairly small bounded region. Beside theoretical guarantees, we present a thorough computational evaluation of the proposed solution. In addition to the baseline implementation, adapting an effective (but non-polynomial time) routing subroutine, we also provide a highly efficient implementation that quickly computes near-optimal solutions. Hardware experiments on the microMVP platform composed of non-holonomic robots confirms the practical applicability of our algorithmic pipeline. 

   more » « less
4. Informative Path Planning Algorithm for the Exploration of Unknown 2D Environments

   https://doi.org/10.1109/UEMCON59035.2023.10316101  

   Macias, Geronimo; Lee, Kooktae (October 2023, IEEE)

   This paper addresses the Informative Path Planning (IPP) algorithm for autonomous robots to explore unknown 2D environments for mapping purposes. IPP can be beneficial to many applications such as search and rescue and cave exploration, where mapping an unknown environment is necessary. Autonomous robots' limited operation time due to their finite battery necessitates an efficient IPP algorithm, however, it is challenging because autonomous robots may not have any information about the environment. In this paper, we formulate a mathematical structure of the IPP problem along with the derivation of the optimal control input. Then, a discretized model for the IPP algorithm is presented as a solution for exploring an unknown environment. The proposed approach provides relatively fast computation time while being applicable to broad robot and sensor platforms. Various simulation results are provided to show the performance of the proposed IPP algorithm. 

   more » « less
5. Coordination-free Multi-robot Path Planning for Congestion Reduction Using Topological Reasoning

   https://doi.org/10.1007/s10846-023-01878-3  

   Wang, Xiaolong; Sahin, Alp; Bhattacharya, Subhrajit (July 2023, Journal of Intelligent & Robotic Systems)

   Abstract We consider the problem of multi-robot path planning in a complex, cluttered environment with the aim of reducing overall congestion in the environment, while avoiding any inter-robot communication or coordination. Such limitations may exist due to lack of communication or due to privacy restrictions (for example, autonomous vehicles may not want to share their locations or intents with other vehicles or even to a central server). The key insight that allows us to solve this problem is to stochastically distribute the robots across different routes in the environment by assigning them paths in different topologically distinct classes, so as to lower congestion and the overall travel time for all robots in the environment. We outline the computation of topologically distinct paths in a spatio-temporal configuration space and propose methods for the stochastic assignment of paths to the robots. A fast replanning algorithm and a potential field based controller allow robots to avoid collision with nearby agents while following the assigned path. Our simulation and experiment results show a significant advantage over shortest path following under such a coordination-free setup. 

   more » « less