In the field of artificial intelligence, a great deal of effort has been extended toward improving methods for temporal constraint satisfaction. Research on this topic typically addresses either the representation of a constraint system, the algorithms necessary to compute its resolution, or the application of these techniques to real-world problems commonly faced in practice.; However, there are certain situations where existing temporal representations and reasoning systems remain inadequate. First, many state-of-the-art solvers are unable to provide much more than a notice of failure when encountered with infeasibility, whereas one may instead desire some form of partial plan. Second, there are some scenarios where the Constraint Satisfaction Problem contains a mixture of both finite-domain and temporal constraints, requiring a hybrid approach to obtain a jointly feasible solution. Finally, there may be cases where the constraints of a given problem are themselves uncertain. When faced with such uncertainty, it may be useful to precompute a set of contingent solutions for all possible scenarios, or to instead produce a single robust solution that is likely to be supported in the greatest number of realizations.; This dissertation proposes a series of powerful extensions to the Disjunctive Temporal Problem to accommodate each of the aforementioned concerns. We first investigate the problem of infeasibility in DTPs by proposing the application of partial constraint satisfaction. We present both systematic and approximate algorithms to achieve this objective, and expose a strong connection to the related problem of preferential optimization. Second, we consider a hybrid constraint system capable of expressing both finite-domain and temporal constraints. This requires not only a new representation, but also a new algorithm for establishing consistency of the hybrid problem. Third, we propose a method to handle uncertainty with respect to the constraints of a DTP by introducing the Uncertain Disjunctive Temporal Problem. This new formalism allows the encoding of meta-level decisions that lie outside the direct control of the executing agent, giving rise to several forms of resolution. We conclude with a novel application of this enhanced temporal constraint satisfaction system to the interesting and unusual domain of rectangle packing.
展开▼
