Planning Robust Temporal Plans A Comparison Between CBTP and TGA Approaches

Yasmina Abdeddaim, Eugene Asarin, Matthieu Gallien, Felix Ingrand, Charles Lesire, Mihaela Sighireanu

Planning for real world applications, with explicit temporal representation and a robust execution is a very challenging problem. To tackle it, the planning community has proposed a number of original and successful approaches. However, there are other paradigms "outside" the Automated Planning field which may prove to be successful with respect to this objective. This paper presents a comparison of two "planning" approaches dealing with temporal and/or discrete uncertainties and with a strong emphasis on robust execution. The first approach is based on chronicles and constraint satisfaction techniques; it relies on a causal link partial order temporal planner, in our case IxTeT. The second approach is based on timed game automata and reachability analysis, and uses the UPPAAL-TIGA system. The comparison is both qualitative (the kind of problems modeled and the properties of plans obtained) and quantitative (experimental results on a real example). To make this comparison possible, we propose a general scheme to translate a subset of IxTeT planning problems into UPPAAL-TIGA game-reachability problems. A direct consequence of this automated process would be the possibility to apply validation and verification techniques available in the timed automata community.

Subjects: 1.11 Planning; 16. Real-Time Systems

Submitted: Jun 27, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.