Vlahavas I.1, Refanidis I.2 (Area Editors)
1Aristotle University, Dept. of Applied Informatics, Thessaloniki
2University of Macedonia, Dept. of Applied Informatics, Thessaloniki

TABLE OF CONTENTS

1. INTRODUCTION

2. CLASSICAL PLANNING

3. RESOURCE PLANNING AND SCHEDULING

4. MULTI-AGENT PLANNING

5. KNOWLEDGE ENGINEERING IN PLANNING

6. APPLICATIONS OF PLANNING AND SCHEDULING

7. CLOSURE & REMARKS

 

 

1. INTRODUCTION

Automated planning and scheduling is a branch of artificial intelligence that is concerned with the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles . Unlike classical control and classification problems, the solutions are complex and have to be discovered and optimized in multidimensional space.
In static and deterministic environments that can be easily modeled, automated planning can be performed offline. Solutions can be found and evaluated prior to execution. However, in unknown, dynamic and non-deterministic environments, the strategy often needs to be revised online. Models and policies need to be adapted. Solutions usually resort to iterative trial and error processes commonly seen in artificial intelligence. These include dynamic programming, reinforcement learning and combinatorial optimization.

A typical planner takes three inputs: a description of the initial state of the world, a description of the desired goals, and a set of actions that the executor is able to perform, all encoded in a formal language such as PDDL. The planner produces a (potentially partially ordered) set of actions that leads from the initial state to a state satisfying the goals. An alternative language for describing planning problems is that of hierarchical task networks, in which a set of tasks is given, and each task can be either realized by a primitive action or decomposed in a set of other tasks.
In its general form automated planning is an NP-Complete problem. Many approaches in the past have made various assumptions in order to make the problem tractable. For instance, the STRIPS planning system assumed the world to be static, closed, deterministic, completely observable by the agent and several others. Most of the assumptions made by STRIPS have also been adopted by most of the posterior classical planning systems. Some popular techniques include: forward chaining and backward chaining state-space search, possibly enhanced by the use of relationships among conditions (e.g. Graphplan) or heuristics synthesized from the problem, search through plan space, and translation to propositional satisfiability.
If the assumption of determinism is dropped and a probabilistic model of uncertainty is adopted, then this leads to the problem of policy generation for a Markov decision process (MDP) or (in the general case) partially observable Markov decision process (POMDP).
In the following we present the main contributions by Greek researchers and research teams in the general area of planning and scheduling. We adopt the overall taxonomy of planning and scheduling used in ‎[7].

2. CLASSICAL PLANNING

Classical planning refers generally to planning for restricted state-transition systems. Actions are considered instantaneous and deterministic, whereas the environment is static and fully observable; so planning can be performed off-line and execution is guaranteed to succeed. Despite its restrictive and unrealistic nature, significant research efforts have been devoted worldwide to classical planning, giving rise to powerful algorithms which subsequently were adapted to more realistic settings.

There are a variety of algorithms coping with the problem of classical planning. Roughly speaking, they fall into four main categories: state-space planning, plan-space planning, graph-based planning and satisfiability algorithms.
The Logic Programming and Intelligent Systems (LPIS) research group at the Department of Informatics of Aristotle University of Thessaloniki, headed by Prof. Ioannis Vlahavas, is active in this area over the last 10 years. The outcomes of this effort so far can be summarized in two PhD degrees awarded to Ioannis Refanidis ‎[15] and Dimitris Vrakas ‎[31], one edited volume ‎[27] and approximately 50 papers in conferences and journals.
Initial research focused on domain-independent heuristic state-space planning, which resulted in a variety of planning systems (GRT, MO-GRT , AcE, BP and HAPRC) and the participation to the 2nd International Planning Competition (2000).
GRT (‎[17]) is a heuristic state-space planner that constructs its heuristic function in a domain-independent way. The planner achieves significant performance in many domains as it has been shown in the 2nd international planning competition. An extension to the basic planning system uses XOR-constraints, in order to analyze a planning problem in a sequence of easier sub-problems that have to be solved sequentially ‎[14].
MO-GRT(‎[16]) is an extension of the GRT planner, with the ability to construct a multi-objective heuristic function in a domain independent way. Criteria, their scales and preferences among them are provided by the user. The planner compensates plan quality and solution time, depending on the criteria weights.
AcE (‎[28]) is a domain independent state space planner that utilizes a heuristic based on action evaluation. The heuristic obtains estimates for the cost of applying each action of the domain by performing a forward search in a relaxed version of the initial problem. The estimates for the actions are then utilized in a backward search on the original problem.

