Journal
IEEE ROBOTICS AND AUTOMATION LETTERS
Volume 8, Issue 8, Pages 4545-4552Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/LRA.2023.3286815
Keywords
Path planning for multiple mobile robots or agents; task and motion planning; shortest path bounds
Categories
Ask authors/readers for more resources
This letter investigates the minimization of the longest travel distance for a group of mobile robots with interchangeable goals through polynomial-time approximations of the shortest path search. The proposed algorithm iteratively increases the accuracy of the path planning and provides a certificate for the optimality of the goal assignment. Feasible paths and expanded sample sets are used to determine upper and lower bounds on the shortest paths, respectively, using sampling-based path planning. A case study on multi-robot path planning is presented to demonstrate the application of the proposed method.
Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment with obstacles is NP-hard however. In this letter, we investigate when polynomial-time approximations of the shortest path search are sufficient to determine the optimal assignment of robots to goals. In particular, we propose an algorithm in which the accuracy of the path planning is iteratively increased. The approach provides a certificate when the uncertainties on estimates of the shortest paths become small enough to guarantee the optimality of the goal assignment. To this end, we apply results from assignment sensitivity assuming upper and lower bounds on the length of the shortest paths. We then provide polynomial-time methods to find such bounds by applying sampling-based path planning. The upper bounds are given by feasible paths, the lower bounds are obtained by expanding the sample set and leveraging the knowledge of the sample dispersion. We demonstrate the application of the proposed method with a multi-robot path-planning case study.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available