PlanNet is an AI Planning architecture based on Constraint Satisfaction Techniques  aimed at supporting the (re)configuration management of a distributed network environments.

  
 
 

	INTRODUCTION
	THE ARCHITECTURE
	EXAMPLES
	A GUI For PlanNet
	PEOPLE
	RELATED PAPERS
	RELATED LINKS
	ACKNOWLEDGMENTS

 
 

Many modern systems allow automatic reconfiguration and repair mechanisms at the price of writing complex scripts, procedural applications, one for each situation that is likely to happen. This approach may still be acceptable for simple tasks, or when these tasks are routinely performed and the script is written once and forall by an application developer. The approach will no longer be acceptable when the way to achieve a goal depends on policies which are established on the fly by the administrator and are not entirely predictable at application development time. Therefore, not only does the procedural approach require long development time, but it's not even flexible enough to cope with unexpected situations. 

AI planning techniques represent a more flexible approach that overcomes those limits since they can provide some sort of automation in the script generation. This is a big step towards the automation of management tasks. 
A Planner is an Intelligent Agent which dynamically synthesises the sequence of actions (plan) necessary to achieve a desired state (goal) starting from a given initial state of the system. The basic actions used by the planner are defined by means of preconditions and post-conditions. Preconditions represent the conditions to be satisfied in the current state in order for that action to be executed. Post-conditions represent the effects the action causes on the world, so as to change its current state. Thus, given a domain of application, automated planning allows the system to achieve any goal, by synthesising the appropriate plan starting from a domain of basic actions. New actions can be added to this domain when any update of the system requires them, so to avoid rewriting complex procedural applications. 

Planning problems are represented by NP-complete search problems. Thus, the problem solution is represented by a point satisfying a set of constraints in a finite discrete space. Constraint Satisfaction (CS) techniques represent a successful paradigm widely used for solving such problems in order to reduce the search space so to improve the computational efficiency of the problem solving algorithm. The idea behind these techniques is an active use of constraints to a priori prune the search-tree branches that cannot lead to a consistent solution, thus avoiding many failures and consequent highly expensive backtracking steps.  CS techniques are often adopted for modelling and solving planning problems.  In order to do that, it is required to map the planning problem into a Constraint Satisfaction Problem (CSP). 

We have developed PlanNet: a planning architecture, which exploits Constraint Satisfaction (CS) techniques both to improve its computational efficiency and to deal with the problem of incomplete and changing knowledge.  One of the main simplifying assumptions traditional planners are based on is the hypothesis of closed and static world, i.e., the planners refer to a formal, static and complete description of the initial state of the world while they build the plan. In a networked computer system the amount of data to be considered is huge and continuously changing; thus, it is not trivial, if not even impossible, to load, translate in a formal language and update all the hierarchical knowledge describing the current situation. There is need for an information gathering mechanism in charge of dynamically acquiring necessary information during the planning process.  On the other hand, standard CS approaches need all the information on variable domains at the beginning of the computation. 

Thus, we extend the CSP framework in order to treat constraints on variables ranging on partially or completely unknown domains. Those constraints, called Interactive Constraints may result in a knowledge acquisition process and a consequent propagation. PlanNet has been implemented by using the finite domain library of the constraint logic programming language ECLiPSe properly extended to cope with the interactive model. 
 

• the Planner
• the Domain of Actions
• the Information Gathering Module
• the Executor

  

Given a final goal, the Planner (module 1 in Figure 1) synthesises the plan of necessary actions to achieve the goal by exploiting the set of actions (module 2) performable on the system modeled in a formal language. Moreover, during the planning process the planner can access the real system by means of the Information Gathering Module (module 3) in order to acquire information on the current system state. Once the plan is built the Planner calls the Executor (module 4) which will execute the ground actions corresponding to the modeled actions of the plan. 

  

The Planner   

Our planner is an integrated planner, based on Constraint Satisfaction (CS) techniques, which combines the problem solving ability of generative planning algorithms and the capability of reactive planning algorithm to interact with the real system. We have designed it as a block composed of two modules (see Figure 2): 
 

• a Generative Module
• a Reactive Module

 

 

 
The Generative Module 

The generative module (module 1a in Figure 2) is responsible of building the plan necessary to reach a desired state starting from the current state of the system. The two inputs of the 
algorithm are: 
 

