Robust Solutions to Markov Decision Problems with Uncertain Transition Matrices: Its Applications in Robust Aircraft Path Planning

Arnab Nilim
(Professor Laurent El Ghaoui)
Eurocontrol 014692, (DARPA) F33615-01-C-3150, and (NSF) ECS-9983874

Optimal solutions to the Markov decision problems (MDPs) are often sensitive with respect to the state transition probabilities. In many practical problems, the estimation of the transition probabilities is far from accurate. Hence, estimation errors are, together with the curse of dimensionality, a limiting factor in applying MDPs to real-world problems. We propose an algorithm for solving finite-state and finite-action MDPs, where the solution is guaranteed to be robust with respect to the estimation errors of the state transition probabilities. Our algorithm involves a statistically accurate yet numerically efficient representation of uncertainty via likelihood or entropy functions. The worst-case complexity of the robust algorithm is within a factor log n (n is the number of states) of the original Bellmann recursion. Hence, robustness can be added at almost no extra computing cost. We applied our algorithm to the problem of the dynamic routing of an aircraft under stochastic obstacles, where the probabilties of the obstacles are unknown but bounded. We showed that a siginificant reduction in delay can be obtained by using our robust strategies with respect to the nominal strategy when the data is uncertain.

[1]
L. El Ghaoui and A. Nilim, "Robust Solutions to Markov Decision Problems with Uncertain Transition Matrices" (submitted for publication).
[2]
A. Nilim, L. El Ghaoui, and V. Duong, "Robust Dynamic Routing of Aircraft under Uncertainty," IEEE Digital Avionics Systems Conf., Irvine, CA, November 2002.
[3]
A. Nilim, L. El Ghaoui, and V. Duong, "Routing of Aircraft with Uncertain Weather Probabilities," Institute of Operations Research and Management Sciences, San Jose, CA, November 2002.
[4]
A. Nilim, L. El Ghaoui, M. Hansen, and V. Duong, "Trajectory-based Air Traffic Management (TB-ATM) under Weather Uncertainty," USA/EUROPE ATM R&D Seminar, Santa Fe, NM, December 2001.
[5]
A. Nilim, L. El Ghaoui, M. Hansen, and V. Duong, "Dynamic Routing of Aircraft under Uncertainty," Institute of Operations Research and Management Sciences, Miami, FL, November 2001.