论文标题
多代理路径的启发式指导汇编
Heuristically Guided Compilation for Multi-Agent Path Finding
论文作者
论文摘要
多代理路径查找（MAPF）是找到连接代理在共享环境中指定的初始和目标位置的非冲突路径的任务。我们专注于基于汇编的求解器，其中MAPF问题以不同的形式主义（例如混合成员线性编程（MILP），布尔满意度（SAT）或约束编程（CP）表示。作为这些形式主义的目标求解器充当黑盒，在基于MAPF编译的求解器中将MAPF特定的启发式方法整合在一起是具有挑战性的。我们在这项工作中展示了如何为目标SAT求解器编码的MAPF，其中反映了特定域的启发式知识。启发式知识通过为每个代理选择候选路径并仅构造这些候选路径的编码，而不是为代理的所有可能路径构造编码，从而将启发式知识转移到SAT求解器中。进行的实验表明，启发式指导的汇编的表现优于基于SAT的MAPF求解器的香草变体。
Multi-agent path finding (MAPF) is a task of finding non-conflicting paths connecting agents' specified initial and goal positions in a shared environment. We focus on compilation-based solvers in which the MAPF problem is expressed in a different well established formalism such as mixed-integer linear programming (MILP), Boolean satisfiability (SAT), or constraint programming (CP). As the target solvers for these formalisms act as black-boxes it is challenging to integrate MAPF specific heuristics in the MAPF compilation-based solvers. We show in this work how the build a MAPF encoding for the target SAT solver in which domain specific heuristic knowledge is reflected. The heuristic knowledge is transferred to the SAT solver by selecting candidate paths for each agent and by constructing the encoding only for these candidate paths instead of constructing the encoding for all possible paths for an agent. The conducted experiments show that heuristically guided compilation outperforms the vanilla variants of the SAT-based MAPF solver.
