|The complexity of networked computer systems is
rapidly increasing due to the vast number of machines from different
manufactures, widely distributed and connected by a variety of networking
technologies. The management workload grows along with the number of
computers interconnected and the relevant complex distributed applications
and tasks that need to be performed. Among the management activities that
get harder in this scenario, there's there is the configuration and
reconfiguration of the system.
Basically, to configure a system, means to perform actions on its components, thus, the more the complexity of the managed objects grows, the more the number of possible actions and their combinations and interaction increases.
The same considerations are valid in the case of repair activity in system security management. Recovery from a dangerous situation can be an inherently complex task, so that it might require a big deal of interaction with the system administrator for a step-to-step flow control of the repair process.
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
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.
|We have chosen a modular approach in order to design our architecture.
Four main modules need to be considered (see Figure 1):
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.
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):
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
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).
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.
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
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 (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
When variable domains contain more than one value a search process is performed at execution time, in order to choose, at run time, a (still) consistent
solution, if any, among the possible alternatives, i.e., we need to check, before executing an action, if its preconditions are still verified.
This can be realised by an interactive constraint propagation activity
which checks the satisfiability of the precondition in the real world.
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
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
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
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 (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.
|A GUI FOR PlanNet|
|A Graphical User Interface for PlanNet has been implemented in
Through the same GUI, the user can run stored goals or define new goals.
You can follow an example of interaction with the PlanNet GUI.
|A number of different papers on PlanNet and its applications can be found at Papers From Lia|
|This project is supported by Hewlett
Packard Laboratories of Bristol-UK (Extended Enterprise Laboratory).