SRI's Artificial Intelligence Center Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap.A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ASRI International.  333 Ravenswood Avenue.  Menlo Park, CA 94025-3493. SRI International is a nonprofit corporation. Search  |  Contact  |  SRI Home
Space 1x1
 AIC Home   >   Background   >   Publications   >   Details
Space 1x1

Publication Details

Strong Controllability of Disjunctive Temporal Problems with Uncertainty

by Peintner, B. and Venable, K. B. and Yorke-Smith, N.

in Proceedings of the Thirteenth International Conference on Principles and Practices of Constraint Programming (CP'07) pp. 856-863,

Address: Providence, RI
Sep 2007.
   Abstract

The Disjunctive Temporal Problem with Uncertainty (DTPU) is an extension of the Disjunctive Temporal Problem (DTP) that accounts for events not under the control of the executing agent. We investigate the semantics of DTPU constraints, refining the existing notion that they are simply disjunctions of STPU constraints. We then develop the first sound and complete algorithm to determine whether Strong Controllability holds for a DTPU. We analyze the complexity of our algorithm with respect to the number of constraints in different classes, showing that, for several common subclasses of DTPUs, determining Strong Controllability has the same complexity as solving DTPs.

   Electronic Copies

Adobe PDF

BibTeX

EndNote
Copyright ©©2007 Springer-Verlag

   Associated Projects

CALO

Cognitive Assistant that Learns and Organizes
As part of DARPA’s Perceptive Agent that Learns (PAL) program, SRI and team members are working on developing a next-generation "Cognitive Agent that Learns and Organizes" (CALO).
 

   AIC Personnel

Name Title E-mail
Peintner, Bart Computer Scientist
Yorke-Smith, Neil Computer Scientist

Spacer 1x1
Spacer 1x1
 
SRI International

©2008 SRI International, 333 RavenswoodAvenue, Menlo Park, CA 94025-3493
SRI International is a nonprofit corporation. Privacy policy