Static Target Search Path Planning Optimization with Heterogeneous Agents


  1. Berger, J.
  2. Lo, N.
  3. Barkaoui, M.
Corporate Authors
Defence Research and Development Canada, Valcartier Research Centre, Quebec QC (CAN);T-OptLogic Ltd, Quebec City QC (CAN)
As discrete multi-agent static open-loop target search path planning known to be computationally hard recently proved to be solvable in practice in the homogeneous case, its heterogeneous problem counterpart still remains very difficult. The heterogeneous problem introduces broken symmetry reflected by dissimilar sensing ability/capacity, agent capability and relative velocity and, is further exacerbated when operating under near real-time problem-solving constraints, as key decision variables grow exponentially in the number of agents. Departing from the homogeneous agent model already published, new integer linear and quadratic programming formulations are proposed to reduce computational complexity and near-optimally solve the discrete static search path planning problem involving heterogeneous agents. The novelty consists in taking advantage of typical optimal path solution property to derive new tractable problem models. At the expense of a slightly accrued computational complexity, the proposed quadratic integer program formulation conveys considerable benefit by keeping key decision variables linear in the number of agents. The convexity property of its defined objective function further allows ensuring global optimality when a local optimum is computed. Special agent network representations capturing individual agent decision moves are also devised to simplify problem modeling and expedite constraint modeling specification. As a result, costeffective quadratic program
search path planning;search and rescue;quadratic programmimng;linear programming;heterogeneous agents
Report Number
DRDC-RDDC-2015-P187 — External Literature
Date of publication
22 Feb 2016
Number of Pages
Electronic Document(PDF)

Permanent link

Document 1 of 1

Date modified: