Stanford OnlineStanford AA274A Principles of Robotic Autonomy | Autumn 2019 | Decision Making Under Uncertainty
Stanford Online
Decision under uncertainty 0:05
The lecture turns to high-level decisions such as whether to cross an intersection or change lanes. The point is that these choices depend on perceptual uncertainty and on uncertainty about other agents, especially people around you. You need a model that can handle safety and efficiency together. The plan is to focus first on the mathematical setup, then on baseline algorithms. Dynamic programming and Markov decision processes are the main tools today.
Sequential control model 3:31
A sequential decision problem is written as a discrete-time system with state x, control u, control limits, and an additive cost made of stage costs plus a terminal cost. The sequence is chosen once, so the result is open loop and can fail if the state drifts from the nominal path. Additivity matters because it lets you avoid brute-force search. The key idea is the principle of optimality: if a full path is optimal, each tail subproblem must also be optimal.
Tail optimality 19:30
Tail optimal sequences are optimal for tail problems, and that rests on additive cost. If a tail were not optimal, you could swap in a lower-cost one and beat the sequence you first called optimal. In the stochastic case, backward and forward reasoning are not the same, and the same idea will need an expected value. For now, the point is that this clean deterministic setup makes the structure easier to see.
Dynamic programming 24:02
The principle cuts computation sharply. If you already know the best ways to reach F from C, D, and E, then from B you only compare those three choices and reuse the saved tail costs. Dynamic programming works backward from the end. You set the terminal cost, then solve each state by minimizing immediate cost plus the stored cost to go. It gives the global minimum, and constraints can actually help by reducing the actions you must check.
Stochastic dynamic programming 39:31
Expectation is a linear way to rank random outcomes, but variance and other risk terms make the problem nonlinear. Then dynamic programming no longer applies cleanly. In the stochastic setting, the next state includes a disturbance whose distribution depends only on the current state and control. That Markov assumption lets you work with closed-loop policies and still prove a principle of optimality for the tail of the problem.
Inventory example 48:03
The example is a warehouse with stock level as the state, ordering quantity as the control, and demand as the random disturbance. Stock next time is the leftover after demand, with a limit that total stock cannot exceed two units. Demand takes values 0, 1, or 2 with probabilities 0.1, 0.7, and 0.2. Using dynamic programming, the optimal action at state zero and time two is to order one unit.
Approximation and course close 1:01:31
Dynamic programming becomes hard when the state space is large, the probability model is unknown, or the data changes online, as in inventory control, scheduling, or a robot whose transition model must be updated from current capabilities. The lecture points to two fixes: approximate in value space, by replacing the optimal cost to go with a surrogate, or approximate in policy space, by searching over a restricted policy class. Examples include simpler dynamics for motion planning, neural networks that learn cost to go from data, and state aggregation into macro states.
AI-generated summary. It can be wrong or incomplete - check anything that matters against the original.
