Project 01 / Robotics · Planning under uncertainty
Dynamic Programming for Belief-Aware Robot Navigation
Combining offline dynamic programming with online Bayesian belief updates to study how a robot should navigate when it cannot confidently localize itself.
01 / overview
Navigation doesn’t end at the first goal.
A robot that repeatedly receives new goals has to do more than make progress. It has to preserve a useful estimate of where it is.
This project studies persistent navigation under partial observability: stochastic actions, noisy observations, and a belief distribution over possible grid locations. The central question is whether actively maintaining that belief improves long-run navigation.
Goal-conditioned dynamic programming, online Bayesian belief updates, myopic and belief-aware policies, and simulation experiments across three diagnostic environments. A collaborative project with Jessie Chan.
02 / approach
Plan offline. Maintain belief online.
The implemented planner uses a shared dynamic-programming backbone over physical grid states. For each active goal, it computes a value table V_g(s); both partially observable policies evaluate that table through the current belief.
- OfflineMap + goal → value table
Precompute goal-conditioned navigation value over known grid states.
- Online · observeBayesian belief update
Combine stochastic motion, noisy observations, and the prior belief.
- Online · decideScore candidate actions
Use expected navigation value; optionally penalize expected posterior entropy.
- Online · actMove, observe, repeat
Update the belief and continue when the next goal arrives.
Es ∼ b[Vg(s)] = ∑s b(s) Vg(s)
Averaging over possible locations avoids treating the most likely state as certain.Myopic policy · λH = 0
Prioritizes expected goal-directed value under the current belief, without an entropy regularizer.
Belief-aware policy · λH = 0.5
Adds an expected posterior entropy term to balance immediate progress with localization uncertainty.
03 / experiments
Three environments. Three different stories.
Each diagnostic run spans 200 steps with transition noise p = 0.25 and observation noise σ = 0.5. A fully observable planner provides an upper reference. Task progress, belief quality, and empirical safety are measured separately.
Distinct landmarks make uncertainty manageable.
An additional landmark breaks the map’s symmetry. Both partially observable planners complete 16 goals, compared with 17 for the fully observable reference.
Watch the simulation
33 sec · Silent replayText description of the replay
Three grid-world views show the same environment under different policies. Blue shading represents the location belief; a green circle marks the true position, an outlined square marks the MAP estimate, an orange cross marks the goal, and stars mark landmarks. A line traces the recent path. Each panel displays goal completions, collisions, belief entropy, probability assigned to the true state, and MAP error as the robot moves.
An additional landmark breaks the map’s symmetry. Both partially observable planners complete 16 goals, compared with 17 for the fully observable reference. The results table below summarizes the diagnostic comparison.
| Metric | Myopic | Belief-aware |
|---|---|---|
| Goals completed ↑ | 16 | 16 |
| Mean entropy ↓ | 0.4756 | 0.4512 |
| MAP error ↓ | 0.215 | 0.180 |
| Collisions ↓ | 9 | 9 |
Belief awareness slightly improves localization while preserving throughput.
Explore the original entropy trace
Results transcribed from Tables I and II of the report. These are single-seed diagnostic runs, not multi-seed benchmark estimates.
04 / results
The gain is real. So is the tradeoff.
Low ambiguity preserves throughput.
In the asymmetric map, both partially observable planners reach 16 goals against the reference’s 17. Belief awareness reduces MAP error from 0.215 to 0.180 without sacrificing completion.
Bottlenecks improve localization, not safety.
MAP error falls from 1.440 to 0.290 and completed goals rise from 4 to 6. But collisions rise from 9 to 12, and invalid attempts from 11 to 15. More accurate localization alone does not ensure safer behavior.
Symmetry exposes confident mistakes.
Entropy falls from 0.8490 to 0.7959 while MAP error rises from 0.580 to 1.825. Completed goals drop from 5 to 2. The policy can concentrate its belief on the wrong aliased state.
05 / lessons
Measure correctness, not just certainty.
The next iteration should evaluate deeper belief-space planning, explicit collision-aware constraints or safety filters, and calibration-oriented belief metrics. Multi-seed sweeps over noise and objective weights would establish how consistently the observed tradeoffs hold.
The experiment changed the design question: from “can the planner lower uncertainty?” to “when does information-seeking produce correct localization and safe progress?”
06 / Resources
Explore the details.
The full writeup
Navigation Without a Finish Line
Methods, experimental details, figures, and references. PDF · 6 pages.
Authors
Arjen Singh & Jessie Chan · UCLA ECE M237, Spring 2026
Tools & methods
Python · Dynamic programming · Bayesian filtering · Simulation
Next case study / 02