EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Decentralized, Distributed, and Resilient Pathfinding for Dynamic, GPS-Denied Environments Using Visual Common Landmarks

Nasim Paykari, Damian Lyons, Mohamed Rahouti

ACM Transactions on Cyber-Physical Systems · 31.10.2026 · 10 (4) · 1-33

DOI: 10.1145/3818616 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Cyber-Physical Systems, online erschienen am 13.07.2026. Verfasst von Nasim Paykari und 2 weiteren Autor:innen. Die Arbeit nennt 53 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Division of Undergraduate Education.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Multi-robot navigation to an out-of-view destination in dynamic, GPS-denied environments is challenging because robots must plan over a changing, non-metric connectivity graph while maintaining route continuity under sensing and topology disruptions. We present a decentralized pathfinding framework in which robots record commonly observed visual Common Landmarks (CLs) as blockchain transactions, forming a continuously updated shared CL-graph for navigation beyond the current field of view. On top of a multi-goal weighted search over this CL-graph, we introduce two resilience mechanisms, PathShift and PathSwap , which precompute up to \(k-1\) backup paths to reduce recovery overhead when the primary route is invalidated by CL-recognition failures or robot/edge loss. Across simulations on randomly generated CL-graphs with varying robot counts and graph densities (100–1,000 trials), PathShift provides the strongest overall recovery performance. In the representative \(k=3\) , 15-robot, edge-probability-0.4 setting, it achieves the lowest average backtracking cost under both edge removal (0.04) and robot failure (0.01), compared with PathSwap (0.73/0.51), Yen’s algorithm (0.06/0.02), and all-paths Dijkstra (0.12/0.06). It also attains a 100% recovery success rate in our non-adversarial failure model, while PathSwap achieves 88–89%. Runtime experiments further show that PathShift and PathSwap execute faster than Yen’s and all-paths Dijkstra as robot count and edge density increase. Compared with D* Lite in this non-metric CL setting, PathShift yields similar main-path lengths while providing slightly more alternative paths on average (3.3 vs. 3.25), indicating stronger failover support. These results identify PathShift as the most effective lightweight strategy for resilient decentralized navigation in the evaluated setting.

Förderung

  • Division of Undergraduate Education

Zitieren

APA

Paykari, N., Lyons, D., & Rahouti, M. (2026). Decentralized, Distributed, and Resilient Pathfinding for Dynamic, GPS-Denied Environments Using Visual Common Landmarks. ACM Transactions on Cyber-Physical Systems, 10(4), 1-33. https://doi.org/10.1145/3818616

Vancouver

Paykari N, Lyons D, Rahouti M. Decentralized, Distributed, and Resilient Pathfinding for Dynamic, GPS-Denied Environments Using Visual Common Landmarks. ACM Transactions on Cyber-Physical Systems. 2026;10(4):1-33. doi:10.1145/3818616

BibTeX
@article{Paykari2026,
  author = {Paykari, Nasim and Lyons, Damian and Rahouti, Mohamed},
  title = {Decentralized, Distributed, and Resilient Pathfinding for Dynamic, GPS-Denied Environments Using Visual Common Landmarks},
  journal = {ACM Transactions on Cyber-Physical Systems},
  year = {2026},
  volume = {10},
  number = {4},
  pages = {1--33},
  doi = {10.1145/3818616}
}
Kostenlos starten →