The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions
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. Al...
Main Author: | |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2021
|
Subjects: | |
Online Access: | http://arxiv.org/abs/2111.09093 |
id |
ftarxivpreprints:oai:arXiv.org:2111.09093 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:2111.09093 2023-09-05T13:23:43+02:00 The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions Alpern, Steve 2021-11-17 http://arxiv.org/abs/2111.09093 unknown http://arxiv.org/abs/2111.09093 Computer Science - Artificial Intelligence text 2021 ftarxivpreprints 2023-08-16T16:47:37Z 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. Comment: 16 figures Text The Pointers ArXiv.org (Cornell University Library) |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Computer Science - Artificial Intelligence |
spellingShingle |
Computer Science - Artificial Intelligence Alpern, Steve The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions |
topic_facet |
Computer Science - Artificial Intelligence |
description |
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. Comment: 16 figures |
format |
Text |
author |
Alpern, Steve |
author_facet |
Alpern, Steve |
author_sort |
Alpern, Steve |
title |
The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions |
title_short |
The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions |
title_full |
The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions |
title_fullStr |
The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions |
title_full_unstemmed |
The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions |
title_sort |
faulty gps problem: shortest time paths in networks with unreliable directions |
publishDate |
2021 |
url |
http://arxiv.org/abs/2111.09093 |
genre |
The Pointers |
genre_facet |
The Pointers |
op_relation |
http://arxiv.org/abs/2111.09093 |
_version_ |
1776204311264493568 |