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.
翻译:在此信中,我们考虑了多机器人高效搜索路径规划(MESPP)问题,在这个问题上,一组机器人被部署在一个以图表为代表的环境下,以在给定的期限内捕捉移动目标。我们证明这个问题是NP硬的,并展示了第一套混合内线编程(MILP)模型,以解决MESPP问题。我们的模型首先包括多个搜索器、任意抓取范围以及假底片。尽管MESPP的最新算法是以简单的路径查点为基础的,但采用MILP作为规划范式,能够利用现代解决问题者的强大技术,产生更好的计算性能,从而延长规划视野。这些模型的设计是为了计算离线的最佳解决方案,但可以很容易地适应分布在网上的方法。我们的模拟显示,与先前的状态相比,计算时间有可能减少98%。我们还表明,分布式方法几乎和集中在6%的环境下进行,在本信所研究的环境下进行搜索,其优势不大,需要大量时间的考虑。