DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
AD1004206
Title:
An Innovative Multi-Agent Search-and-Rescue Path Planning Approach
Descriptive Note:
Technical Report
Corporate Author:
DRDC Valcartier Quebec City, Quebec Canada
Report Date:
2015-03-09
Pagination or Media Count:
10.0
Abstract:
Search and rescue path planning is known to be computationally hard, and most techniques developed to solve practical size problems have been unsuccessful to estimate an optimality gap. A mixed-integer linear programming MIP formulation is proposed to optimally solve the multi-agent discrete search and rescue SAR path planning problem, maximizing cumulative probability of success in detecting a target. It extends a single agent decision model to a multi-agent setting capturing anticipated feedback information resulting from possible observation outcomes during projected path execution while expanding possible agent actions to all possible neighboring move directions, considerably augmenting computational complexity. A network representation is further exploited to alleviate problem modeling, constraint specification, and speed-up computation. The proposed MIP approach uses CPLEX problem-solving technology in promptly providing near optimal solutions for realistic problems, while offering a robust upper bound derived from Lagrangean integrality constraint relaxation. Modeling extension to a closed-loop environment to incorporate real-time action outcomes over a receding time horizon can even be envisioned given acceptable run-time performance. A generalized parameter-driven objective function is then proposed and discussed to suitably define a variety of user-defined objectives. Computational results reporting the performance of the approach clearly show its value.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE
