Пример планирования с частичным упорядочением
Теперь рассмотрим, как можно с помощью алгоритма POP решить задачу с запасным колесом, описанную в разделе 11.1. Описание этой задачи повторно приведено в листинге 11.4.
Листинг 11.4. Описание простой задачи замены колеса со стертой покрышкой
Init(At{Flat,Axle) A At(Spare,Trunk)) Goal(At(Spare,Axle)) Action(Remove(Spare,Trunk),
Precond: At(Spare,Trunk)
Effect: —iAt (Spare, Trunk) A At (Spare, Ground) ) Action (Remove (Flat, Axle) ,
Precond: At(Flat,Axle)
Effect: -iAt (Flat, Axle) A At (Flat, Ground) ) Action(PutOn(Spare, Axle),
Precond: At(Spare,Ground) A —I At(Flat,Axle)
Effect: -nAt (Spare, Ground) A At (Spare, Axle) ) Action (LeaveOvernight,
Precond:
Effect: -nAt (Spare, Ground) A -nAt (Spare, Axle) A -nAt (Spare, Trunk) A -nAt (Flat, Ground) A -nAt (Flat, Axle) )
Поиск решения начинается с начального плана, содержащего действие Start с результатом At (Spare, Trunk) A At (Flat, Axle) и действие Finish с единственным предусловием At (Spare, Axle). Затем вырабатываются преемники путем взятия открытого предусловия для его проработки (не допускающей отмены) и выбора среди возможных действий для его достижения. На данный момент мы не будем задумываться над тем, что нужно воспользоваться какой-то эвристической функцией, которая могла бы помочь в выработке этих решений, и станем выбирать варианты, которые внешне кажутся произвольными. Последовательность событий описана ниже.
1. Взять единственное открытое предусловие, At (Spare, Axle), действия Finish. Выбрать единственное применимое действие, PutOn (Spare, Axle).
2. Взять предусловие At (Spare, Ground) действия PutOn (Spare, Axle). Выбрать единственное применимое действие, Remove (Spare, Trunk), чтобы достичь его. Результирующий план показан на рис. 11.3.
Взять предусловие -iAt {Flat, Axle) действия PutOn{Spare, Axle). Просто для того чтобы поступить вопреки здравому смыслу, выберем действие LeaveOvernight, а не действие Remove{Flat, Axle). Но обратите внимание на то, что действие LeaveOvernight также имеет результат -iAt {Spare, Ground), который означает, что оно конфликтует со следующей причинной связью:
Remove {Spare, Trunk)At (sP4ROUND)putOn{ Spare, Axl e)
Чтобы разрешить этот конфликт, добавим ограничение упорядочения, которое помещает действие LeaveOvernight перед действием Remove {Spare, Trunk). Возникающий при этом план показан на рис. 11.4. (Предлагаем читателю ответить на вопросы, почему такое дополнение позволяет разрешить конфликт и почему нет другого способа его разрешить?)
4. В этот момент единственным оставшимся открытым предусловием является предусловие At {Spare, Trunk) действия Remove{Spare, Trunk). Единственным действием, позволяющим достичь этого предусловия, является существующее действие Start, но причинная связь от Start к Remove {Spare, Trunk) конфликтует с результатом -iAt (Spare, Trunk) действия LeaveOvernight. В данный момент не существует способа разрешить конфликт с действием LeaveOvernight — его нельзя переупорядочить таким образом, чтобы оно находилось перед Start (поскольку ни одно действие не может происходить перед действием Start), и нельзя переупорядочить его так, чтобы оно находилось после Remove {Spare, Trunk) (поскольку уже имеется ограничение, которое упорядочивает его перед Remove {Spare, Trunk)). Поэтому необходимо вернуться к одному из предыдущих состояний, удалить действие LeaveOvernight и две последние причинные связи, возвратившись в состояние, показанное на рис. 11.3. Планировщик фактически доказал, что действие LeaveOvernight не может применяться в качестве способа замены колеса.
5. Еще раз рассмотрим предусловие —At{Flat,Axle) действия PutOn(Spare, Axl e). На этот раз выберем действие Remove (Flat, Axl е).
6. Снова возьмем предусловие At (Spare, Trunk) действия Remove(Spare, Trunk) и выберем действие Start, чтобы его достичь. На сей раз конфликты не возникают.
7. Возьмем предусловие At (Flat, Axle) действия Remove (Flat, Axle) и выберем действие Start для его достижения. Это дает нам полный согласованный план (иными словами, решение), как показано на рис. 11.5.
Хотя данный пример очень прост, он иллюстрирует некоторые преимущества планирования с частичным упорядочением. Во-первых, причинные связи способствуют заблаговременному отсечению тех частей пространства поиска, которые не содержат решений из-за неустранимых конфликтов. Во-вторых, решение, приведенное на рис. 11.5, представляет собой план с частичным упорядочением. В данном случае преимущества невелики, поскольку имеются только две возможные линеаризации; тем не менее повышенная гибкость выбора вариантов может пойти агенту на пользу, например, если ему придется менять колесо в середине шоссе с интенсивным движением.
Этот пример также указывает на некоторые возможные усовершенствования, которые вполне могут быть осуществлены. Например, в данном случае налицо дублирование усилий: действие Start соединяется связью с действием Remove (Spare, Trunk) до того, как конфликт вызывает возврат, а затем эта связь снова разрывается из-за возврата, даже несмотря на то, что она не участвует в конфликте. После этого в ходе продолжения поиска связь снова восстанавливается. Такое развитие событий является типичным для хронологических возвратов, и его последствия могут быть смягчены с помощью возвратов, управляемых с учетом зависимостей.