A theory of robust planning

A notion of robustness for planning problems is introduced in a model with uncertainty, based on a global probabilistic model. The authors define the notion of a robust strategy within this model, which allows comparison of different strategies. They then study how an outside observer would know in advance the level of robustness of a system. The analysis is based on the complexity class IP, the class of problems that can be efficiently verified by a random interactive proof system. The approach was applied to a mobile robot trying to execute a plan in a geometrical environment following a strategy that uses various sensors to cope with the uncertainty. Various examples of robust and nonrobust strategies are given