The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions
This addresses motion planning under uncertainty for applications like autonomous vehicles or UAVs, building incrementally on prior work in ant navigation and AI trust.
The paper tackles the problem of optimizing motion planning when a GPS-like system suggests directions with a known probability of being correct, aiming to minimize expected travel time to a destination. It introduces the Faulty GPS Problem, analyzing optimal trust probabilities and extending to scenarios with node-dependent trust and competitive search.
This paper optimizes motion planning when there is a known risk that the road choice suggested by a Satnav (GPS) is not on a shortest path. At every branch node of a network Q, a Satnav (GPS) points to the arc leading to the destination, or home node, H - but only with a high known probability p. Always trusting the Satnav's suggestion may lead to an infinite cycle. If one wishes to reach H in least expected time, with what probability q=q(Q,p) should one trust the pointer (if not, one chooses randomly among the other arcs)? We call this the Faulty Satnav (GPS) Problem. We also consider versions where the trust probability q can depend on the degree of the current node and a `treasure hunt' where two searchers try to reach H first. The agent searching for H need not be a car, that is just a familiar example -- it could equally be a UAV receiving unreliable GPS information. This problem has its origin not in driver frustration but in the work of Fonio et al (2017) on ant navigation, where the pointers correspond to pheromone markers pointing to the nest. Neither the driver or ant will know the exact process by which a choice (arc) is suggested, which puts the problem into the domain of how much to trust an option suggested by AI.