Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 150
Текст из файла (страница 150)
При использовании этих расщепленных символов мы можем удалить параметр, значение которого нас не интересует: АС(Р, .ТРК)" а» (АС(Р, .ТРК)' Я (РТУ (Р,)' а РТУ»(ТРК)')) ч (Рзу»(Р,)' а Р2у»(.ТРК)') Обратите внимание на то, что в этой аксиоме аэропорты ~КО и ТАК больше не упоминаются. Вообще говоря, теперь расщепленные символы действий позволяют добиться того, чтобы размер каждой аксиомы состояния-преемника был независимым от количества аэропортов.
Аналогичные сокрашения допускаются в аксиомах предусловия и ак- Глава 11. Основы планирования 551 сиомах исключения действий (см. упр. 11.1б). Для описанного выше случая с 10 временными этапами, 12 самолетами и 30 аэропортами полная аксиома исключения действий сокращается с 583 миллионов выражений до 9360 выражений. Но остается непреодоленным еше один недостаток: представление с помошью расшепленных символов не допускает описания параллельных действий. Рассмотрим два параллельных действия, ь2у( Р„ЯкО, тьк) ' и ь2у( р,, тьк, Яко) '. Преобразовав их в расшепленные представления, получим следующее: кто,(я,)' х язв,(яро)' л к)у,(.танк)' х к.~у (д~) к яту ( гяк) х яту (яро) Теперь больше нет возможности определить с помошью этого выражения, что произошло! Мы знаем, что самолеты Р, и Р, вылетели, но не можем выяснить места их отправления и назначения.
Это означает, что должна использоваться полная аксиома исключения действий со всеми указанными выше недостатками. Планировшики, основанные на проверке выполнимости, способны обрабатывать крупные задачи планирования, например находить оптимальные тридцати- этапные решения для задач планирования в мире блоков с десятками блоков. Размер пропозиционального представления и стоимость решения в выс(пей степени зависят от задачи, но в большинстве случаев узким местом становится нехватка памяти, требуемой для хранения пропозициональных аксиом.
Одним из интересных результатов этих исследований оказалось то, что алгоритмы поиска с возвратами, такие как РРЬЬ, часто лучше решают задачи планирования по сравнению с алгоритмами локального поиска, подобными (яа2)сЯАТ. Это связано с тем, что основная часть пропозициональных аксиом представляет собой хорновские выражения, которые эффективно обрабатываются с помощью метода распространения единичных выражений.
Это наблюдение привело к разработке гибридных алгоритмов, в которых комбинируется некоторый метод случайного поиска с возвратами и метод распространения единичных выражений. 11.6. АНАЛИЗ РАЗЛИЧНЫХ ПОДХОДОВ К ПЛАНИРОВАНИЮ Планирование — это область искусственного интеллекта, которая в настоящее время привлекает значительный интерес, Одна из причин такой ситуации состоит в том, что в планировании объединяются два основных направления развития искусственного интеллекта, которые рассматривались нами до сих пор, — поиск и логика. Это означает, что любой планировщик может рассматриваться либо как программа, в которой осуществляется поиск решения, либо как такая программа, которая (конструктивно) доказывает сушествование решения. Такое перекрестное обогашение идеями, взятыми из этих двух областей, привело не только к повышению производительности, которое за последнее десятилетие достигло нескольких порядков величины, но и к расширению использования планировшиков в производственных приложениях.
К сожалению, у нас еше нет четкого понимания того, какие методы являются в наибольшей степени подходящими для задач того или иного типа. Вполне возможно также, что появятся новые методы, которые вытеснят существующие. Планирование главным образом представляет собой такое занятие, в котором приходится держать под контролем комбинаторный взрыв. Если в проблемной об- 552 Часть! Ъ'. Планирование ласти имеется р примитивных высказываний, то количество состояний становится равным 2Я.
В сложных проблемных областях величина р может стать весьма значительной. Следует также учитывать, что объекты в проблемной области характеризуются не только свойствами (Ьосасзоп, СоЛог и тд.), но и отношениями (Ас, Оп, 8есыееп и т.д.). При наличии с) объектов в проблемной области с тернарными отаз ношениями количество состояний достигает 2~ .
На этом основании можно сделать вывод, что в наихудшем случае попытка решить задачу планирования становится безнадежной. Мошным средством преодоления подобной пессимистической ситуации становится подход по принципу "разделяй и властвуй". В наилучшем случае (при полной декомпонуемости задачи) подход "разделяй и властвуй" обеспечивает экспоненциальное ускорение работы. Однако декомпонуемость нарушается из-за отрицательных взаимодействий между действиями. Планировшики с частичным упорядочением позволяют справиться с такой ситуацией с помошью причинных связей — мощного подхода к формированию представлений, но, к сожалению, каждый конфликт должен быть разрешен с помошью выбора определенного варианта (связанного с размешением конфликтуюшего действия до или после связи), а количество таких вариантов может увеличиваться экспоненциально.
Алгоритм ~гар)зр1ап позволяет избежать необходимости использования этих вариантов на этапе формирования графа, поскольку в нем для регистрации конфликтов используются взаимно исключающие связи, а выбор варианта, касаюшегося того, как должны быть разрешены эти конфликты, фактически не осушествляется. Алгоритм Ядтр1ап предоставляет аналогичный набор взаимно исключаюших отношений, но в нем для этого применяется общая форма СХЕ, а не специальная структура данных. Насколько успешным окажется такой подход, зависит от области применения решателя задач БАТ.
Иногда возможность эффективного решения задачи обеспечивается путем определения того, какие отрицательные взаимодействия могут быть исключены. Задача называется имеющей 'а. упорядочиваемые водцели, если существует такой порядок подцелей, что планировщик может достичь их в указанном порядке, не будучи вынужденным отменять какую-либо из ранее достигнутых подцелей. Например, если в мире блоков цель состоит в построении столбика (например, в котором блок д стоит на 8, который, в свою очередь, стоит на С, стояШем, в свою очередь, на столе, таЬ|е), то подцепи являются упорядочиваемыми снизу вверх: если вначале будет достигнута подцель "С на таЫ е", то никогда не придется ее отменять в ходе достижения других подцелей.
Планировщик, в котором используется такой прием с упорядочением снизу вверх, способен решить любую задачу в проблемной области мира блоков без возвратов (хотя и может оказаться, что он не всегда находит самый короткий план). В качестве более сложного примера укажем, что для планировщика Кешоге Айепц который управлял космическим аппаратом Реер Брасе Опе агентства ХАБА, было определено, что высказывания, касающиеся управления космическим аппаратом, являются упорядочиваемыми.
По-видимому, в этом нет ничего удивительного, поскольку космический аппарат проектируется его разработчиками так, чтобы была возможность управлять им как можно проще (разумеется, с учетом всех прочих ограничений). Пользуясь преимушеством последовательного упорядочения целей, планировщик Кетоге Аяепг был способен в процессе планирования устранять ос- 553 Глава 1!. Основы планирования ионную часть поиска. Это означает, что он оказался достаточно быстродействующим для того, чтобы с его помощью можно было управлять этим космическим аппаратом в реальном времени, а такая задача раньше казалась невыполнимой.
Существует несколько способов ограничения комбинаторного взрыва. Как было показано в главе 5, есть несколько методов управления возвратами в задачах удовлетворения ограничений (Сопзггаш~ Яабз?асйоп РгоЫет — С5Р), таких как возвраты, управляемые зависимостями. Все эти методы могут применяться и в планировании. Например, задачу извлечения решения из графа планирования можно сформулировать как булеву задачу С5 Р, переменные которой указывают, должно ли данное конкретное действие произойти в данное конкретное время. Эту задачу С5Р можно решить с использованием любого из алгоритмов, приведенных в главе 5, такого как алгоритм с минимальными конфликтами.
Тесно связанный с этим метод, используемый в системе в1аскЪох, состоит в преобразовании графа планирования в выражение СА)Р, а затем извлечении плана с использованием решателя задач БАТ. Повидимому, такой подход обладает более высокой производительностью, чем ЯАтр1ап, и причиной этого, скорее всего, является то, что в графе планирования уже устранены многие невозможные состояния и действия из рассматриваемой задачи. Кроме того, такой подход действует лучше по сравнению с алгоритмом Стар?зр1ап, по-видимому, из-за того, что поиск условий выполнимости, полобный алгоритму ?Га1кЯАТ, характеризуется гораздо большей гибкостью, чем ограниченный поиск с возвратами, используемый в алгоритме Сгарпр1ап. Нет никакого сомнения в том, что такие планировщики, как Стар)зр1ап, БАТр1ап и В1асйЬох, привели к значительному прогрессу в области планирования, поскольку позволили, во-первых, поднять уровень производительности систем планирования, а вовторых, дали возможность понять связанные с этим представительные и комбинаторные проблемы.
Однако эти методы по своей сути являются пропозициональными и поэтому предназначены исключительно длл использования в тех проблемных областях, которые они способны представить. (Например, задачи планирования экспедиторской доставки с несколькими десятками обьектов и местонахождений могут потребовать гигабайтов памяти лля хранения соответствующих выражений СНЕ) Создается впечатление, что для достижения дальнейшего прогресса в этой области потребуются представления и алгоритмы в логике первого порядка, хотя такие структуры, как графы планирования, по-прежнему будут оставаться полезным источником эвристик.
11.7. РЕЗЮМЕ В этой главе определена залача планирования в детерминированных, полностью наблюдаемых вариантах среды. В ней описаны основные прелставления, используемые для задач планирования, и прелставлено несколько алгоритмических подходов к их решению. Наиболее важные понятия, изложенные в этой главе, перечислены ниже. ° Системы планирования основаны на использовании алгоритмов решения задач, которые применяются к явным представлениям состояний и действий в пропозипиональной логике (или логике первого порядка). Такие представления обеспечивают возможность получения эффективных эвристик, а также разработки мощных и гибких алгоритмов для решения задач планирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
