Potential Error in the Reuse of Nilsson's A Algorithm for Path-finding in Military Simulations

Abstract

We were recently asked to evaluate the Footprint-to-Pathfinder¹ path-finding implementation for possible reuse in OneSAF Objective System. The Footprint-to-Pathfinder path-finding code implements a variation of an algorithm described by Nils Nilsson called the A Algorithm. The A Algorithm can guarantee the optimal, lowest cost path between two points when it uses an “admissible” evaluation function. It is then called the A* (A-Star) Algorithm. The Footprint-to-Pathfinder implementation uses a simplification to the A Algorithm that preserves optimality when a particular condition exists. The condition that enables the simplification—the monotone restriction—is neither well known nor explained with most references for the A Algorithm. In fact, most references imply that an admissible evaluation function is sufficient. However, there are admissible evaluation functions that will cause the simplified implementation to return a path that is sub-optimal. OneSAF Objective System does not restrict admissible evaluation functions as Footprint-to-Pathfinder does. Thus the simplified algorithm is inappropriate for the OneSAF Objective System. Because the monotone restriction is not well publicized, this paper describes it in the context of path finding for combat simulations.