Search |  Contact |  SRI Home 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.

AIC Seminar Series

Efficient Solutions to Temporal Constraint Satisfaction Problems with Preferences

Bart PeintnerUniversity of Michigan

Date:  2005-06-13 at 10:00

Location:  EJ228  (Directions)

   Abstract

Recent planning and scheduling applications have successfully used the Temporal Constraint Satisfaction Problem (TCSP) formalism for representing events to be scheduled and temporal constraints between them. Given a TCSP, the task is to find a schedule or a set of schedules that satisfies all constraints in the problem, or to prove that none exists. TCSPs have at least two limitations in the context of planning applications: the hard bounded constraints often do not match reality; and it is difficult for a planning system to recover if any constraint is violated during plan execution. To address both limitations, we have extended the TCSP formalism to include preferences, which allow constraints to be satisfied to different degrees. Once preferences are added, the problem changes from a satisfaction problem to an optimization problem, and thus requires new algorithms for finding solutions. In this talk, I will begin by describing our Autominder planning application, how it uses TCSPs, and its requirements for a TCSP solver. Then, I will review the basics of TCSPs, show how to extend them with preferences, and describe one of the algorithms we have developed to quickly find high-valued schedules for a given TCSP with Preferences.

   Note for Visitors to SRI

Please arrive at least 10 minutes early in order to sign in and be escorted to the conference room. SRI is located at 333 Ravenswood Avenue in Menlo Park. Visitors may park in the visitors lot in front of Building E, and should follow the instructions by the lobby phone to be escorted to the meeting room. Detailed directions to SRI, as well as maps, are available from the Visiting AIC web page.

SRI International
©2014 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493
SRI International is an independent, nonprofit corporation. Privacy policy