An Ant System Algorithm for the Neutralization Problem

Abstract

We consider a path planning problem wherein an agent needs to safely and swiftly navigate from a given source location to a destination through an arrangement of disk-shaped obstacles. The agent possesses a limited neutralization capability in the sense that. it can neutralize a certain number of obstacles enroute and pass through them safely upon neutralization. Optimal utilization of such a capability is called the neutralization problem. This problem is essentially a shortest path problem with resource constraints, which has been shown to be NP-Hard except for some trivial variants. In this study, we propose an ant system algorithm for the neutralization problem. In the proposed algorithm, the state transition rule makes use of certain problem-specific information to guide the ants. We show how the parameters of the algorithm can be fine-tuned for enhanced performance and we present limited computational experiments including a real-world naval minefield dataset. Our experiments suggest that the proposed algorithm finds high quality solutions in general with reasonable computational resources.