Лекция 5 - 02.11.2010

страницата се нуждае от дописване/преглеждане


Планиране

Търсим последователност от действия, които да ни помогнат да достигнем дадени цели. Най-общо казано, имаме някаква цел, пространство от състояния и дадени действия - с тези неща трябва да изберем последователност от действия, с които да достигнем целта си. Класът задачи, които включват проблема за планирането, е доста широк.

Разглеждаме проблема от гледната точка на един интелигентен агент - какви трудности би срещнал той, изграждайки си план за действие? Целейки ефективност, агентът трябва да избере действия, които имат отношение към постигане на целта, да избере добра евристична функция, съобразявйки се със спецификата на проблема, и (много важно) да може да разбие (декомпозира) проблема на по-малки проблеми.

За да можем да решаваме задачи (проблеми) от този сорт, трябва да можем да ги формализираме. За целта са съставени езици, специално пригодени за описания на действията и състоянията, използвани при планирането. Един такъв език трябва да може да описва широк кръг проблеми, да бъде достатъчно рестриктивен, че да позволява ефективни алгоритми, и да бъде така структуриран, че да подпомага планиращия алгоритъм. Примери за такива езици са STRIPS и ADL.

Language features

Като цяло, важи предположението за "затворения" (ограничен) свят.

Представяне на състоянията

Езикът декомпозира света (универсума) до набор от логически условия и представя едно състояние като конюнкция на положителни литерали.

Представяне на целите

Целта се представя като конюнкция от условия. Целта е достигната, когато тази конюнкция е част от резултата от поредицата от действия.

Предстаявне на действията

Едно действие се състои от условия и ефекти.
Пример:

Action(Fly(p,from,to),
    PRECOND: At(p,from) ^ Plane(p) ^ Airport(from) ^ Airport(to),
    EFFECT: not(At(p,from)) ^ At(p,to))

На човешки език: предусловията гласят, че p е самолет, с който се лети от стартова точка from до крайна точка to, като from и to са летища. Ефектът от действието е, че самолетът се намира в to (и не се намира във from).

Семантика на езика: Когато предусловията за дадено действие са удовлетворени, то може да бъде приложено. Литералите, които са споменати в ефекта, се променят - останалите не.
[Изразителност и разширения в STRIPS - pdf]
Пример: превоз на стоки [pdf]. Имаме действия "товарене", "разтоварване", "летене". Имаме начално условие (инициализация), с описание на света, и цел, която се опитваме да достигнем. Планът се състои в последователност от позволени действия, достигащи до крайната цел.
Пример: резервна гума [pdf]. Този пример отива отвъд STRIPS и навлиза в ADL.

Планиране с търсене в пространство от състояния (планове)

Възможно е да подходим от двете страни на проблема: тръгваме от началното състояние и търсим последователност от действия, която достига до крайното, или тръгваме от крайното състояние и търсим действия, които биха довели от началното до крайното състояние - един вид reverse engineering1

Progression planners

Започваме от началното състояние и разглеждаме позволените действия. Стремим се да достигнем до състояние, което удовлетворява заложената цел. В процеса си строим търсещо дърво, отразяващо възможните пътеки на действие.
Алгоритъм: […]

Regression planners

Търсим действия, чийто ефект би довел до постигане на целта. Действията не трябва да премахват необходини ни състояния. Предимството на подхода е, че разглеждаме само действия, достигащи до целта - често се постига по-малко разклоняване на търсещото дърво.
Алгоритъм: Задаваме (описваме) цел G. За дадено действие A, което е релевантно (достига до целта) и консистентно (не нарушава дадени условия), определяме предшествениците:

  • Премахваме положителните ефекти, описани в A, от G;
  • Ако A включва някакви предусловия, неописани в G, ги добавяме.
  • Прекъсваме изпълнението, ако полученото състояние отговаря на началните условия.

Всеки алгоритъм за търсене би могъл да се използва за търсене в пространството от състояния.

Евристики за търсене в пространството от състояния

Евристиката е важен момент от намиране на ефективно решение, независимо дали прогресивно или регресивно. Например, интересува ни броят действия, необходим за постигане на целта, както и намиране на достатъчно добро приближение за решението, когато проблемът е NP-труден.

[?…]

Частично наредени планове

Досега разлежданите планирания (progression, regression) са видове пълно наредени планирания (планове). Можем да изградим пълно нареден план, работейки с частично наредени планове. Пример: обуване на обувки (и чорапи). Планът, който изграждаме, включва две независими последователности от действия - за ляв и десен крак. За разлика от пълните наредби, тук не заявяваме твърд ред на изпълнение на тези последователности.

Най-простият план има само начално и крайно състояние. Тръгвайки от него, "доуточняваме" детайлите в плана. ("София->Варна"; постепенно доуточняваме през кои междинни точки ще преминем - "изясняваме" плана). Имаме и някакви ограничения - действието A трябва да се случи преди действието B. Имаме причинно-следствени връзки, които важат при прехода от едно до друго състояние - действието, което свързва двете състояния, не бива да ги нарушава. Имаме и така наречените "отворени" условия - тези, които още не сме удовлетворили.

Един план е съвместим (консистентен), ако няма цикли в ограниченията на последователностите, и няма конфликти (цикли) в причинно-следствените връзки. В процеса на действие, частично нареденият план се преобразува в пълно нареден.

С частично наредения план действаме по следния начин: избираме едно отворено условие, след което търсим всички консистентни планове-наследници (поредици от действия), които удовлетворяват условието. Когато генерираме планове-наследници, добавяме причинните връзки и ограниченията към плана (a —p-> B и A < B). След това разрешаваме конфликтите между новата причинна връзка и съществуващите [?планове], както и между новото състояние A и съществуващите [???].

В обобщение: Започваме с неясен / непълен план. Към него можем да добавяме връзка от съществуващ план към отворено условие, да добавим стъпка за изпълнение на отвореното условие, и да вкараме наредба за дадена стъпка, за да разрешим съществуващ конфликт. Ако достигнем неудовлетворимо условие, се връщаме назад (backtracking). Когато завърши процесът, имаме пълно нареден план.

Пример с резервна гума [pdf] [тоя пример е хубав и донякъде обяснява абстрактните простотии за частично наредените планове].
За определяне на предусловие (PRECOND) може да използваме принципа за най-ограничената променлива (most-heavily-constrained) в CSP.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License