Both goal and actions are represented in a formal language. So far we have been using a very simple language which consists in a slight extension of the propositional Strips representation. The acronym ``Strips'' stands for ``STanford Research Institute Problem Solver'' a very famous and influential planner built in the 1970s to control an unstable mobile robot known affectionately as ``Shakey''. The propositional Strips representation restricts the type of goal states that may be specified to those matching a conjunction of positive ground literals. In the Strips representation, actions are represented with preconditions and effects where preconditions follow the same restriction as the problem's goal: they are a conjunction of positive literals. An action's effect, on the other hand, is a conjunction that may include both positive and negative literals. For example, we might define the action move-C-from-A-to-Table as follows: Precondition: ((on C A) (clear C)) Effect: ((on C Table) (not (on C A)) (clear A)). We allow the planner to work with action schemata with variables; thus, conjuncts representing preconditions, effects and goals can be expressed as non ground (unary or binary) literals. Moreover, while Strips describes the initial state of world with a complete set of ground literals, as most of the traditional generative planners do, (i.e., they assume to have a complete and static knowledge of the current state of the system (Close World Assumption)), our planner dynamically acquires knowledge from the real system by exploiting the Interactive Constraint Satisfaction (ICSP) framework. The acquired knowledge is loaded in a knowledge base, called IS (see Figure 3). 
IS grows continuously during the planning process and it contains only information needed to build the plan. 
For more details see section "The Information Gathering Module". 

The plan search engine is a Partial Order Planner (POP) planning algorithm is a regressive non-linear planner performing least commitment planning. It is sound and complete for its actions representation meaning that the planner is always able to return a correct plan if such a plan exists. 

The planner treats preconditions and final goals as interactive constraints: as soon as it selects an open condition from the Agenda, it will put it into the constraint store handled by the constrain solver. More precisely, at each step, the planner, starting from the goal, tries to verify an open condition Q in the initial state by means of the associated Interactive Constraint. 

In case the constraint solver returns a failure, the planner searches for an action already in the plan or a new action containing an effect unifiable with Q. The algorithm ends when all preconditions are guaranteed to be satisfied in a consistent way with all the constraints of the plan. 
At the end of the planning process all the CSPs involved should have been successfully solved and all the action variables instantiated. If some variables are still non instantiated it means that constraint propagation has been not enough to deterministically reduce all the variable domains to one single value. Traditional CSPs perform a non deterministic labelling step in which some variables are instantiated to a still consistent values so that suspended constraints are awaked and the propagation goes on. This is an iterative process that ends when all the variables are instantiated to a consistent value. 

In our framework the CSPs representing the action variable binding activity are treated in a different way. Non instantiated variables are left unbound so as the output of the generative phase of the planning process will be a plan schema more than a completely instantiated sequence of actions. 

The reactive module (module 1b in Figure 2) will provide for its refinement. 
The reason of our choice is based on the consideration that solutions consistent for the generative planner can be inconsistent when executed in the real world, since we assume that the underlying system can dynamically change. 

The output of (module 1a} will be represented by a total ordered plan schemata as opposed to a total order sequence of actions completely instantiated which represents the solution found by a traditional planner. 
 

 

 
The Reactive Module 

The reactive module (module 1b in Figure 2) is devoted to verify, before execution, whether action preconditions are still true and, after action execution, whether action effects have been properly executed. The hypothesis of static world is another unrealistic assumption of traditional planners, since most real domains are typically highly dynamic. The problem of dynamic world is due to the facts that 
 

This can lead to a failure of the plan execution, either because action preconditions are no longer verified at execution time and the corresponding action cannot be successfully executed, or because action effects are not those expected because of a non deterministic behaviour of the system. We propose an hybrid planning architecture which combines a generative planner in charge of producing a set of alternative plans (see section above) and a reactive 
planner to refine the final plan and verify its execution. In order to realise the reactive module, we need: 
 

• a run-time precondition verification mechanism which checks whether action preconditions are still true at execution time (Plan Refinement Module in Figure 2)

• an effect verification mechanism able to check if the corresponding action has been properly executed; (Plan Refinement Module in Figure 2)

• an executable backtracking mechanism which allows to ``retract'' action effects when the real world situation does not correspond to the one expected by the planner; (Recovery Module in Figure 2) 

This can be realised by an interactive constraint propagation activity which checks the satisfiability of the precondition in the real world. 
Obviously, if precondition variables are already instantiated, the interaction with the underlying system returns a boolean value, while if those variables are associated with a domain, the domain can be pruned in order to remove values which are no longer consistent with the current state of the system. 

Thus the plan execution process result in a search process in order to find the totally instantiated actions before performing them on the real world. Note that while during the generative process the interactive constraints rely on the cache IS,  in this phase they only interact with the real system since the information collected in IS is assumed to be out of date. 

