Subdimensional Expansion for Multi-Objective Multi-Agent Path Finding
Subdimensional Expansion for Multi-Objective Multi-Agent Path Finding
复制标题
DOI：
10.1109/lra.2021.3096744
复制
发表时间：
2021-02
影响因子：
5.2
通讯作者：
Z. Ren;S. Rathinam;H. Choset
中科院分区：
文献类型：
--
作者：
Z. Ren;S. Rathinam;H. Choset
传统的多代理路径计划者通常确定一个优化单个目标的路径，例如路径长度。通常，这些标准可能不会直接比较，有时只是互相竞争。无效，因为可能的解决方案的大小，即帕累托最佳集合可以用代理的数量成倍增长。使用称为细节扩展的框架。我们结合了优势和细分扩展原则，以创建一种新算法，称为多目标M $^*$（MOM $^*$），该算法只有在这些代理必须相互“互动”时，动态地对计划进行了计划。 MOM $^*$计算有效的多个代理的帕累托最佳设置，并且自然而然地交易了帕累托（Pareto）最佳设置和计算效率的子最佳近似值。具有数百种解决方案的问题实例的帕累托最佳设置，标准多目标A $^*$算法在有限的时间内找不到。
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.