Search papers, labs, and topics across Lattice.
This paper addresses the problem of navigation in environments with uncertain connectivity, where nodes have varying visibility levels, enabling observation of distant edges. They propose a heuristic algorithm that balances the cost of detouring to high-visibility locations with the information gained, optimizing a custom observation reward and traversal cost. The method samples shortest paths on environment realizations to define edge utility and estimate the path with the highest reward, demonstrating lower traversal costs and reduced computational overhead compared to existing methods.
Strategically detouring to vantage points with high visibility slashes navigation costs in uncertain environments, outperforming shortest-path baselines and computationally expensive alternatives.
Navigating an environment with uncertain connectivity requires a strategic balance between minimizing the cost of traversal and seeking information to resolve map ambiguities. Unlike previous approaches that rely on local sensing, we utilize a framework where nodes possess varying visibility levels, allowing for observation of distant edges from certain vantage points. We propose a novel heuristic algorithm that balances the cost of detouring to high-visibility locations against the gain in information by optimizing the sum of a custom observation reward and the cost of traversal. We introduce a technique to sample the shortest path on numerous realizations of the environment, which we use to define an edge's utility for observation and to quickly estimate the path with the highest reward. Our approach can be easily adapted to a variety of scenarios by tuning a single hyperparameter that determines the importance of observation. We test our method on a variety of uncertain navigation tasks, including a map based on real-world topographical data. The method demonstrates lower mean cost of traversal compared to a shortest path baseline that does not consider observation and has exponentially lower computational overhead compared to an existing method for balancing observation with path cost minimization.
