Планирование с частичным упорядочением и несвязанными переменными
В этом разделе рассматриваются сложности, которые могут возникнуть, если алгоритм POP используется с представлениями действий в логике первого порядка, которые могут включать переменные. Предположим, что имеется задача в мире блоков (см. листинг 11.3) с открытым предусловием On (А, В) и следующим действием:
Action (Move (b, х, у) , Precond: Оп(Ь,х) л Clear(b) л Clear(y), Effect: On(b,y) л Clear(x) л -лОп(Ь,х) л —iClear(y) )
Это действие достигает результата Оп{А, В), поскольку результат Оп{Ь,у) унифицируется с термом Оп(А,В) с помощью подстановки {Ь/А, у/В]. Затем применим эту подстановку к действию и получим следующее:
Action {Move {А, х, В) Precond: Оп{А,х) л Clear(А) л Clear{В) Effect: Оп{А,В) л Clear(x) л -лОп{А,х) л -.Clear(B) )
При этом переменная х остается несвязанной. Тем самым в данном действии определено, что блок А нужно переместить откуда-то, а откуда, не сказано. В этом заключается еще один пример реализации принципа наименьшего вклада: мы можем отложить выполнение выбора до какого-то этапа, в котором сам план укажет для нас этот выбор. Например, предположим, что в начальном состоянии имеется предусловие On (A, D). В таком случае для достижения предусловия Оп(А,х) может использоваться действие Start со связыванием х с D. Такая стратегия с ожиданием дополнительной информации перед выбором х часто является более эффективной по сравнению с опробованием любого возможного значения х и возвратом в ответ на неудачный выбор каждого из этих значений.
Из-за наличия переменных в предусловиях и действиях процесс обнаружения и разрешения конфликтов усложняется. Например, после добавления к плану действия Move (А, х, В) потребуется следующая причинная связь:
Move(A,xlB)04) Finish
Если имеется другое действие М2 с результатом -iOn(A, z), то М2 конфликтует, только если переменная z равна в. Чтобы учесть такую возможность, расширим представление планов для включения множества ограничений неравенства в форме zx, где z — переменная, ах — либо другая переменная, либо константный символ. В данном случае можно было бы разрешить конфликт путем добавления ограничения zB, которое означает, что в будущих дополнениях к плану разрешается конкретизировать переменную z любым значением, кроме В. При каждом применении к плану некоторой подстановки необходимо контролировать, чтобы подобные неравенства не противоречили этой подстановке. Например, подстановка, которая включает х/у, конфликтует с ограничением неравенства хФу. Такие конфликты не могут быть разрешены, поэтому планировщику приходится выполнять возврат.
Более подробный пример планирования по алгоритму POP с переменными в мире блоков приведен в разделе 12.6.