The effect verification mechanism checks if the corresponding action has been properly executed. For this purpose, again, the plan refinement module calls the constraint solver. There is need to associate with each action effect an interactive constraint so as to query the underlying system and check whether the action has achieved the desired effect. Note that in this case variables appearing in action effects are already ground and the effect verification results in a boolean value. Thus, the interaction with the real world results in a consistency checking more than proper knowledge acquisition which is computationally less complex. If the verification succeeds, the execution of the plan goes on by selecting the next action. Otherwise, the executor (module 4 in Figure 4) returns fail and a backtracking mechanism is performed by the recovery module iin order to select an alternative plan action instance. 

The repair mechanism supports the cases in which the planner, through IC-driven verification, realises that the effects of the action are not those expected. The planner has to support repair activity also for dealing with irreversible action execution (an irreversible action is an action whose effects are not backtrackable after execution). The problems of reactive planners are mostly related with backtracking of irreversible actions. We are currently studying how to provide the action domain with Backup actions to add to the plan during the first phase of the planning process each time an irreversible action is instantiated. Those actions are then used in charge of synthesising a recovery plan, at run time, in case of execution failure. Another solution 
could be to synthesise the recovery plans as conditional plans during the generative phase; then, they would be executed only whether the related action failed. The former solution makes the plan generation faster but, in case of failures, slows down the execution of the plan; the latter solution is, thus, advisable when the probabilities of failures is high. 
 

The Information Gathering Module   

The knowledge acquisition mechanism is transparent to the planner, meant as the box including both the plan search engine and the constraint solver. Each time there is need to prove a goal (i.e., open condition) in the initial state, the plan search engine calls the constraint solver, which is responsible for reporting about the state of the goal under consideration. The interactive constraint propagation activity results in a traditional constraint propagation or information retrieval activity according to the available variable domain knowledge. The propagation mechanism is transparent to the plan search engine. 

When domain information is not enough to standard propagation, the constraint solver queries an acquisition module (see Figure 3) which is responsible of providing the needed information either by inferring it from a knowledge base, in our case IS, or by retrieving it directly from the real world. 
 

The acquisition module acts as a proxy since it offers to the planner an interface to the real world and performs additional pre and post processing of the original data. We can think of the planner as a client responsible for a specific task, (i.e., constraint propagation and consequent precondition verification), and, in order to perform its task, it invokes the functionality of the original system indirectly by simply accessing the proxy. In this way, the planner doesn't have to change its syntax to query the system nor to worry about when there is need for a remote access and when the desired information has been already locally stored in a knowledge base. 

IS represents a cache more than a proper knowledge base since it contains only information ``on demand" necessary to build the plan. With respect to 
the proxy, it represents a data area that temporarily holds results so as to avoid redundant access to the real system. When a precondition is tested by means of interactive constraint propagation, in case the related knowledge has already been retrieved, the correspondent atomic formula should be inferred, by the proxy module, from the facts contained in IS. In order to speed up the inference mechanism, we decided to directly load the information in IS, in terms of binary predicates. Thus, the acquisition phase is extended with a translation phase so as to reduce the complexity of inference activity on this knowledge during further constraint propagation. It is worth to underline that IS is not static, but it grows continuously according to the new information retrieved by the acquisition module. IS has the aim to avoid sensor abuse, i.e., to reduce as much as possible the number of accesses of the proxy to the original system. To improve this mechanism and support universal and existential quantification on goal proving, we explicit the fact that IS already contains all the information regarding a specific resource by adding an all annotation to that item. This reasoning methodology is based on 
the Local Closed Word (LCW) assumption. 

Acquisition from the real world is performed by propagating an interactive constraint and it is guided by one of the two variables of the corresponding binary predicate. That variable domain needs to be completely or partially known; then, for each known domain value, all the related information - not only the information strictly regarding the predicate - is retrieved. 

In a distributed computer system based on a UNIX platform, the proxy queries the real world by means of UNIX sensing commands.  In order to test the planner on real examples we have interfaced the acquisition module with the original platform by means of low level function running as actual access modules 

 

The Executor   

The Executor (module 4 in Figure 2) is represented by a module able to interact with the low level system in order to execute the ground actions corresponding to the declarative actions of the plan produced by the generative planner and the recovery plans provided by the recovery module. 
Each time an action execution fails, the actual plan execution is interrupted and 4 waits for further directions by the recovery module. Vice versa 
when the recovery plan has been successfully executed the actual plan execution resumes from the failed action. 

• An example of disk management on an HPUX system 
• An example of process management
• An example of repair plan in the context of an Intrusion Detection System

• Rosy Barruffi
• Evelina Lamma
• Paola Mello
• Michela Milano
• Rebecca Montanari
• Paolo Torroni

• Internet Softbot
• O-Plan