Multi-Agent Path Finding for Self Interested Agents
Multi-Agent Path Finding for Self Interested Agents
复制标题
自利代理的多代理路径查找
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Steven Okamoto
中科院分区：
文献类型：
--
作者：
Zahy Bnaya;Roni Stern;Ariel Felner;R. Zivan;Steven Okamoto
多智能体寻路(MAPF)处理单个智能体的路径规划，使得全局成本函数(例如，成本之和)最小化，同时避免智能体之间的冲突。以前的工作提出了集中式或完全协作的分散式算法，假设代理将遵循分配给它们的路径。然而，当代理商是{em自身利益}时，只有当他们认为这条路是他们最有益的选择时，他们才会遵循这条路。在本文中，我们提出使用一种税收方案来隐式协调MAPF中的自利主体。我们提出了几种征税方案，并对它们进行了实验比较。我们表明，即使我们同时考虑旅行成本和代理人支付的税款，智能税收方案也可以产生比非协调方案更低的总成本。
Multi-agent pathfinding (MAPF) deals with planning paths for individual agents such that a global cost function (e.g., the sum of costs) is minimized while avoiding collisions between agents. Previous work proposed centralized or fully cooperative decentralized algorithms assuming that agents will follow paths assigned to them. When agents are {em self-interested}, however, they are expected to follow a path only if they consider that path to be their most beneficial option. In this paper we propose the use of a taxation scheme to implicitly coordinate self-interested agents in MAPF. We propose several taxation schemes and compare them experimentally. We show that intelligent taxation schemes can result in a lower total cost than the non coordinated scheme even if we take into consideration both travel cost and the taxes paid by agents.