TY - GEN

T1 - Distributed extended beam search for quantitative model checking

AU - Wijs, A.J.

AU - Lisser, B.

PY - 2006

Y1 - 2006

N2 - In this paper, we mainly focus on solving scheduling problems with model checking, where a finite number of entities needs to be processed as efficiently as possible, for instance by a machine. To solve these problems, we model them in untimed process algebra, where time is modelled using a special tick action. We propose a set of distributed state space explorations to find schedules for the modelled problems, building on the traditional notion of beam search. The basic approach is called distributed (detailed) beam search, which prunes parts of the state space while searching using an evaluation function in order to find near-optimal schedules in very large state spaces. Variations on this approach are presented, such as distributed flexible, distributed g-synchronised, and distributed priority beam search, which can also practically be used in combinations.

AB - In this paper, we mainly focus on solving scheduling problems with model checking, where a finite number of entities needs to be processed as efficiently as possible, for instance by a machine. To solve these problems, we model them in untimed process algebra, where time is modelled using a special tick action. We propose a set of distributed state space explorations to find schedules for the modelled problems, building on the traditional notion of beam search. The basic approach is called distributed (detailed) beam search, which prunes parts of the state space while searching using an evaluation function in order to find near-optimal schedules in very large state spaces. Variations on this approach are presented, such as distributed flexible, distributed g-synchronised, and distributed priority beam search, which can also practically be used in combinations.

U2 - 10.1007/978-3-540-74128-2_11

DO - 10.1007/978-3-540-74128-2_11

M3 - Conference contribution

SN - 978-3-540-74128-2

T3 - Lecture Notes in Artificial Intelligence

SP - 166

EP - 184

BT - Proceedings of the 4th Workshop on Model Checking and Artificial Intelligence

A2 - Edelkamp, S.

A2 - Lomuscio, A.

PB - Springer

CY - Heidelberg

ER -