BP (‎[30]) is a bi-directional state space planning system, that is based on a hybrid search strategy and simple domain independent heuristic functions. The hybrid search strategy embodies two search threads whose execution is dynamically interleaved.
HAPRC (‎[33]) is a planning system which automatically fine-tunes its planning parameters according to the morphology of the problem in hand, through a combination of planning, machine learning and knowledge-based techniques. The adaptation is guided by a rule-based system that sets planner configuration parameters based on measurable characteristics of the problem instance. The knowledge of the rule system has been acquired off-line through a rule induction algorithm.
The main idea behind these planning systems was to analyze the planning problem in a pre-processing phase, thus computing informative (although inadmissible) heuristics that have been proved powerful in the subsequent search phase. An alternative idea was to parallelize part of the planning process, especially that of computing the heuristic values for the various nodes, resulting in significant acceleration of the overall planning process ‎[32].
LPIS group participated actively in the PLANET European Network of Excellence , whereas it hosted the 2nd International Summer School on Planning, which took place in September 2002 , in Halkidiki. Furthermore, Ioannis Refanidis (now at University of Macedonia) chairs the 6th International Planning Competition, which will take place in Sydney, 2008 , as well as the 19th International Conference on Automated Planning and Scheduling, which will take place in Thessaloniki, in September of 2009 .

Research at the University of Cyprus focused in the last years on the application of linear and mixed-integer programming techniques to planning problems. More specifically, [5] presents an improved Integer Programming formulation of planning along with ideas on how the linear relaxation of this formulation can be used in heuristic search. Moreover, the University of Cyprus participated in the organization of the Deterministic Track of the 5th International Planning Competition [6].

3. RESOURCE PLANNING AND SCHEDULING

Resource planning and scheduling concerns the augmentation of planning systems with abilities to handle real world aspects, such as actions with (deterministic or probabilistic) durations and resources. Usually such problems are solved in two phases: In the first phase a plan is constructed using classical planning algorithms, whereas in the second phase scheduling algorithms are employed in order to find the minimum plan makespan. In case of resources, the scheduling problem becomes more complicated, whereas the objective might be to minimize some combination of makespan and resource consumption. Approaches that integrate the planning and scheduling phase can also be considered.

3.1 TEMPORAL PLANNING AND SCHEDULING

Algorithms on temporal planning do not take into account resources, whereas their objective is simply to minimize the plan's makespan. Most of the algorithms for temporal planning search in the plan-space and utilize constraint propagation algorithms to compute the time windows of the tasks.

Preliminary work on temporal planning and scheduling has conducted at the Department of Applied Informatics of University of Macedonia. This work exploits a temporal planning graph in order to extract additional disjunctive constraints over the problem's variables, based on both permanent and temporary mutex relations, which are subsequently used by a CSP solver, in order to solve the temporal dimension of the planning problem ‎[20].
Part of the work at the University of Cyprus was concerned with the problem of applying Mixed Integer Programming techniques to temporal planning. The particular Mixed Integer Programming formulation of [3], models a planning problem by two sets of linear inequalities. The first set involves integer variables and is a Graphplan-like encoding where the duration of the actions is ignored. The second set involves both integer and real valued variables, and models the temporal aspects of the problem. The two sets interact through their common integer variables.

3.2. PLANNING AND EXECUTION

