Computational Complexity of some Optimization Problems in Planning
Meysam Aghighi
май 2017 · Linköping Studies in Science and Technology. Dissertations Кніга 76 · Linköping University Electronic Press
Электронная кніга
35
Старонкі
reportАцэнкі і водгукі не спраўджаны Даведацца больш
Пра гэту электронную кнігу
Automated planning is known to be computationally hard in the general case. Propositional planning is PSPACE-complete and first-order planning is undecidable. One method for analyzing the computational complexity of planning is to study restricted subsets of planning instances, with the aim of differentiating instances with varying complexity. We use this methodology for studying the computational complexity of planning. Finding new tractable (i.e. polynomial-time solvable) problems has been a particularly important goal for researchers in the area. The reason behind this is not only to differentiate between easy and hard planning instances, but also to use polynomial-time solvable instances in order to construct better heuristic functions and improve planners. We identify a new class of tractable cost-optimal planning instances by restricting the causal graph. We study the computational complexity of oversubscription planning (such as the net-benefit problem) under various restrictions and reveal strong connections with classical planning. Inspired by this, we present a method for compiling oversubscription planning problems into the ordinary plan existence problem. We further study the parameterized complexity of cost-optimal and net-benefit planning under the same restrictions and show that the choice of numeric domain for the action costs has a great impact on the parameterized complexity. We finally consider the parameterized complexity of certain problems related to partial-order planning. In some applications, less restricted plans than total-order plans are needed. Therefore, a partial-order plan is being used instead. When dealing with partial-order plans, one important question is how to achieve optimal partial order plans, i.e. having the highest degree of freedom according to some notion of flexibility. We study several optimization problems for partial-order plans, such as finding a minimum deordering or reordering, and finding the minimum parallel execution length.
Ацаніце гэту электронную кнігу
Падзяліцеся сваімі меркаваннямі.
Чытанне інфармацыb
Смартфоны і планшэты
Усталюйце праграму "Кнігі Google Play" для Android і iPad/iPhone. Яна аўтаматычна сінхранізуецца з вашым уліковым запісам і дазваляе чытаць у інтэрнэце або па-за сеткай, дзе б вы ні былі.
Ноўтбукі і камп’ютары
У вэб-браўзеры камп’ютара можна слухаць аўдыякнігі, купленыя ў Google Play.
Электронныя кнiгi i iншыя прылады
Каб чытаць на такіх прыладах для электронных кніг, як, напрыклад, Kobo, трэба спампаваць файл і перанесці яго на сваю прыладу. Выканайце падрабязныя інструкцыі, прыведзеныя ў Даведачным цэнтры, каб перанесці файлы на прылады, якія падтрымліваюцца.
