Published January 1, 2017
| Version v1
Journal article
Open
AN OPTIMAL ALGORITHM FOR THE OBSTACLE NEUTRALIZATION PROBLEM
Creators
- 1. Marmara Univ, Comp Engn Dept, TR-34722 Istanbul, Turkey
- 2. Yasar Univ, Software Engn Dept, TR-35100 Izmir, Turkey
Description
In this study, an optimal algorithm is presented for the obstacle neutralization problem (ONP). ONP is a recently introduced path planning problem wherein an agent needs to swiftly navigate from a source to a destination through an arrangement of obstacles in the plane. The agent has a limited neutralization capability in the sense that the agent can safely pass through an obstacle upon neutralization at a cost added to the traversal length. The goal of an agent is to find the sequence of obstacles to be neutralized en route minimizing the overall traversal length subject to the neutralization limit. Our optimal algorithm consists of two phases. In the first phase an upper bound of the problem is obtained using a suboptimal algorithm. In the second phase, starting from the bound obtained from phase I, a k-th shortest path algorithm is exploited to find the optimal solution. The performance of the algorithm is presented with computational experiments conducted both on real and synthetic naval minefield data. Results are promising in the sense that the proposed method can be applied in online applications.
Files
bib-0950735f-8e76-4923-8f8e-bc984e3762f7.txt
Files
(156 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:1f9062d39613f0824d0271822deb4d5e
|
156 Bytes | Preview Download |