In classical temporal or atemporal planning the effects and the timing of the actions can be completely determined by the execution agent. In such settings, where there is no uncertainty about the timing of the events, each action can be scheduled in advance of execution. In more realistic settings however, the duration of some events (typically the duration of the actions) are not in the direct control of the agent; these are called uncontrollable events. In these cases, first an agent needs to know that correct execution is guaranteed for all expected timings of the uncontrollable events (often called the consistency checking problem). Second, it needs to know when to execute the next action so that the probability of correct execution is maximized (called the dispatch problem).
As part of his masters and Ph.D. thesis, Prof. Ioannis Tsamardinos and colleagues developed algorithms for efficient execution of temporal plans encoded as Simple Temporal Problems that solve the dispatch problem optimally ‎[23]‎[11]. Simple Temporal Problems allow the specification of plans with convex temporal constraints. These allow polynomial times for consistency and dispatch to be achieved but restrict significantly the type of temporal plans that can be represented. In subsequent work a temporal constraint-satisfaction solver for more expressive plans using disjunctive constraints (called Disjunctive Temporal Problems) was built, called Epilitis ‎[21]. Epilitis could solve the consistency problem for such plans while at the time being the most efficient solver of its kind. Execution algorithms solving the dispatch problem for plans encoded as Disjunctive Temporal Problems were presented at ‎[24]. The semantics of temporal plans to incorporate a probabilistic interpretation to the consistency and dispatch problems were extended in ‎[22].

The above work assumed that the only type uncertainty during execution regarded the occurrence of the uncontrollable events. A different type of uncertainty is causal uncertainty where depending on agent’s observations during execution, she may decide to take one course of action or another. A formalism that can encode this type of information, including both constraints about the timing of events plus possible agent’s choices for action was developed. Algorithms for solving the consistency problem and guarantee that there is a way to execute the plan under all possible observations were presented in ‎[25]‎[26].
The above theory, formalism and algorithms were employed in Autominder ‎[12], a robotic-based cognitive orthotic system that aids elderly people with cognitive disabilities in their daily activities; in addition, they were applied in workflow management systems and theory ‎[2].

4. MULTI-AGENT PLANNING

The work of the University of Cyprus in Multi-agent Planning described in [4], presents algorithms for the problems of coordination and cooperation between agents that are based on an underlying classical planner which is used by the agents to generate their individual plans, but also to find plans that are consistent with those of the other agents. The procedures are able to generate plans of optimal length.

5. KNOWLEDGE ENGINEERING IN PLANNING

Knowledge Enginnering in AI Planning is the process that deals with the acquisition, validation and maintenance of planning domain models, and the selection and optimization of appropriate planning machinery to work on them. Hence, knowledge engineering processes support the planning process: they comprise all of the off-line, knowledge-based aspects of planning that are to do with the application being built, and any on-line processes that cause changes in the planner’s domain model (‎[1]).
Research at the Department of Informatics at the Aristotle University of Thessaloniki in the last years focused on developing visual programming languages and user-friendly environments for the visualization and definition of planning domains and problems. The outcomes of the research can be summarized in two systems, namely ViTAPlan (‎[29]) and VLEPPO(‎[9]). The above systems offer the user an integrated environment for visualizing, designing, checking and solving planning domains and problems. They offer the user a visual programming module that enables him to encode new planning problems just by using visual elements and simple mouse operations. The visual tool performs a validity check on the visual program created by the user and then compiles it to PDDL files that are either solved by one of the embedded planning systems or send to an appropriate web service in order to obtain the solution. ViTAPlan also embodies a monitoring model that simulates the execution of the acquired solution (plan) and enables the expert user to discover dependencies in the plan’s steps and experiment with alternative plans.

6. APPLICATIONS OF PLANNING AND SCHEDULING

Research at the Department of Applied Informatics of University of Macedonia in the last years focused on the problem of scheduling personal tasks that appear in a user's calendar ‎[19]. Results of this research include an enhanced problem formulation, domain-dependent algorithms to solve the scheduling problem ‎[18], as well as an implemented web-accessible intelligent calendar application called SelfPlanner that allows the user to enter her tasks and preferences, solves the optimization problem and presents the resulting plan. SelfPlanner integrates with Google Calendar in order to present the plan, as well as with a Google Maps applications in order to specify location references and compute distances ‎[13].
Moreover the department of Informatics at the Aristotle University of Thessaloniki has investigated the application of AI Planning in e-Learning and composition of semantic web services resulting in two main systems, PASER and PORSCE. PASER (‎[10]) is a system for automatically synthesizing curricula using AI Planning and Semantic Web technologies. The use of classical planning techniques allows the system to dynamically construct learning paths even from disjoint learning objects, meeting the learner’s profile, preferences, needs and abilities. PORSCE (‎[8]) is a system combining an object ranking algorithm and a domain independent planning system in order to semantically search the space of possible compositions of Web services, generating plans according to the desirable level of relaxation set by the user.

