Conflict-tolerant and conflict-free multi-agent meeting
Conflict-tolerant and conflict-free multi-agent meeting
复制标题
容忍冲突和无冲突的多主体会议
DOI：
10.1016/j.artint.2023.103950
复制
发表时间：
2023
影响因子：
14.4
通讯作者：
Koenig, Sven
中科院分区：
文献类型：
--
作者：
Atzmon, Dor;Felner, Ariel;Li, Jiaoyang;Shperberg, Shahaf;Sturtevant, Nathan;Koenig, Sven
在多代理会议问题（MAM）中，任务是为多个代理找到最佳会议位置，以及每个代理到该位置的路径。在所有可能的会议地点中，根据给定的成本函数，最优会议地点具有最小的成本。本研究考虑两个代价函数：(1)所有智能体路径到会议地点的代价之和（SOC）和(2)其中最长路径的代价（MKSP）。MAM在现实生活中有很多应用，比如为多个旅行代理（人、汽车或机器人）选择一个集合点。在本文中，我们将MAM分为两个变体。在其基本版本中，MAM允许多个代理占用同一位置，也就是说，它是冲突容忍的。对于MAM，我们引入了多方向启发式搜索算法MM*，该算法在不同的代价函数下寻找最优的会议地点。MM*将meetin Middle（MM）双向搜索算法推广到寻找多个座席的最优会议位置的情况。提出了几种适用于MM*的启发式方法，实验证明了MM*的优点。由于智能体可能存在于世界中，因此MAM的解决方案可能包含冲突路径，即多个智能体同时占据同一位置。MAM问题的第二个变体称为无冲突多代理会议（CF-MAM），其任务是为多个代理（如MAM）找到最佳会议位置，以及到该位置的无冲突路径（与著名的多代理寻路问题（MAPF）相同的方式）。为了最优求解CF-MAM，我们引入了两种结合MAM和MAPF求解器的新算法。我们证明了这两种算法的最优性，并对它们进行了实验比较，展示了每种算法的优缺点
In theMulti-Agent Meetingproblem (MAM), the task is to find the optimal meeting location for multiple agents, as well as a path for each agent to that location. Among all possible meeting locations, the optimal meeting location has the minimum cost according to a given cost function. Two cost functions are considered in this research: (1) the sum of all agents paths' costs to the meeting location (SOC) and (2) the cost of the longest path among them (MKSP). MAM has many real-life applications, such as choosing a gathering point for multiple traveling agents (humans, cars, or robots).In this paper, we divide MAM into two variants. In its basic version, MAM allows multiple agents to occupy the same location, i.e., it isconflict tolerant. For MAM, we introduce MM*, aMulti-Directional Heuristic Searchalgorithm, that finds the optimal meeting location under different cost functions. MM* generalizes theMeet in the Middle(MM) bidirectional search algorithm to the case of finding an optimal meeting location for multiple agents. Several admissible heuristics are proposed for MM*, and experiments demonstrate the benefits of MM*.As agents may be embodied in the world, a solution to MAM may contain conflicting paths, where more than one agent occupies the same location at the same time. The second variant of the MAM problem is calledConflict-Free Multi-Agent Meeting(CF-MAM), where the task is to find the optimal meeting location for multiple agents (as in MAM) as well as conflict-free paths (in the same manner as the prominentMulti-Agent Path Findingproblem (MAPF)) to that location. For optimally solving CF-MAM, we introduce two novel algorithms, which combine MAM and MAPF solvers. We prove the optimality of both algorithms and compare them experimentally, showing the pros and cons of each algorithm.1