Home : Project Archive : Automated Synthesis of Planners and Schedulers
 

Automated Synthesis of Planners and Schedulers

PRINCIPAL INVESTIGATORS: Dr. Douglas R. Smith, Prof. Subbarao Kambhampati

OBJECTIVE: This project focuses on applying synthesis technology to the routine production of high-performance, specialized planning and scheduling tools.

APPROACH: Software synthesis is the process of transforming a high-level declarative specification of a planning or scheduling problem into correct and highly efficient code.

PROGRESS: We are about 18 months into the current ARPI contract. We have been working to develop the Planware system which will mechanize KIDS-style synthesis of high-performance schedulers so that a domain expert who is not trained in program synthesis can produce and evolve effective schedulers. The user is required to specify the scheduling problem by selecting/giving task features, resource features, and cost information. Initially these will be selected from a pre-existing library/KB. Later we will allow the user to add some kinds of new task and resource features. Planware will have two levels of automation. The first is fully automatic generation of the scheduler from the user problem statement. The second allows a more sophisticated user to guide the implementation decisions, which can result in more efficient code.

We recently demonstrated the automatic synthesis of a transportation scheduler in Planware, given just a user selection of task attributes and resource type.

PRODUCTS: The ITAS (In-Theater Airlift Scheduler) is installed at PACAF AOC, Hickham AFB, and is used for exercises (CPX's, JWID-95, and IFD4). An NT-version has been developed and delivered to the Barrelmaster at AMC (Air Mobility Command).

FY97 ACCOMPLISHMENTS:

1. Domain-theory construction in Planware -- Most of our effort during FY97 has focused on automatically constructing and refining domain theories. This was the most time-consuming and difficult task in generating software using KIDS.

2. Ladder construction in Planware -- Wecontinued to develop and refine support for algorithm design by classification in Specware/Planware.

3. Extensions to the Constraint Propagation code generator -- We generalized our tactic for generating constraint propagation code and continued experiements with it.

4. Taxonomy of resource theories -- We deveoped a taxonomy of theories for various classes of resources. This result will enable us to more easily build domain theories for new scheduling applications.

5. Integer Linear Programming -- We performed an experiment in generating problem-specific code for Integer Linear Programming problems, based on our constraint propagation design tactic.

6. Synthesis of State-space planners -- Using KIDS and Kambhampati's theory of refinement planning, we synthesized customized planners in blocks world and logistics domains and showed that they out-perform traditional planners by several orders of magnitude.

7. Work on unifying the refinement planners -- One of the pre-requisites for automated synthesis of planners is a declarative theory of planning. We have recently extended the refinement planning framework and proposed a sub-class of refinement planners called disjunctive planners, that cover several novel planning paradigms such as Graphplan, SATPLAN and COPS. This will, in future, support synthesis of extended planners.

FY98 OBJECTIVES:

1. Develop the interface to Planware so that the user can extend the task and resource feature library. This requires a structured dialog to extract the necessary formal information without requiring the user to speak higher-order logic.

2. Improve the heuristics that are used to control the design/implementation process, so that the automated scheduler generator produces good code for a wide range of specified problems.

3. Support the specification of problems involving multiple kinds of resources being scheduled (e.g. aircraft, crews, fuel, mog).

4. Specify and generate a crew scheduling system for TBM Core System, in collaboration with MITRE and BBN (using KIDS). Continue the evolution of ITAS in collaboration with BBN (using KIDS).

5. Synthesis of Partial Order Planners: We expect to be able to demonstrate synthesis of customized partial order planners, and evaluate the efficiency of synthesized planners.

6. Developing the theory of Disjunctive planners: We expect to further develop the theory of disjunctive planners, in preparation for their eventual automated synthesis.

TECHNOLOGY TRANSITION:

1. CAMPS (Combined Air Mobility Planning System) is a new joint effort by Kestrel, CMU, and BBN with Logicon as overall contractor. The aim is to the operational next-generation scheduling tools for Air Mobility Command, Scott AFB. CAMPS incorporates Kestrel's high-performance scheduling technology, and CMU's rescheduling and mixed-initiative technology.

system name: CAMPS
purpose: Strategic airlift scheduling
environment requirements: NT, Java, C++, CommonLisp
POC phone: 315-330-3655
POC e-mail: lemmer@ai.rl.af.mil

2. ITAS (In-Theater Airlift Scheduler) is installed at PACAF AOC, Hickham AFB, and is used for exercises (CPX's, JWID-95, and IFD4). Impact is measured in terms of time and effort to produce a flyable schedule. PACAF personnel have stated that they would be much more productive using ITAS in a contingency. ITAS was produced using significant new DARPA-sponsored technology in program synthesis which is applied to DoD scheduling problems.

system name: ITAS
purpose: Theater cargo airlift scheduling
environment requirements: Macintosh computer w/ MS Foxpro and MCL
POC phone: 415-493-6871
POC e-mail: smith@kestrel.edu

3. KIDS is installed at over 40 sites worldwide. It has been used, for example, at Rome Lab for synthesizing Nuclear Power Plant Maintenance schedulers, and at ASU for synthesizing planning algorithms. Impact is measured in terms of (1) productivity -- time to produce an efficient, correct algorithm for a given problem, and (2) speed of the resulting algorithms.

system name: KIDS
purpose: program synthesis
environment requirements: Sparcstation 2 or higher, Franz CL, Software Refinery
POC phone: 415-493-6871
POC e-mail: smith@kestrel.edu

PUBLICATIONS:

Burstein, M.B. and Smith, D.R., ITAS: A Portable Interactive Transportation Scheduling Tool Using a Search Engine Generated from Formal Specifications, in Proceedings of the Third International Conference on Artificial Intelligence Planning Systems (AIPS-96), Edinburgh, AAAI Press, May 1996, 35-44.

Douglas R. Smith, Eduardo A. Parra, and Stephen J. Westfold, Synthesis of Planning and Scheduling Software, in Advanced Planning Technology, (Ed. A. Tate), AAAI Press, Menlo Park, California, 1996, 226-234.

Smith, D.R., Toward a Classification Approach to Design, invited paper in Proceedings of the Fifth International Conference on Algebraic Methodology and Software Technology, AMAST'96, LNCS 1101, Springer Verlag, 1996, 62--84.

Carla P. Gomes, Douglas R. Smith, and Stephen J. Westfold, Synthesis of Schedulers for Planned Shutdowns of Power Plants, Proceedings of the Eleventh Knowledge-Based Software Engineering Conference, IEEE Computer Society Press, Los Alamitos, California, September 1996, 12-20.

1. Failure driven explanation-based learning of search control knowledge. S. Kambhampati, S. Katukam and Y.Qu. Artificial Intelligence, Vol 88, pp. 253-315. 1996.

2. On the nature and role of modal truth criteria in planning. S. Kambhampati and D.S. Nau. Artificial Intelligence. Vol. 82. Pp. 129- 155. 1996.

3. Theoretical Contributions of Artificial Intelligence, S. Kambhampati. Invited Sidebar. IEEE Computer 50th anniversary issue. 1996.

4. Planning and Scheduling. T. Dean (Professor, Brown University), S. Kambhampati, CRC Handbook on Computer Science and Engineering. CRC Press. 1996. pp. 614-633.

5. Challeges in bridging plan-synthesis paradigms. S. Kambhampati. Proc. IJCAI, 1997. To appear..

6. Why does Graphplan work? S. Kambhampati and E. Lambrecht. To be presented as a poster at IJCAI-97.

7. Process planner's assistant: An interactive and Iterative approach to automating process planning. X. Li, S. Kambhampati and J. Shah. ASME Design for Manufacturing workshop. 1997.

8. Formalizing dependency directed backtracking and explanation based learning in refinement search. S. Kambhampati. Proc. National Conference on AI, Portland, OR, pp. 757-762.

9. Design and Implementation of a replay framework based on a partial order planner. L. Ihrig (Ph.D. student) and S. Kambhampati. Proc. National Conference on AI, Portland, OR, pp. 849-854.

10. Refinement planning: Status and Prospectus. S. Kambhampati. Proc. National Conference on AI, Portland, OR,.

11. On the role of disjunctive representations and constraint propagation in refinement planning. S. Kambhampati and X. Yang (Formerly ASU Ph.D. student). Proc. 5th Intl. Conference on Knowledge Representation and Reasoning. 1996. Pp. 135-147. .

12. A candidate-set based analysis of subgoal interactions in conjunctive goal planning. S. Kambhampati, L. Ihrig (Ph.D. student) and B. Srivastava (M.S. Student), Proc. 3rd AI Planning Systems Conference. 1996. Pp. 125-133.

13. Unifying Classical Planning Approaches. S. Kambhampati and B. Srivastava. ASU CSE TR-96-006. (Submitted to Artificial Intelligence ). 55 pages.

14. On the relations between Dependency Directed Backtracking and Explanation based learning in planning and constraint satisfaction. S. Kambhampati. Submitted to Journal of Artificial Intelligence. Revised version re-submitted.

15. Synthesizing customized planners from specifications. B. Srivastava and S. Kambhampati. ASU CSE TR 96-014. Submitted to Journal of AI Research. Revised version under review.

16. Design and Implementation of a replay framework based on a partial order planner. L. Ihrig and S. Kambhampati. Submitted to Journal of AI research. Revised version under review

17. Admissible pruning strategies based on plan-minimality for plan space planning. S. Kambhampati. Submitted to Journal of AI Research. 1996.

18. Design and Implementation of a derivational replay framework for partial order planning. L. Ihrig. Ph.D. Dissertation. Defended, May 1996. Arizona State University.

19. Planning for Information Gathering: A tutorial Survey. E. Lambrecht and S. Kambhampati. ASU CSE Technical Report (in preparation).

DATE PREPARED: 13 May 97

'97 Quad Chart

- Back to Top -

- Home - About Kestrel - Research Staff - Current Projects - Project Archive -
- Publications - Technology Transfer - Career Opportunities - Contact Kestrel -