Performance evaluation of an exact method for the obstacle neutralization problem

Abstract

The Obstacle Neutralization Problem (ONP) is an NP-Hard path planning problem wherein an agent needs to swiftly navigate from a given start location to a target location through an arrangement of disc-shaped obstacles on the plane. The agent has a limited neutralization capability in the sense that it can neutralize an obstacle after which it can safely traverse through. A neutralization can only be performed at a cost, which is added to the overall traversal length. The goal is to find the optimal neutralization sequence that minimizes the agent's total traversal length. In this study, we compare the performance of a recently proposed exact algorithm for ONP against a conventional solution obtained via an integer programming formulation. This exact algorithm consists of two phases. In Phase I, an effective and fast algorithm is used to obtain a suboptimal solution. In the Phase II, a k-th shortest path algorithm is used to close any gaps. The integer programming formulation is solved via the popular SCIP solver. We present computational experiments conducted on synthetic problem instances on a discrete plane with varying resolutions. Our results indicate that the exact algorithm provides an almost 10-fold improvement in execution time when compared against the integer programming approach.