Mutex reasoning in cooperative path finding modeled as propositional satisfiability
Mutex reasoning in cooperative path finding modeled as propositional satisfiability
复制标题
协作路径查找中的互斥推理被建模为命题可满足性
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Pavel Surynek
中科院分区：
文献类型：
--
作者：
Pavel Surynek
本文讨论了协作路径查找（CPF）问题，其任务是为一组代理中的代理找到路径。每个智能体都有一个起点和一个目标位置，它的任务是从给定的起点到达目标。当遵循路径时，智能体不得相互碰撞，并且必须避开障碍物。建议用一种所谓的互斥推理来增强CPF的命题编码。互斥推理试图排除不可达的情况，以减少搜索空间的大小。检查给定的一对位置是否可由给定的一对代理合作到达。如果不是，则禁止该对顶点中的代理的出现。进行的实验评估表明，互斥推理提高了现有的编码2至5倍，在解决运行时，搜索最大完工时间的最佳解决方案。
This paper addresses a problem of cooperative path finding (CPF) where the task is to find paths for agents of a group of agents. Each agent is given a starting and a goal position and its task is to reach the goal from the given start. When following the paths, agents must not collide with each other and must avoid obstacles. It is suggested to augment propositional encodings of CPF with a so called mutex reasoning. Mutex reasoning is trying to rule out unreachable situations to reduce the size of the search space. It is checked whether a given pair of locations is reachable by a given pair of agents cooperatively. If not occurrence of the pair of agents in the pair of vertices is forbidden. The performed experimental evaluation showed that mutex reasoning improves existent encodings by 2 to 5 times in terms of solving runtime when makespan optimal solutions are searched.