The problems of control synthesis, scheduling and planning may be formalised as games between a system (player) and an environment (adversary): The player may influence the adversary by taking choices based on his knowledge of the current state and vice versa. The goal for the player is to keep the environment within a desired range of states (or dually to steer it towards a desired type of state) by making the right choices following a winning (or optimal) strategy. Depending on the setting, algorithms for synthesising control strategies and schedules for finite state or real time systems and planning problems are known. In practice however, environments with large state spaces make such a synthesis hopelessly difficult.

In this task the consortium will attack the algorithmic aspects of controller synthesis and planning including approaches that prefer a simpler sub-optimal strategy over an optimal one. Modification and extension of heuristic methods from model checking and operations research will be investigated to allow for transfer to (optimal) control synthesis and to the closely related domain of online scheduling problems.

In analysing timed automata models obtained from PDDL+ domain descriptions, the consortium expects to benefit from static analysis of the PDDL+ source in obtaining information about independencies and mutual exclusions between action-instances. A specific structural property of timed automata models of job shop scheduling problems is that they are acyclic. This reduces their complexity and provides for specialised algorithms for analysis and synthesis including heuristic forward search, especially in the context of optimisation.

responsible partner: VERIMAG