More Like this

1. 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
2. Scalable distributed algorithms for multi-robot near-optimal motion planning

   https://doi.org/10.1109/CDC40024.2019.9029416  

   Zhao, Guoxiang; Zhu, Minghui (December 2019, 2019 IEEE 58th Conference on Decision and Control)

   This paper investigates a class of motion planning problems where multiple unicycle robots desire to safely reach their respective goal regions with minimal traveling times. We present a distributed algorithm which integrates decoupled optimal feedback planning and distributed conflict resolution. Collision avoidance and finite-time arrival at the goal regions are formally guaranteed. Further, the computational complexity of the proposed algorithm is independent of the robot number. A set of simulations are conduct to verify the scalability and near-optimality of the proposed algorithm. 

   more » « less
3. Adaptive Multiple Distributed Bidirectional Spiral Path Planning for Foraging Robot Swarms

   https://doi.org/10.1109/CRV60082.2023.00036  

   Lu, Qi; Luna, Ryan (June 2023, IEEE)

   The Distributed Deterministic Spiral Algorithm (DDSA) has shown great foraging efficiency in robot swarms. However, when the number of robots in the swarm increases, scalability becomes a significant bottleneck due to increased collisions among robots, making it challenging to deploy them in the search space (e.g., 20 robots). To address this issue, we propose an adaptive Multiple-Distributed Bidirectional Spiral Algorithm (MDBSA) that enhances scalability. Our proposed algorithm partitions the squared search arena into multiple identical squared regions and assigns robots to regions dynamically based on the number of regions. In each region, a bidirectional spiral search path is planned, and when a robot completes its search, it is assigned to either an unassigned region or a region with one robot. The two robots will then travel along the path from the starting and ending points of the spiral path. We evaluated the performance of robot swarms using the MDBSA algorithm in the ARGoS robot simulator. Our experimental results show that the proposed MDBSA algorithm outperforms DDSA. When robots deliver collected resources to regions instead of the center, it reduces collisions and significantly improves the scalability of the robot swarm. Our findings suggest that a multiple-distributed search strategy is an efficient solution for foraging robot swarms. 

   more » « less
4. 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
5. Decentralized Multi-Robot Information Gathering From Unknown Spatial Fields

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

   Newaz, Abdullah Al; Alsayegh, Murtadha; Alam, Tauhidul; Bobadilla, Leonardo (May 2023, IEEE Robotics and Automation Letters)

   We present an incremental scalable motion planning algorithm for finding maximally informative trajectories for decentralized mobile robots. These robots are deployed to observe an unknown spatial field, where the informativeness of observations is specified as a density function. Existing works that are typically restricted to discrete domains and synchronous planning often scale poorly depending on the size of the problem. Our goal is to design a distributed control law in continuous domains and an asynchronous communication strategy to guide a team of cooperative robots to visit the most informative locations within a limited mission duration. Our proposed Asynchronous Information Gathering with Bayesian Optimization (AsyncIGBO) algorithm extends ideas from asynchronous Bayesian Optimization (BO) to efficiently sample from a density function. It then combines them with decentralized reactive motion planning techniques to achieve efficient multi-robot information gathering activities. We provide a theoretical justification for our algorithm by deriving an asymptotic no-regret analysis with respect to a known spatial field. Our proposed algorithm is extensively validated through simulation and real-world experiment results with multiple robots. 

   more » « less