A penalty search algorithm for the obstacle neutralization problem

Fuat Alkaya, A, Aksakalli, V and Priebe, C 2015, 'A penalty search algorithm for the obstacle neutralization problem', Computers and Operations Research, vol. 53, pp. 165-175.

Document type: Journal Article
Collection: Journal Articles

Title A penalty search algorithm for the obstacle neutralization problem
Author(s) Fuat Alkaya, A
Aksakalli, V
Priebe, C
Year 2015
Journal name Computers and Operations Research
Volume number 53
Start page 165
End page 175
Total pages 11
Publisher Pergamon Press
Abstract We consider a path planning problem wherein an agent needs to swiftly navigate from a source to a destination through an arrangement of obstacles in the plane. We suppose the agent has a limited neutralization capability in the sense that it can safely pass through an obstacle upon neutralization at a cost added to the traversal length. The agent's goal is to find the sequence of obstacles to be neutralized en route that minimizes the overall traversal length subject to the neutralization limit. We call this problem the obstacle neutralization problem (ONP), which is essentially a variant of the intractable weight-constrained shortest path problem in the literature. In this study, we propose a simple, yet efficient and effective suboptimal algorithm for ONP based on the idea of penalty search and we present special cases where our algorithm is provably optimal. Computational experiments involving both real and synthetic naval minefield data are also presented.
Subject Optimisation
Keyword(s) Combinatorial optimization
Path planning
Weight-constrained shortest path
Suboptimal algorithm
DOI - identifier 10.1016/j.cor.2014.08.013
Copyright notice © 2014 Elsevier Ltd.
ISSN 0305-0548
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Altmetric details:
Access Statistics: 118 Abstract Views  -  Detailed Statistics
Created: Thu, 23 Jun 2016, 10:28:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us