论文标题
用于多机器人非对抗性搜索的混合刻板线性编程模型
Mixed-Integer Linear Programming Models for Multi-Robot Non-Adversarial Search
论文作者
论文摘要
在这封信中，我们考虑了多机器人有效的搜索路径计划（MESPP）问题，其中将机器人团队部署在以图表为代表的环境中，以在给定的截止日期内捕获移动目标。我们证明了这个问题是NP-HARD，并提出了第一组混合组件线性编程（MILP）模型来解决MESPP问题。我们的模型是第一个同时包含多个搜索者，任意捕获范围和虚假负面因素的模型。尽管MESPP的最先进算法是基于简单的路径枚举，但采用MILP作为计划范式允许利用现代求解器的强大技术，从而产生更好的计算性能，并因此更长的计划范围。这些模型设计用于离线计算最佳解决方案，但可以轻松适应分布式在线方法。我们的模拟表明，相对于先前的最新时间，计算时间可以减少98％。我们还表明，在本信中研究的设置中，分布式方法的性能几乎和集中式的能力在6％之内，其优势是需要大量的时间 - 实践搜索任务的重要考虑因素。
In this letter, we consider the Multi-Robot Efficient Search Path Planning (MESPP) problem, where a team of robots is deployed in a graph-represented environment to capture a moving target within a given deadline. We prove this problem to be NP-hard, and present the first set of Mixed-Integer Linear Programming (MILP) models to tackle the MESPP problem. Our models are the first to encompass multiple searchers, arbitrary capture ranges, and false negatives simultaneously. While state-of-the-art algorithms for MESPP are based on simple path enumeration, the adoption of MILP as a planning paradigm allows to leverage the powerful techniques of modern solvers, yielding better computational performance and, as a consequence, longer planning horizons. The models are designed for computing optimal solutions offline, but can be easily adapted for a distributed online approach. Our simulations show that it is possible to achieve 98% decrease in computational time relative to the previous state-of-the-art. We also show that the distributed approach performs nearly as well as the centralized, within 6% in the settings studied in this letter, with the advantage of requiring significant less time - an important consideration in practical search missions.
