Jongann Lee

About

Research interests, background, and contact.
Publications

Published papers in planning, robotics, and equivariant learning.
Projects

Explore the rest of my work.

Navigating in Uncertain Environments with Heterogeneous Visibility

Jongann Lee, Melkior Ornik
University of Illinois Urbana-Champaign
IROS 2026
Paper Code arXiv Poster

Introduction

Traditional path planning under uncertainty, such as the Canadian Traveller Problem (CTP) and Informative Path Planning (IPP), often overlooks heterogeneous visibility.

In real-world environments, vantage points offer varying levels of information. We propose a framework that:

  • Exploits High-Visibility Nodes: Leverages non-local sensing to observe distant edges from specific vantage points.
  • Balances Exploration/Exploitation: Uses an observation reward combined with traversal costs to balance both.

Our approach prioritizes informative vantage points when planning in high-uncertainty environments.

Problem Setting

The environment is modeled as a graph G = (V, E) with source vs and target vt.

Key Components:

  • Traversal Cost: Each edge e has a cost c(e).
  • Visibility Mapping: vis(v) ⊆ E defines edges observable from node v.
  • Edge Blockages: A subset Eb ⊂ E is statically blocked. No prior knowledge of the probability distribution of blockages is assumed.

Objective: Navigate from vs to vt with minimum cumulative traversal cost.

Since minimum path cost is a random variable, the policy should balance information gain with path cost minimization.

Short Diverse Path Sampling

We generate a path tree of depth r by recursively branching n times, where each branch represents a shortest path computed after removing all edges within an m-hop radius of a node sampled from the parent path.

Poster sampling tree with miniature graphs showing shortest paths after adding virtual obstacles at successive branches.
Path sampling by recursively adding virtual obstacles.

Path Generation

We define a path reward R(P) that balances cost-efficiency with the information gain of visiting high-visibility nodes.

1. Edge Utility (U): An edge’s utility is based on its frequency in the diverse path set, weighted by depth in the sampled tree.

2. Observation Reward (Robs): The sum of utilities for all currently unobserved edges visible from node v:

Robs(v)=∑e∈vis(v)U(e)(1−1obs(e))

Already observed edges contribute no further reward, including when encountered again along a candidate path.

3. Overall Path Reward:

R(P)=λ∑v∈PRobs(v)−∑e∈Pc(e)

The path with the highest reward is selected from a second sampled path tree. The weight λ controls the importance of observation.

Experiment: Plateau

Poster plateau grid: source in green, target in cyan, high-visibility plateaus in yellow, and chokepoint edges in red.
Plateaus offer high visibility at a high entry cost.

We test on a grid with plateaus (high visibility, high entry cost). Chokepoint edges have an independent blockage probability p (not used during planning). We compare our method against a Shortest Path (SP) baseline and RPP.

Result on Plateau Environment (p = 0.5)
Method Mean Std Dev Runtime (ms)
SP 43.75 16.05 2.5
RPP 34.00 0.00 11083
Ours (λ = 3) 36.00 6.00 94.2

On a different plateau environment we evaluate the performance of our algorithm with different reward ratios λ.

Mean Path Cost (Plateau)
Blockage p SP λ = 0 λ = 3 λ = 10
0 22.00 22.00 22.00 22.00
0.1 30.10 30.10 29.98 30.51
0.2 35.35 35.35 34.77 34.85
0.3 39.20 39.20 37.62 37.63
0.4 42.46 42.46 39.71 39.63
0.5 45.11 45.11 40.98 40.93

RPP achieves the lowest mean cost in the first comparison, while our method requires substantially less computation.

Experiment: Natural Terrain

We test on a natural terrain environment with mountains (high visibility, high traversal cost). Three obstacles are randomly placed with probability p.

Poster natural terrain comparison showing a blue shortest-path route, a red visibility-aware route, and three black obstacles.
Mountains provide high-visibility vantage points.

The shortest path baseline (blue) and our proposed method (red) are compared; dashed lines show the initial intended path and the solid lines show the actual path used.

Mean Path Cost (Natural Terrain)
Blockage p SP λ = 1 λ = 3
0 147.62 150.49 150.80
0.2 153.37 151.31 151.61
0.4 157.41 152.07 152.40
0.6 159.40 152.76 153.19
0.8 159.01 153.38 153.97

Discussion

Baseline Equivalence: At λ = 0, the proposed agent’s behavior is equivalent to that of the Shortest Path (SP) agent.

Observation Weighting: Increasing λ assigns higher priority to edge observations, improving performance in these environments when blockages are likely.

With no blockages, the observation detour increases cost on the natural terrain map. These experiments are simulations, including the map based on real-world topographical data.

BibTeX

@inproceedings{lee2026heterogeneousvisibility,
  title={Navigating in Uncertain Environments with Heterogeneous Visibility},
  author={Lee, Jongann and Ornik, Melkior},
  booktitle={IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year={2026},
  eprint={2603.03495},
  archivePrefix={arXiv},
  primaryClass={cs.RO},
  url={https://arxiv.org/abs/2603.03495}
}

Acknowledgments

This work was supported by the Office of Naval Research under grants N-00014-25-1-2369 and N-00014-25-1-2519. We thank Manav Vora for help with the writing.