Journal
IEEE ROBOTICS AND AUTOMATION LETTERS
Volume 6, Issue 4, Pages 7153-7160Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/LRA.2021.3096744
Keywords
Motion and path planning; multi-robot systems; path planning for multiple mobile robots or agents
Categories
Ask authors/readers for more resources
This letter presents an approach to avoid the "curse of dimensionality" by leveraging prior multi-agent work and a framework called subdimensional expansion, resulting in a new algorithm called multi-objective M*(MOM*). MOM* efficiently computes the complete Pareto-optimal set for multiple agents, naturally trading off sub-optimal approximations of the Pareto-optimal set and computational efficiency.
Conventional multi-agent path planners typically determine a path that optimizes a single objective, such as path length. Many applications, however, may require multiple objectives, say time-to-completion and fuel use, to be simultaneously optimized in the planning process. Often, these criteria may not be directly compared and sometimes lie in competition with each other. Simply applying standard multi-objective search algorithms to multi-agent path finding may prove to be inefficient because the size of the space of possible solutions, i.e., the Pareto-optimal set, can grow exponentially with the number of agents. This letter presents an approach that bypasses this so-called curse of dimensionality by leveraging our prior multi-agent work with a framework called subdimensional expansion. One example of subdimensional expansion, when applied to A*, is called M* and M* was limited to a single objective function. We combine principles of dominance and subdimensional expansion to create a new algorithm, named multi-objective M*(MOM*), which dynamically couples agents for planning only when those agents have to interact with each other. MOM* computes the complete Pareto-optimal set for multiple agents efficiently and naturally trades off sub-optimal approximations of the Pareto-optimal set and computational efficiency. Our approach is able to find the complete Pareto-optimal set for problem instances with hundreds of solutions which the standard multi-objective A* algorithms could not find within a bounded time.
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