Главная arrow книги arrow Копия Глава 11. Основы планирования arrow Задача планирования
Задача планирования

Рассмотрим, что может произойти, когда обычный агент, решающий задачи с помощью стандартных алгоритмов поиска (поиска в глубину, поиска А* и т.д.), сталкивается с крупными задачами реального мира. Это позволит нам научиться разрабатывать лучших планирующих агентов.

Наиболее очевидная сложность состоит в том, что агент, решающий задачи, может быть просто подавлен огромным количеством действий, не относящихся к делу. Рассмотрим задачу покупки одного экземпляра англоязычного издания настоящей книги с названием AI: A Modern Approach в электронном книжном магазине. Предположим, что агент-покупатель должен совершить одно действие, связанное с покупкой, в расчете на каждый возможный десятицифровой номер ISBN, что приводит к общему количеству действий, равному 10 миллиардам. В ходе применения алгоритма поиска агент должен исследовать состояния результатов всех 10 миллиардов действий, чтобы определить, какое из них соответствует цели, заключающейся в том, чтобы приобрести экземпляр книги с номером ISBN 0137903952. С другой стороны, разумный планирующий агент должен быть способным проработать процедуру покупки в обратном направлении, от явного описания цели, такого как Have{ISBN0137903952), и непосредственно сформировать действие Buy{ISBN013 7'903952). Для этого агенту требуется иметь общие знания о том, что действие Виу(х) приводит к результату Have{x). При наличии этих знаний и цели планировщик может определить в единственном шаге унификации, что правильным действием является Виу( ISBN013 7903952).

Еще одна сложность заключается в определении хорошей эвристической функции. Предположим, что цель агента состоит в том, чтобы купить четыре разных книги в оперативном режиме. Количество планов только для четырех этапов покупки будет составлять, поэтому поиск без точной эвристики даже нет смысла рассматривать. Для человека очевидно, что хорошей эвристической оценкой для стоимости состояния является количество книг, которые еще предстоит купить; к сожалению, эта идея не столь очевидна для агента, решающего задачи, поскольку он рассматривает процедуру проверки цели как "черный ящик", который возвращает истину или ложь в ответ на каждое состояние. Поэтому агент, решающий задачи, не обладает автономностью; он требует, чтобы человек предоставлял ему эвристическую функцию для каждой новой задачи. С другой стороны, если планирующий агент имеет доступ к явному представлению цели как конъюнкции подцелей, то может использовать единственную эвристику, независимую от проблемной области, — количество невыполненных конъюнктов. Для задачи покупки книг цель будет представлять собой выражение, а состояние, содержащее выражение , будет иметь стоимость 2. Таким образом, агент автоматически получает правильную эвристику для этой задачи и для многих других. Ниже в этой главе будет показано, как формировать более сложные эвристики, в которых учитываются не только структура цели, но и возможные действия.