Static target search path planning optimization with heterogeneous agents

Jean Berger (), Nassirou Lo () and Mohamed Barkaoui ()
Additional contact information
Jean Berger: DRDC Valcartier
Nassirou Lo: T-OptLogic Ltd.
Mohamed Barkaoui: Carthage University

Annals of Operations Research, 2016, vol. 244, issue 2, No 2, 295-312

Abstract: Abstract 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, cost-effective quadratic program implementation for realistic problems may be achieved to rapidly compute near-optimal solutions, while providing a robust bound on solution quality through Lagrangian relaxation.

Keywords: Search path planning; Search and rescue; Quadratic programmimng; Linear programming; Heterogeneous agents (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-016-2145-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:244:y:2016:i:2:d:10.1007_s10479-016-2145-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-016-2145-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().