  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.
