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

Verification and Synthesis of Plans With Cyclic Flow of Control

Siddharth SrivastavaUniversity of Massachusetts, Amherst[Home Page]

Notice:  Hosted by Richard Waldinger

Date:  2011-08-04 at 16:00

Location:  EJ228 (SRI E Building)  (Directions)

   Abstract

Automated planning represents one of the fundamental tasks of problem solving: computing a sequence of actions which will change a given situation to a more desirable, goal situation. In this talk I will present my work on solving "generalized" planning problems, where the objective is to find an algorithmic, generalized plan that will solve infinitely many similar planning problems.

Generalized plans can also express algorithms. Although this makes the synthesis and verification of generalized plans incomputable in general, I will present a unified approach for accomplishing both of these tasks in many interesting, non-trivial settings. Our approach computes the conditions under which a generalized plan will terminate and reach the goal using original methods for finding termination conditions for a class of abacus programs (a Turing complete model of computation). Our approach for synthesis of generalized plans is to incrementally generate a relevant linear plan, to generalize this plan, and then to merge it with an existing generalized plan, which is initially empty. In this process, we use abstract interpretation to generalize linear plans by identifying loop invariants as well as to determine plan segments that share the same context and can therefore be merged together.

In addition to results on planning domains, I will also present some initial results of using these methods for program synthesis. Finally, I will touch upon some of our new results on a \emph{sound and complete} approach for verification and synthesis of generalized plans with qualitative actions.

[Joint work with Hector Geffner, Neil Immerman and Shlomo Zilberstein]

   Bio for Siddharth Srivastava

Siddharth Srivastava received his Ph.D. in computer science from the University of Massachusetts Amherst in 2010. His research interests include various aspects of knowledge representation, automated planning, and program synthesis in AI, as well as formal methods for model checking and static analysis of programs. He recently received an Honorable Mention for the Best Dissertation Award at ICAPS 2011 and an Outstanding Dissertation Award from UMass, Amherst. His work on determining termination conditions for plans with loops won a Best Paper Award at the International Conference on Automated Planning and Scheduling, 2010. He also received a Best Final Year Project award for his undergraduate thesis at IIT Kanpur.

   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