 |
A Constraint-based Scheduler for Railway Traffic | |
|
An Object-Oriented Approach to Planning | |
|
PlanNet: A constraint-based PLANner for the NETwork |
 |
A Constraint-based Scheduler for Railway Traffic | |
|
General Description | |
| Scheduling deals with the allocation of resources to activities over
time,
by respecting precedence, duration, capacity and incompatibility
constraints, in order to achieve the optimal use of resources
or the optimal accomplishment of tasks.
Over the past decade, a large number of efforts have investigated and exploited Artificial Intelligence Techniques in facing scheduling problems. Scheduling problems arise in domains like manufacturing, transportation, computer processing, production planning and so on. In most of them, namely constraint-based approaches, constraint processing plays a central role. We have developed a constraint based scheduler for the railway traffic regulation and management. This task is currently handled by human experts who should take into account an enormous number of variables. Our scheduler analyzes a limited temporal interval and produces the correct schedule for the incoming trains. The results are very encouraging since the systems greatly overcome the performances of a human expert. The system has been first implemented for dealing only with railway stations. Later, it has been extended to cope with a railway line. The final system relies on a distributed architecture where different schedulers, each regulating a railway station, communicate and cooperate in order to achieve a solution, see InterSymp95 or AIENG96. A prototype of the system has been implemented by using the Constraint Logic Programming language ECLiPSe.
| ||
|
Current and Future Works | |
| ||
|
Keywords | |
| ||
|
Participants | |
|
Funded by | |
| ||
|
An Object-Oriented Approach to Planning | |
|
General Description | |
| The more recent trend in planning
is to build integrated architectures,
composed by a generative planner and a reactive planner,
meant to join the problem-solving abilities of
the former with the capability of execution and control in real
environments of the latter.
In these architectures, the generative planner is in charge to produce only a partial plan, which is refined and executed by the reactive planner. Thus, it is possible to face the problem of planning in domains where knowledge is partial or transient. Even though integrated architectures solve some of the traditional limits of generative and reactive approach to planning, many problems are still open. In particular, integrated architectures does not completely solve the problem of dealing with incomplete knowledge, because plan synthesis, even though partial, is based on a static knowledge base. A less debated problem, which we wall the hard-wired choice problem, concerns reactive planners: the coupling between coding plans and controlling their selection. This problem, that can be considered as a manifestation of the Qualification Problem, is related to the plan choice mechanism used by reactive planners: plan applicability is verified in the current world state. We propose an extended mechanism of plan selection allowing dynamic verification of preconditions that can be used by the generative component of an integrated architecture to approach the problem of incomplete knowledge, and by the reactive planner to solve the hard-wired choice problem. Our proposal is based on an Object-Oriented domain representation, and on object dynamic classification as a tool for plan selection and knowledge acquisition.
| ||
|
Keywords | |
| ||
|
Participants | |
| ||
|
Funded by | |
| ||
|
PlanNet: A constraint-based PLANner for the NETwork | |
|
General Description | |
| 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. One of the main management activity that become more difficult
in this scenario is the configuration and reconfiguration of the system.
Configure a system basically means to perform actions on its objects, 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 value for repair activity in system security management.
Recovery from a dangerous situation can be an inherently complex task,
so that it might require a lot 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 prize of writing complex scripts, procedural applications, one for each situation that is likely to happen. If this approach is still acceptable for simple tasks or when these tasks are routinely performed and the script is written once forever by an application developer, it will be acceptable no longer 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. Thus, not only the procedural approach requires long development time, but also it is not flexible enough to cope with unexpected situations. AI planning techniques represent a more flexible approach that overcomes those limits since it can provide some sort of automation in the script generation which is a big step towards the automation of management tasks. 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 assumption 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 no trivial, if not 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. | ||
|
Keywords | |
| ||
|
Participants | |
|
Funded by | |
| ||
 About this Server |
 DocMaster |
 LIA WebMaster |
|
| ||