An Information-theoretic –based Integer Linear Programming Approach for the Discrete Search Path Planning Problem


  1. Berger, J.
  2. Lo, N.
  3. Boukhtouta, A.
  4. Noel, M.
Corporate Authors
Defence Research and Development Canada, Valcartier Research Centre, Quebec QC (CAN);T-OptLogic Ltd, Quebec City QC (CAN)
Discrete search path planning is known to be a NP-Hard problem, and problem-solving methods proposed so far rely on heuristics with no way to reasonably estimate solution quality for practical size problems. Departing from traditional nonlinear model formulations, a novel information-theoretic –based approach using integer linear programming (ILP) is proposed to optimally solve the discrete open-loop centralized search path planning problem with anticipated feedback, involving a team of homogeneous agents. The approach takes advantage of objective function separability and conditional probability independence of observations to efficiently minimize expected system entropy. A network representation is exploited to simplify modeling, reduce constraint specification and speed-up problem-solving. The novelty of the approach consists in capturing false-alarm observations explicitly while proposing an original and efficient way to linearize the underlying non-linear expected entropy function required to properly represent target location uncertainty, making for the first time practical problems tractable. The proposed ILP formulation rapidly yields near-optimal solutions for realistic problems while providing for the first time, a robust lower bound through Lagrangian relaxation. Long planning problem horizon may be dynamically adapted by periodically solving new problem instances incorporating actual observation outcomes from previous episodes over receding horizons. Computation
combinatorial optimization;search path planning;information theory;network flow;linear programming;open-loop with anticipated feedback
Report Number
DRDC-RDDC-2015-P105 — External Literature
Date of publication
01 Oct 2015
Number of Pages
Electronic Document(PDF)

Permanent link

Document 1 of 1

Date modified: