Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 139
Текст из файла (страница 139)
Такая среда называется средой;ъ. классического планирования. В отличие от этого, неклассическое планирование предназначено для частично наблюдаемых или стохастических вариантов среды и для него требуется другой набор алгоритмов и проектов агентов, описанный в главах 12 и 17. 513 Глава 11. Основы планирования 11.1. ЗАДАЧА ПЛАНИРОВАНИЯ Рассмотрим, что может произойти, когда обычный агент, решающий задачи с помощью стандартных алгоритмов поиска (поиска в глубину, поиска А* и т.д.), сталкивается с крупными задачами реального мира. Это позволит нам научиться разрабатывать лучших планирующих агентов.
Наиболее очевидная сложность состоит в том, что агент, решающий задачи, может быть просто подавлен огромным количеством действий, не относящихся к делу. Рассмотрим задачу покупки одного экземпляра англоязычного издания настоящей книги с названием АУ: А Модегл АрргиасЬ в электронном книжном магазине. Предположим, что агент-покупатель должен совершить одно действие, связанное с покупкой, в расчете на каждый возможный десятицифровой номер 1ВВХ, что приводит к общему количеству действий, равному!0 миллиардам. В ходе применения алгоритма поиска агент должен исследовать состояния результатов всех 10 миллиардов действий, чтобы определить, какое из них соответствует цели, заключающейся в том, чтобы приобрести экземпляр книги с номером 15ВХ 0137903952. С другой стороны, разумный планирующий агент должен быть способным проработать процедуру покупки в обратном направлении, от явного описания цели, такого как Науе(1БНН0137903952), и непосредственно сформировать действие ниу( 1ннн013 7903952) .
Для этого агенту требуется иметь общие знания о том, что действие виу(х) приводит к результату наие(х). При наличии этих знаний и цели планировщик может определить в единственном шаге унификации, что правильным действием является Виу(15ВН013 7903952) . Еше одна сложность заключается в определении хорошей эвристической функции.
Предположим, что цель агента состоит в том, чтобы купить четыре разных книги в оперативном режиме. Количество планов только для четырех этапов покупки будет составлять 10", поэтому поиск без точной эвристики даже нет смысла рассматривать. Для человека очевидно, что хорошей эвристической оценкой для стоимости состояния является количество книг, которые еше предстоит купить; к сожатению, эта идея не столь очевидна для агента, решающего задачи, поскольку он рассматривает процедуру проверки цели как "черный ящик", который возвращает истину или ложь в ответ на каждое состояние.
Поэтому агент, решающий задачи, не обладает автономностью; он требует, чтобы человек предоставлял ему эвристическую функцию для каждой новой задачи. С другой стороны, если планирующий агент имеет доступ к явному представлению цели как конъюнкции подцелей, то может использовать единственную эвристику, независимую от проблемной области, — количество невыполненных конъюнктов.
Для задачи покупки книг цель будет представлять собой выражение наие(7() а наие(н) а наие(0) а наие(и), а состояние, содержащее выражение наие(й) а наие(0), будет иметь стоимость 2. Таким образом, агент автоматически получает правильную эвристику для этой задачи и для многих других. Ниже в этой главе будет показано, как формировать более сложные эвристики, в которых учитываются не только структура цели, но и возможные действия. Наконец, агент-решатель задач может оказаться неэффективным из-за того, что не способен воспользоваться ев. декомпозицией задачи. Рассмотрим задачу доставки множества пакетов ночной почты по соответствующим адресатам, которые разбросаны по всей Австралии.
В данном случае имеет смысл найти аэропорт, ближайший к каждому адресату, и разделить общую задачу на несколько подзадач, по одной на 514 Часть 1Ч. Планирование каждый аэропорт. А в самом множестве пакетов, доставляемых через каждый конкретный аэропорт, можно определить в зависимости от города адресата допустимость дальнейшей декомпозиции. Как было описано в главе 5, способность выполнять декомпозицию такого рода обеспечивает повышение эффективности решателей задач удовлетворения ограничений. Такое же утверждение остается справедливым для планировшиков; в наихудшем случае может потребоваться время 0(п! ) для поиска наилучшего плана доставки п пакетов, но если существует возможность выполнить декомпозицию этой задачи на и равных частей, затраты времени будут составлять только О( (пг')с) ) хн) . Как было отмечено в главе 5, идеально декомпонуемые задачи являются очень привлекательными, но встречаются редко'.
Проекты многих систем планирования (особенно планировшиков с частичным упорядочением, описанных в разделе 11.3) основаны на предположении, что большинство задач реального мира являются сух частично декомпоиуемыми. Это означает, что планировгцик может работать над подцелями независимо, но, скорее всего, ему потребуется также выполнить определенную дополнительную работу по объединению результирующих субпланов. Применительно к некоторым задачам такое предположение не оправдывается, поскольку велика вероятность того, что работа над одной подцелью будет приводить к разрушению результатов работы над другой подцелью. Именно из-за такого взаимодействия подцелей и являются трудноразрешимыми многие головоломки (подобные задаче игры в восемь). Язык задач планирования Как следует из приведенного выше описания, сам способ представления задач планирования (состояний, действий и целей) должен обеспечивать возможность для алгоритмов планирования воспользоваться логической структурой задачи.
Весь секрет состоит в том, чтобы найти язык, достаточно выразительный для описания широкого круга задач, но вместе с тем достаточно ограничительный для обеспечения функционирования на его основе эффективных алгоритмов. В этом разделе вначале рассматривается основной язык представления классических планировшиков, известный под названием' 5(г)рз.
Затем кратко представлены некоторые из многих возможных вариантов языков, подобных 5(г)рз. ° Представление состояний. В планировщиках применяется декомпозиция мира на логические условия, а состояние представляется в виде конъюнкции положительных литералов. Мы будем рассматривать пропозициональные литералы; например, выражение Рооп ж ~7пнпоьгп может представлять состояние агента- неудачника (бедного и безвестного). В этой главе будут также использоваться ли- тЕРаЛЫ ПЕРВОГО ПОРЯДКа; НаПРИМЕР, ВЫРажЕНИЕ АС(Р1аПЕз,МЕ1ЬОиДПЕ) Л ЛС (Р1аПЕз, ЯУС)ПЕУ) МОжЕт ПРЕДСтаВЛЯтЬ ОДНО ИЗ СОСтОЯНИй В ЗаДаЧЕ ДОСтаВКИ ' Следует отметить, что даже залача доставки пакетов не является идеально декомпонуемой.
Могут возникать такие случаи, в которых лучше назначить пакеты для доставки в более отдаленный аэропорт, если это позволит исключить необхолимость еще одного полста в более близкий аэропорт. Тем не менее большинство компаний, занимающихся доставкой почты, предпочитают решения, характеризующиеся вычислгпельной и организационной простотой, таким решениям, которые продиктованы требованиями декомпозиции.
з 5гпрз — сокращение от 5Таптощ йезеагс!з (пзщще Ргоыет 5о)хег. Глава ! !. Основы планирования 5(5 пакетов. Литералы в описаниях состояния первого порядка должны быть базовыми и не содержащими функций. Такие литералы, как А г (х, у) или дг(раейег(Ргес)), Бус)пеу), недопускаются. Кроме того, используетсяпредположение о замкнутом мире, которое означает, что любые условия, не упомянутые в описании состояния, считаются ложными.
° Представление целей. Цель — это частично заданное состояние, представленное в виде конъюнкции положительных базовых литералов, таких как дхс)з л Распоиа или А е ( Р,, та)зз' е з'. ) . Пропозици опальное состояние а 'гк удовлетворяет цели д, если а содержит все атомы из с (и, возможно, другие атомы). Например, состояние Ыси л Ратоиа л м1аегаЫе (богатый, знаменитый и несчастный) удовлетворяетцелиЯусй л Ратоиа. ° Представление действий. Любое действие задается в терминах предусловий, которые должны соблюдаться до того, как оно может быть выполнено, и результатов, которые становятся следствием его выполнения. Например, действие, состоящее в перелете самолета из одного места в другое, можно записать следующим образом; лсехои(Е1у!р, Ггссь со), Ргесопд: ЛЕ (р, Егот) л Рзапе(р) л Ахгроге (агом) л Ахгрогс ( Сс), еееесс: ле(р, ггот) л Ае(р, ес) ) где Ргесопс) обозначает предусловие, а кЕЕесг — результат.
Такое выражение следовало бы называть не просто действием, а Ж схемой действия, в том смысле, что в нем представлен целый ряд различных действий, которые могут явиться следствием конкретизации переменных р, ггоп и Со различными константами. Вообще говоря, любая схема действия состоит из перечисленных ниже трех частей. ° имя действия и список параметров (например, Р1у(р, ггоя, ео) ) служат для обозначения действия. ° 'а. Предусловием называется конъюнкция не содержащих функций положительных литералов, регламентирующая то, что должно быть истинным в некотором состоянии, прежде чем можно будет выполнить рассматриваемое действие.
Любые переменные, заданные в предусловии, должны также присутствовать в списке параметров действия. ° Ъ. Результатом является конъюнкция не содержащих функций литералов, представляющая собой описание того, как изменится состояние после выполнения действия. В состоянии, ставшем результатом действия, подтверждается истинность положительного литерала Р в результате, тогда как применительно к отрицательному литералу ~Р подтверждается его ложность. Переменные, присутствующие в результате, должны также присутствовать в списке параметров действия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
