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: | Article in Journal/Newspaper |
Language: | unknown |
Published: |
arXiv
2021
|
Subjects: | |
Online Access: | https://dx.doi.org/10.48550/arxiv.2111.09093 https://arxiv.org/abs/2111.09093 |
id |
ftdatacite:10.48550/arxiv.2111.09093 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.48550/arxiv.2111.09093 2023-05-15T18:32:44+02:00 The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions Alpern, Steve 2021 https://dx.doi.org/10.48550/arxiv.2111.09093 https://arxiv.org/abs/2111.09093 unknown arXiv Creative Commons Attribution 4.0 International https://creativecommons.org/licenses/by/4.0/legalcode cc-by-4.0 CC-BY Artificial Intelligence cs.AI FOS Computer and information sciences Article CreativeWork article Preprint 2021 ftdatacite https://doi.org/10.48550/arxiv.2111.09093 2022-03-10T13:30:59Z 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. : 16 figures Article in Journal/Newspaper The Pointers DataCite Metadata Store (German National Library of Science and Technology) |
institution |
Open Polar |
collection |
DataCite Metadata Store (German National Library of Science and Technology) |
op_collection_id |
ftdatacite |
language |
unknown |
topic |
Artificial Intelligence cs.AI FOS Computer and information sciences |
spellingShingle |
Artificial Intelligence cs.AI FOS Computer and information sciences Alpern, Steve The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions |
topic_facet |
Artificial Intelligence cs.AI FOS Computer and information sciences |
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. : 16 figures |
format |
Article in Journal/Newspaper |
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 |
publisher |
arXiv |
publishDate |
2021 |
url |
https://dx.doi.org/10.48550/arxiv.2111.09093 https://arxiv.org/abs/2111.09093 |
genre |
The Pointers |
genre_facet |
The Pointers |
op_rights |
Creative Commons Attribution 4.0 International https://creativecommons.org/licenses/by/4.0/legalcode cc-by-4.0 |
op_rightsnorm |
CC-BY |
op_doi |
https://doi.org/10.48550/arxiv.2111.09093 |
_version_ |
1766216910659125248 |