7. CLOSURE & REMARKS

Research in planning and scheduling in Greece is an active area, with many researchers and research teams developing new algorithms and several applications based on planning and scheduling technology being deployed.
An important landmark for the Greek planning and scheduling community is the organization of the 19th International Conference on Automated Planning and Scheduling that will take place in September 2009, in Thessaloniki and will be chaired by Ioannis Refanidis. This will be an opportunity for the broader Greek AI community to have a touch with the latest achievements in planning and scheduling technology, as well as with the most prominent researchers worldwide, thus exchanging ideas and establish relationships.

 


 

REFERENCES

  1. Aler R., Borrajo D., Haslum P., Garagnani M., Jarvis P. and McCluskey T.L., Knowledge Engineering for Planning ROADMAP. PLANET Network of Excellence. 2003.
  2. Berfield A., Chrysanthis P.K., Tsamardinos I., Pollack M.E. and Banerjee S.,A Scheme for Integrating e-Services in Establishing Virtual Enterprises, 12th International Workshop on Research Issues on Data Engineering (RIDE-02) .
  3. Dimopoulos Y. and Gerevini A., “Temporal Planning through Mixed Integer Programming: a preliminary report”, 8th International Conference on the Principles and Practice of Constraint Programming, CP-02, NY, USA, September 2002, pages 47-62, LNCS 2470, Springer.
  4. Dimopoulos Y. and Moraitis P.. Multi-Agent Coordination and Cooperation through Classical Planning, IEEE/WIC/ACM Int. Conf. on Intelligent Agent Technology, (IAT 2006), Hong-Kong, 2006, IEEE Press.
  5. Dimopoulos Y., “Improved Integer Programs and Heuristic Search for AI Planning”, Sixth European Conference on Planning, ECP'01 , September 2001, Spain, LNCS, Springer.
  6. Dimopoulos Y., Gerevini A., Haslum P. and Saetti A., The Benchmark Domains of the Deterministic Part of IPC-5, Booklet of the 2006 Planning Competition, ICAPS'06, Lake District, UK, 2006.
  7. Ghallab M., Nau D., and Traverso P., Automated Planning, theory and practice. Morgan Kaufmann, 2004.
  8. Hatzi O., Meditskos G., Vrakas D., Bassiliades N., Anagnostopoulos D. and Vlahavas I., “A Synergy of Planning and Ontology Concept Ranking for Semantic Web Service Composition”, Proc. Of the 11th Ibero-American Conference on Artificial Intelligence, Lisbon Portugal, 2008.
  9. Hatzi, O., Vrakas D., Bassiliades N., Anagnostopoulos D. and Vlahavas I., “VLEPpO: A Visual Language for Problem Representation”, 26th Workshop of the UK Planning and Scheduling Special Interest Group, Roman Bartak (Ed.), pp. 60 - 66, Prague, Czech Republic, 2007.
  1. Kontopoulos E., Vrakas D., Kokkoras F., Bassiliades N. and Vlahavas I., “An Ontology-based Planning System for e-Course Generation”, Expert Systems with Applications, Elsevier, 35 (1-2), pp. 398-406, 2008.
  2. Muscettola N., Morris P. and Tsamardinos I., “eformulation of Temporal Plans for Efficient Execution, in Proceedings of the 6th Conference Principles of Knowledge Representation and Reasoning (KR) 1998, pp444-452.
  3. Pollack M.E., Brown L., Colbry D., McCarthy C.E., Orosz C., Peintner B., Ramakrishnan S. and Tsamardinos I., Autominder: An Intelligent Cognitive Orthotic System for People with Memory Impairment, Robotics and Autonomous Systems, 44(3-4):273-282, 2003.
  4. Refanidis I. and Alexiadis A., SelfPlanner: A Intelligent Web-based Calendar Application. Presented at the demo session of the 17th International Conference on Automated Planning and Scheduling Systems (ICAPS-07), Providence, Rhode Island, US, September 2007.
  5. Refanidis I. and Vlahavas I., Exploiting State Constraints in Heuristic State-Space Planning, 5th International Conference on Artificial Intelligence Planning and Scheduling Systems (AIPS-2000), Breckenridge, Colorado, USA, April 2000
  6. Refanidis I., “Heuristic State Space Planning”, PhD dissertation , Dept. of Informatics, Aristotle University of Thessaloniki, 2001
  7. Refanidis I., and Vlahavas I., Multiobjective Heuristic State-Space Planning, Artificial Intelligence Journal, vol 145/1-2 pp 1 – 32, 2003.
  8. Refanidis I., and Vlahavas I., The GRT Planner: Backward Heuristic Construction in Forward State-Space Planning, Journal of Artificial Intelligence Research, 15 (2001), pp. 115-161
  9. Refanidis I., Managing Personal Tasks with Time Constraints and Preferences. 17th International Conference on Automated Planning and Scheduling Systems (ICAPS-07), Providence, Rhode Island, US, September 2007. AAAI Press.
  10. Refanidis I., McCluskey T.L. and Dimopoulos Y., Planning Services for Individuals: A New Challenge for the Planning Community. ICAPS-04 Workshop on Connecting Planning Theory with Practice, Whistler, British Columbia, Canada, 2004.
  11. Refanidis I., Stratified heuristic POCL temporal planning based on planning graphs and constraint programming. ICAPS-05 Workshop on Constraint Programming for Planning and Scheduling, Monterey, California, 2005.
  12. Tsamardinos I. and Pollack M.E., “Efficient Solution Techniques for Disjunctive Temporal Reasoning Problems,” in Artificial Intelligence, 151(1-2), pp 43-89, 2003
  13. Tsamardinos I., A Probabilistic Approach to Robust Execution of Temporal Plans with Uncertainty, Proceedings of the 2nd Greek National Conference on Artificial Intelligence, Thessaloniki, Greece, April 2002, p. 97-108.
  14. Tsamardinos I., Muscettola N. and Morris P., Fast Transformation of Temporal Plans for Efficient Execution, in Proceedings of the 15th National Conference on Artificial Intelligence (AAAI’98), pp254-261.
  15. Tsamardinos I., Pollack M. and Ganchev P., Flexible Dispatch of Disjunctive Temporal Plans, in Proceedings of Sixth European Conference on Planning 2001 (ECP-01), Toledo, Spain, pp. 417—422.
  16. Tsamardinos I., Pollack M.E. and Horty J.F.,Merging Plans with Quantitative Temporal Constraints, Temporally Extended Actions, and Conditional Branches, Proceedings of the 5th International Conference on AI Planning and Scheduling (AIPS 2000), Breckenridge, CO, April, 2000, pp264-272. Winner of the Outstanding Student Paper Award.
  1. Tsamardinos I., Vidal T. and Pollack M.E., CTP: A New Constraint-Based Formalism for Conditional, Temporal Planning, in Special Issue on Planning of Constraints Journal, 8:4 October 2003, p. 365-388.
  2. Vlahavas I. and Vrakas D., “Intelligent Techniques for Planning”, Idea Group Publishing, 2005
  3. Vrakas D. and Vlahavas I., “A Heuristic for Planning based on Action Evaluation”, Proc. 10th International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA '02), Springer-Verlag, LNAI 2443, pp. 61-70, 2002.
  4. Vrakas D. and Vlahavas I., “A Visualization Environment for Planning”, International Journal on Artificial Intelligence Tools”, Vol. 14 (6), pp. 975-998, World Scientific, 2005.
  5. Vrakas D. and Vlahavas I., “Combining Progression and Regression in State-Space Heuristic Planning”, Proc. 6th European Conference on Planning (ECP '01), 2001.
  6. Vrakas D., “Intelligent Planning Systems”, PhD dissertation , Dept. of Informatics, Aristotle University of Thessaloniki, 2004
  7. Vrakas D., Refanidis I. and Vlahavas I., "Parallel Planning via the Distribution of Operators", Journal of Experimental and Theoretical Artificial Intelligence, 2001.
  8. Vrakas D., Tsoumakas G., Bassiliades N. and Vlahavas I., “HAPrc: An Automatically Configurable Planning System”, AI Communications, 18 (1), pp. 1-20, 2005.