CSTRIPS: Towards Explicit Concurrent Planning

M. Oglietti and A. Cesta

In Proceedings of the 3rd Italian Workshop on Planning and Scheduling, AI*IA Symposium, Perugia, Italy, September, 2004

This paper presents a formalism that extends the STRIPS planning language to explicitly deal with concurrent actions. According to this approach, possibly concurrent activities of a domain can be modeled by representing them explicitly as different concurrent threads. The first part of the paper introduces this empowered STRIPS, called Concurrent STRIPS (or CSTRIPS), by giving its syntax and semantics. The second part addresses aspects that help understand the effectiveness of CSTRIPS. It first illustrates a complete example of a quite complex domain in which causal and process reasoning are intertwined, and CSTRIPS is shown to support very well the modeling phase. Then two aspects are addressed which are connected to the computational complexity of reasoning in CSTRIPS: (a) the introduction of the explicit representation of concurrency is shown not to worsen the computational complexity of the problem solving phase; (b)it is shown that in highly parallel domains it is possible to speed up the reasoning by representing the domain as concurrent threads.