|Institutional Office Address
DMIF, Room NN2
|Research Project Title
Computational Complexity and Logical Expressiveness of Automated Planning Languages Supporting Temporal Reasoning
|Research Project Description
Automated Planning is a field of Artificial Intelligence that studies how to build systems capable of acting autonomously to pursue a given goal. In recent years, much research has been focused on planning problems where the notion of time is explicitly considered. Our reearch studies the theoretical properties of planning languages supporting temporal reasoning. In particular, we focus on timeline-based planning, a framework originally introduced at NASA for planning of long-term space missions.
In timeline-based planning, problems are modeled as systems composed of a set of independent, but interacting, components, whose behavior over time is governed by a set of temporal constraints. In contrast, common action-based planning languages model problems by specifying which actions an executor can perform to affect its environment. For this reason, timeline-based planning systems are useful in modeling planning problems where an high number of different components have to cooperate to obtain the given goal. Despite its applicability, theoretical properties of timeline-based planning languages are still not well understood. A complete picture of the computational complexity of the different variants of timeline-based planning problems is missing, as well as a formal comparison with other planning formalisms in terms of expressiveness. Our project aim at filling these gaps in the formal understanding of the paradigm.