SODA

Task Structure Abstraction

Lindblom, Simon and Aronsson, Martin and Kreuger, Per (2001) Task Structure Abstraction. [SICS Report]

[img]Postscript
111Kb
[img]
Preview
PDF
232Kb

Abstract

This paper explores the idea of using formalised abstraction as means of describing various operations on structured representations of planing, scheduling and resource allocation problems. We define a notion of structures on tasks, relations and resources. Each task consists of task parameters and an inductively defined substructure. The task parameters denote domain variables constrained by the relations of the structure while resources formalises resource constraints, typically presupposing the semantics of some global constraint. A notion of consistency of such structures is briefly outlined. We go on characterise properties of safeness and certain conservation properties on operations We claim that such properties are relevant to problem domains where tasks on several different types or levels of resources has to scheduled simultaneously or by partitioning the problem into several subproblems that has then to be coordinated. Finally we present, in some detail, a model of such a problem from the rail transport industry formalised as several task structures. We show how operations on these can be seen as solvers for the various subproblems but also used to transform a specification or a solution of one subproblem into a specification of an other one. We claim that properties of such operations can be used to characterise reasoning in coordination problems.

Item Type:SICS Report
Uncontrolled Keywords:Formal abstraction, task scheduling, resource management, hierarchical planning, approximate methods, problem coordination, constraint programming, formal models
ID Code:2387
Deposited By:Vicki Carleson
Deposited On:30 Jul 2009
Last Modified:18 Nov 2009 16:08

Repository Staff Only: item control page