Article Preview
TopIntroduction
The problem of navigating an agent with disambiguation capability to safely and swiftly traverse a potentially hazardous area is currently receiving considerable attention due to its application to minefield. The operational concepts of minefield reconnaissance via an airborne payload and minefield path planning given the detection data were first introduced in Witherspoon et al. (1995). Most of the early research efforts were put on the mine detection part. A thorough discussion of the mine detection can be found in Holmes et al. (1995). As the output of the mine detection, the detection map consists of a collection of objects with each marked with the estimate of probability of being a true hazard.
The focus of our work presented in this paper is the navigation part. That is to navigate the agent given the detection map a priori. In this problem, it is assumed that in proximity to any of the potential hazards the agent is able to disambiguate, at a cost, its true-false status. Since the agent can disambiguate, the safety is not a concern. Therefore, the navigation objective is to minimize total traversal cost, which consists of the traveling cost and the disambiguation cost.
Due to the randomness sources like the locations, the true-false status, and the detection markers, the agent’s traversal is also random. If a disambiguation is performed, the traversal is named random disambiguation walk (RDW), which is a very novel object that appears in very recent probabilistic path planning literature.
The object random disambiguation walk first appeared in Priebe et al. (2005). However, in this original study, the object was named as random disambiguation path (RDP). We rename the object as random disambiguation walk because the agent may revisit a location. If the world is a (directed) graph so that the agent only travels along the arcs, then the agent may pass some node or arc more than once. In this discrete case, the agent’s final trajectory is precisely a walk, which is defined in the most popular graph theory books (e.g., West, 2000).
Despite the name of the object, an important analytical result in Priebe et al. (2005) is that there exists a positive probability that there will be a RDW that strictly reduces the expected traversal cost compared with any deterministic shortest path that circumvents any risk. This result suggests that any relevant navigation algorithm should be able to exploit the potential benefit of disambiguation(s). Both the work in Priebe et al. (2005) and the follow-up by Fishkind et al. (2007) explored the navigation methods that yield a disambiguation-included traversal with small expected cost. However, a naïve assumption in both works is that any marker is the probability that the associated detection is a true hazard. The reason for this assumption is that both aimed to formulate the problem as a minor modification of the Stochastic Obstacle Scene Problem (SOSP) of Papadimitriou and Yannakakis (1991) since SOSP had been studied. A discrete version of SOSP is well known as the Canadian Traveler Problem (CTP). In CTP, the goal is to minimize the expected cost of traveling from a starting node to a destination node in a finite directed graph in which arcs are marked with their respective probabilities of being traversable or nontraversable, and each arc’s actual nature can be discovered only when encountered. Also, finding the nature of an arc leads to a cost, which has the same meaning as what we mentioned as disambiguation cost.
CTP is also a special case of the Stochstic Shortest Paths with Recourse (SPR) problem of Andreatta and Romeo (1988), who presented a stochastic dynamic programming formulation for SPR and noted its intractability. Another stochastic dynamic programming formulation for SPR was presented in Polychronopoulos and Tsitsiklis (1996), in which several variants were shown to be intractable. In Provan (2003), the SPR problem was proven to be intractable even if the underlying graph is directed and acyclic.