Distributed extended beam search for quantitative model checking

A.J. Wijs, B. Lisser

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

9 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelProceedings of the 4th Workshop on Model Checking and Artificial Intelligence
RedacteurenS. Edelkamp, A. Lomuscio
Plaats van productieHeidelberg
UitgeverijSpringer
Pagina's166-184
ISBN van geprinte versie978-3-540-74128-2
DOI's
StatusGepubliceerd - 2006

Publicatie series

NaamLecture Notes in Artificial Intelligence
Volume4428
ISSN van geprinte versie1611-3349

Vingerafdruk Duik in de onderzoeksthema's van 'Distributed extended beam search for quantitative model checking'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Wijs, A. J., & Lisser, B. (2006). Distributed extended beam search for quantitative model checking. In S. Edelkamp, & A. Lomuscio (editors), Proceedings of the 4th Workshop on Model Checking and Artificial Intelligence (blz. 166-184). (Lecture Notes in Artificial Intelligence; Vol. 4428). Springer. https://doi.org/10.1007/978-3-540-74128-2_11