| A number of systems and applications model time explicitly and so require expressive temporal formalisms and efficient reasoning algorithms. In particular, an increasing number of planning systems deal with metric, quantitative time. This dissertation presents a set of new, efficient, provably correct algorithms for expressive temporal reasoning, based on the use of constraint satisfaction problems and techniques, and demonstrates how they can be used to improve the expressiveness and efficiency of planning and execution systems.; First, the Disjunctive Temporal Problem (DTP) is examined. The DTP is a very powerful and expressive constraint-based, quantitative temporal reasoning formalism that subsumes a number of other previous formalisms, and is capable of representing many planning and scheduling problems. A new algorithm for solving DTPs is presented, and fully implemented in a system called Epilitis. This algorithm achieves significant performance improvement (two orders of magnitude on benchmark problem sets containing randomly generated problems) relative to previous state-of-the-art solvers. In addition, DTP solving is thoroughly examined: alternative solving techniques are investigated, classified, and theoretically analyzed.; In addition to solving DTPs, the execution and dispatching of plans encoded as DTPs is addressed. A novel dispatch algorithm for such plans is presented; amongst other desirable properties, it retains all the available flexibility in the occurrence of events during execution. This is the first known dispatch algorithm for DTPs.; Next, new constraint-based temporal formalisms are defined that allow, for the first time, the representation of temporal and conditional plans, dealing simultaneously with the uncertainty of the outcome of observations and with expressive temporal constraints. The formalisms are named the Conditional Simple Temporal Problem (CSTP) and the Conditional Disjunctive Temporal Problem (CDTP). Appropriate consistency checking algorithms accompany the definitions. In addition, complexity results, theoretical analysis, and tractable subclasses are identified. We also note that both CDTP and the CSTP consistency checking can be translated to DTP consistency checking, indicating a strong theoretical connection among the various formalisms.; We subsequently employ the above results in temporal reasoning to address a number of previously unsolvable problems in planning in a conceptually clear, and potentially very efficient, way. Leveraging the expressivity of our new formalisms, we present planning algorithms that can deal with richly expressive plans that include temporal constraints and conditional execution contexts. In particular we solve the problems of plan merging, plan cost optimization, and in-context plan cost evaluation. |
