## 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.

More information (http://robotics.eecs.berkeley.edu/~nilim) or

Send mail to the author : (nilim@eecs.berkeley.edu)

Edit this abstract