Last issue
2020 (vol. 30) - Number 4

A.B. Malinowska, R. Kamocki, R. Almeida, T. Odzijewicz:

On the existence of optimal consensus control for the fractional Cucker--Smale model

R. Grymin, W. Bożejko, J. Pempera, M. Wodecki, Z. Chaczko:

Algorithm for solving the Discrete-Continuous Inspection Problem

T. Kaczorek, A. Ruszewski:

Global stability of discrete-time nonlinear systems with descriptor standard and fractional positive linear parts and scalar feedbacks

R. Arora, K. Gupta:

Fuzzy goal programming technique for multi-objective indefinite quadratic bilevel programming problem

P. Nowak, J. Czeczot, P. Grelewicz:

Tuning rules for industrial use of the second-order Reduced Active Disturbance Rejection Controller

M.I. Gomoyunov:

Optimal control problems with a fixed terminal time in linear fractional-order systems

Muhafzan, A. Nazra, L. Yulianti, Zulakmal, R. Revina:

On LQ optimization problem subject to fractional order irregular singular systems

M. Blizorukova, V. Maksimov:

On one algorithm for reconstruction of an disturbance in a linear system of ordinary differential equations

ACS Abstract:

2008 (Volume 18)
Number 2
1. Constraint satisfaction techniques in planning and scheduling: An introduction
2. Filtering algorithms for the unary resource constraint
3. Modification strategies for SAT-based plan adaptation
4. Unifying planning and scheduling as timelines in a component-based perspective

Constraint satisfaction techniques in planning and scheduling: An introductionDownload full PDF article
R. Bartak
(Charles University, Czech Republic)

Planning and scheduling are two closely related areas that, despite their similarity, deal with different problems. While the planning ask is to decide which actions are necessary to achieve a given goal, the scheduling task is to allocate known activities to scarce resources, such as machines, over time. Typically planning and scheduling problems are solved separately using different solving techniques. However, real-life problems require a more integrated approach. Constraint satisfaction seems to be such a unifying solving technology for both planning and scheduling problems. This paper describes how constraint satisfaction techniques can be applied to planning and scheduling problems.

keywords: constraint satisfaction, problem modeling, planning, scheduling


Filtering algorithms for the unary resource constraintDownload full PDF article
P. Vilim
(ILOG S.A., Gentilly Cedex, France)

Scheduling is one of the most successful application areas of constraint programming mainly due to special   global constraints designed to model resource restrictions. Among scheduling constraints, the most useful and most studied constraint is probably the unary resource constraint. This paper presents state-of-the-art filtering algorithms for this important constraint. These algorithms are very fast (almost all of them has time complexity O(n log n) and furthermore they are able to take into account so called optional activities, that is, activities which may or may not appear in the schedule depending for example on a resolution of an alternative processing rule(s). In particular, this paper presents the following algorithms: overload checking, edge finding, not-first/not-last, detectable precedences and precedence energy.

keywords: constraint programming, scheduling, optional activities, unary resource, filtering algorithms


Modification strategies for SAT-based plan adaptationDownload full PDF article
R. van der Krogt
(Cork Constraint Computation Centre, University College Cork, Ireland)

Planning, the generation of a course of action to achieve a set of goals, is an important technique in the development of intelligent agents. Heretofore, planning has been largely considered as a one-shot problem. However, in practice, we are often dealing with situations in which an existing plan has to be adapted. Not only might we be facing a dynamic environment that requires a plan to be repaired, but it may also be that we recognize the new planning problem as being similar to one that we have solved before (i.e. case-based planning).
This paper investigates a plan adaptation framework based on SAT-encodings of the planning problem. Compilation techniques have been very successfully applied to planning, as evidenced by their success in recent planning competitions. So far, however, such techniques have not been used for plan adaptation purposes. This paper explores whether it is feasible to modify the generated SAT instances such as to encode information that was extracted from the solution to the original planning problem.

keywords: plan repair, planning as satisfiability


Unifying planning and scheduling as timelines in a component-based perspectiveDownload full PDF article
F. Pecora
(AASS Mobile Robotics Lab, Orebro University, Sweden)
S. Fratini
(ISTC-CNR,National Research Council of Italy)
A. Cesta
(ISTC-CNR,National Research Council of Italy)

The timeline-based approach to planning represents an effective alternative to classical planning for complex domains requiring the use of both temporal reasoning and scheduling features. This paper discusses the constraint-based approach to timeline planning and scheduling introduced in OMPS.  OMPS is a an architecture for problem solving which draws inspiration from both control theory and constraint-based reasoning, and which is based on the notion of components.
The rationale behind the component-based approach shares with classical control theory a basic modeling perspective: the planning and scheduling problem is represented by identifying a set of relevant domain components which need to be controlled to obtain a desired temporal behavior for the entire system. Components are entities whose properties may vary in time and which model one or more physical (or logical) domain subsystems relevant to a given planning context. The planner/scheduler plays the role of the controller for these entities, and reasons in terms of constraints that bound their internal evolutions and the desired properties of the generated behaviors (goals).
Our work complements this modeling assumption with a constraint-based computational framework.  Admissible temporal behaviors of components are specified as a set of causal constraints within a rich temporal specification, and goals are specified as temporal constraint preferences.  The OMPS software architecture presented in this paper combines both specific and generic constraint solvers in defining consistent timelines which satisfy a given set of goals.

keywords: planning, scheduling, timelines


<< Back