Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 141
Текст из файла (страница 141)
Для того чтобы упростить эту задачу, рассмотрим чрезвычайно абстрактную ее версию, в которой не учитываются крепко прихваченные крепежные гайки или другие усложнения. Существуют только четыре действия: выемка запасного колеса из багажника, снятие колеса со стертой покрышкой с оси, установка запасного колеса на ось и оставление автомобиля без присмотра на ночь. Предполагается, что автомобиль находится в районе с исключительно неблагоприятной криминогенной обстановкой, поэтому результатом его пребывания ночью на улице становится исчезновение колес.
Описание АО(. этой задачи приведено в листинге 11.2. Обратите внимание на то, что оно является исключительно пропозициональным. Это описание превосходит по своим возможностям описание на языке 5(прз в том, что в его предусловии для действия РисОп(Брате, Ах1е) (поместить запасное колесо на ось) используется отрицаемый препикат АС (Р1аС, Ах1е) (отрицание предиката АС (Р1аС, Ах1е)— на оси находится колесо со стертой покрышкой). Необходимости в этом можно избежать, применяя вместо него предикат С1еаг(Ах1е) (отсутствие колеса на оси), как будет показано в следующем примере.
Листинг 11.2. Простая задача с запасным колесом Тпхе(АС(Р1ат,лх1е) л АС(Брате, Тгипк) ) Еоа1 (АС(Брате,лх1е) ) Асе1оп (летсие (Браге, Тгипх), Ртесопс): АС(Браге, Ттип)с) еееесс: Ас(Браге, тгипх) л Ас(Браге, Бгоипс()) Асехоп(Яетоие(Р1ае,лх1е), Ртесопсп АС(Р1ае,лх1е) ЕЕЕесг: АС(Р1аС,Ах1е) л АС(Р1ае,етоипс))) Асг1оп(Риееп(Брате, Ах1е), Ртесспп: АС(Браге,огоипЦ) л АС(Р1аС,Ахзе) 520 Часть !'з(. Планирование Егсест: АС(Брате,отоипс)) л АС(Брате,лх1е) ) А с Сз оп (Ьеаиеоиетпзод С, Ргесопс): Еьгест: АС(Брате,отоипй) л АС(Брате,Ах1е) л -АС(Браге,ттип)с) л АС(Р1аС,Отсипсй л АС(Р1ат,лх1е)) Пример: мир блоков Одна из наиболее широко известных проблемных областей планирования известна под названием 'ск мира блоков. Эта проблемная область состоит из множества блоков кубической формы, находящихся на столе'.
Блоки можно укладывать в столбик, но на верхней поверхности одного блока может быть непосредственно размещен только еше один блок. Робот может брать манипулятором блок и перемешать его в другую позицию — либо на стол, либо на верхнюю поверхность другого блока. С помощью манипулятора может быть взят одновременно только один блок, поэтому невозможно взять блок, на котором стоит еше один блок. Цель всегда заключается в том, что должны быть построены один или несколько столбиков из блоков, а сами задачи формулируются в терминах того, какие блоки находятся над указанными другими блоками. Например, задача может состоять в том, чтобы поставить блок А на в и блок О на ().
Для указания на то, что блок Ь находится на блоке х, где х — либо другой блок, либо стол, используется предикат Оп (.Ь, х) . Для перемещения блока Ь с верхней поверхности блока х на верхнюю поверхность блока у применяется действие )чоие( Ь, х, у) . Итак, одним из предусловий перемещения Ь является то, что на нем не стоит какой-то другой блок. В логике первого порядка оно может быть представлено с помощью выражения 3х Оп (х, Ь) или альтернативного выражения 'з(х Оп(х, Ь) Эти выражения могут быть сформулированы как предусловия на языке АР)-. Но мы могли бы оставаться в рамках языка Яг1рз, введя новый преликат, О1еаг(х), который является истинным, если на блоке х ничего нет (верхняя поверхность блока х свободна). Действие лгоие позволяет переместить блок Ь с блока х на блок у, если свободны верхние поверхности и блока Ь, и блока у. После выполнения этого действия верхняя поверхность блока х свободна, а блока у — нет.
Формальное описание действия моие в языке 5(г1рз состоит в следующем: Астзоп (Мои е (Ь, х,з ), Ртесопс): оп(ь,х) л с1еат(Ь) л с1еат(у), Ебгест: Оп(Ь,у) л С1еаг(х) л ~оп(Ь,х) л ~С1еаг(у) ) К сожалению, в этом действии предикат О1еаг не сопровождается должным образом, если блок х или блок у находится на столе. Если х=гаЬ1е, то результатом этого действия будет О1еаг( таЬ1е), но поверхность стола не должна становиться свободной (поскольку она и так всегда свободна), а если у=таЬ1е, то действие имеет предусловие О1еаг( таЬ1е), но вся поверхность стола не обязана быть свободной для того, чтобы на нее можно было поместить блок (поскольку на столе всегда и Мир блоков, используемый в этих исследованиях планирования, гораздо проще по сравнению с версией Яйгб!и, которая показана на с.
бб. 521 Глава 11. Основы планирования без того достаточно места). Для исправления такого положения необходимо предусмотреть два изменения. Во-первых, введем еше одно действие для перемещения блока Ь с блока х на стол; Асг]оп (МогетотаЫе (.Ь, х), Ртесопсы Оп(Ь,х) л С1еат(.Ь) ), Еттесе: Оп(Ь, ТаЬ1е) л С1еат (х) л — Оп(Ь,х) ) Во-вторых, примем интерпретацию предиката С1еат(Ы как означающую, что "на Ь есть достаточно свободного места, чтобы поместился один блок".
При этой интерпретации предикат С1еат(ТаЬ1е) всегда будет истинным. Единственная проблема состоит в том, что ничто не будет препятствовать планировщику использовать действие моуе (Ь, х, ТаЬ1е) вместо действия моуеТОТаЬ1е (Ь, х) . Можно смириться с этой проблемой (она приводит к созданию пространства поиска с размерами больше необходимого, но не становится причиной получения неправильных ответов) или ввести в предусловие Мот е предикат В1ос]г и добавить в предусловие действия Моуе выражение В1ос]с(Ы л В1осх(у) .
Наконец, существует проблема фиктивных действий, таких как мосе(В, с, с), которые должны представлять собой пустую операцию, но имеют противоречивые результаты. Обычно принято игнорировать подобные проблемы, поскольку они редко вызывают выработку неверных планов. Правильный подход состоит в добавлении предусловий в неравенство, как показано в листинге 11.3. Листинг 1].3. Задача планирования в мире блоков: построение столбика из трех блоков. Одним из решений является последовательность действий [моте(В, таые, с),моте(А, таые, в) ] Тпде(оп(А, ТаЬ1е) л Оп(В, ТаЬ1е) л Оп(С, ТаЬ1е) л В1 ос)с (А ) л В1 ос)г ( В) л В1 ос)с ( С) л С1еат(А) л С1еат(В) л С1еат(С) ) Ооа1 (Оп (А, В) л Оп (В, С) ) Аседоп(мо|е(Ь, х, у), Ртесопсп Оп(Ь,х) л С1еат(Ь) л С1еат(у) л В1ос)с(Ь) л (Ь ах) л (Ь Фу) л (хну), Еттесе: Оп(Ь,у) л С1еат(х) л Оп(Ь,х) л С1еат(у) ) Асг1оп(мооетотаЪ1е(Ь, х), Ртесопсн Оп(Ь,х) л С1еат(Ь) л В1ос)г(Ь) л (Ь Ф х), Еттесс: Оп(Ь, ТаЫе) л С1еат(х) л Оп(Ь,х) ) 11.2.
ПлАниРОВАние с помощью поискА В ПРОСТРАНСТВЕ СОСТОЯНИЙ Данный раздел посвящен описанию алгоритмов планирования. Наиболее простой подход состоит в использовании поиска в пространстве состояний. Поскольку описания действий в задаче планирования определяют и предусловия, и результаты, существует возможность организовать поиск в обоих направлениях; либо в прямом, от начального состояния, либо в обратном, от цели, как показано на рис. 11.1. Кроме того, явные представления действий и целей могут использоваться для автоматического вывода эффективных эвристик.
522 Часть 1Ч. Планирование а) б) Рис. П. 1. Два подхода к организации поиска плана: прямой (прогрессивный) поиск в пространстве сопнояний, начинающийся с начального состояния, в котором используюпюя дейсп1вия задачи для прямого поиска целевого соспюяния (о); обратный (регрессивный) поиск в простронопве состояний: поиск доверительного состояния (см. с. 141), начинающийся с целевого состояния (сосп1ояний), в котором для обратного поиска начального состояния используются инверсии действий (б) Прямой поиск в пространстве состояний Подход к организации планирования с использованием прямого поиска в пространстве состояний аналогичен подходу к решению задач, описанному в главе 3. Иногда его называют 'ъ. прогрессивным планированием, поскольку оно предусматривает продвижение в прямом направлении.
При этом мы начинаем с начального состояния задачи и рассматриваем последовательности действий до тех пор, пока не находим последовательность, позволяющую достичь целевого состояния. Формулировка задач планирования в виде задач поиска в пространстве состояний приведена ниже. ° Начальным состоянием поиска является начальное состояние, взятое из задачи планирования. Вообще говоря, каждое состояние должно представлять собой множество положительных базовых литералов; литералы, не присутствующие в определении задачи, являются ложными. ° Всеми действиями, применимыми в некотором состоянии, являются такие действия, для которых выполнены предусловия. Состояние-преемник, являющееся результатом выполнения действия, вырабатывается путем добавления положительных литералов результата и удаления отрицательных литералов результата.
(В случае использования литералов первого порядка к литералам результата необходимо применять унификатор из предусловий.) Обратите внимание на то, что во всех задачах планирования используется единственная функция определения преемника, что является следствием применения явного представления действий. 523 Глава 11. Основы планирования ° В ходе проверки цели осуществляется проверка того, удовлетворяет ли данное состояние цели условиям задачи планирования. ° Стоимость этапа для каждого действия обычно равна 1. Хотя было бы несложно предусмотреть использование различных стоимостей для разных действий, такая возможность в планировщиках бгг)рз применяется редко. Напомним, что при отсутствии функциональных символов пространство состояний задачи планирования является конечным.
Поэтому полным алгоритмом планирования должен быть любой алгоритм поиска в графе, который является полным (например, А*). Начиная с самых первых дней исследований по планированию (примерно с 1961 года) и до сравнительно недавнего времени (примерно до 1998 года), предполагалось, что прямой поиск в пространстве состояний был бы слишком неэффективен для того, чтобы иметь практическое значение. Причины этого понять совсем несложно — достаточно вернуться в начало раздела 11.1.
Во-первых, прямой поиск не решает проблему не относящихся к делу действий — рассматриваются все действия, применимые из каждого состояния. Во-вторых, без хорошей эвристики этот подход быстро приводит к чрезмерному увеличению объема вычислений. Рассмотрим задачу воздушных грузовых перевозок с 1О аэропортами, где в каждом аэропорту имеется 5 самолетов и 20 единиц груза. Цель состоит в том, чтобы переместить все грузы из аэропорта л в аэропорт в.
Существует простое решение этой задачи: погрузить 20 единиц груза в один из самолетов в аэропорту А, полететь на этом самолете в аэропорт в и выгрузить груз. Но формальный поиск этого решения может оказаться затруднительным, поскольку средний коэффициент ветвления является огромным: кахдый из этих 5х10=50 самолетов может полететь в 9 других аэропортов, а каждая из 20х10 = 2 0 0 единиц груза может быть либо разгружена (если она загружена), либо загружена в любой самолет в аэропорту, где она находится (если она разгружена). Допустим, что в среднем существует около 1000 возможных действий, поэтому дерево поиска с глубиной, равной глубине очевидного решения, имеет около 1000" узлов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
