Главная » Просмотр файлов » Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006)

Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 143

Файл №1245267 Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006)) 143 страницаРассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267) страница 1432021-01-15СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 143)

Сушествует также возможность создавать ослабленные задачи, удаляя отрицательные результаты без удаления предусловий. Таким образом, если некоторое действие в первоначальной задаче имеет результат А л — В, то в ослабленной задаче будет иметь результат А. Это означает, что не нужно беспокоиться об отрицательных взаимодействиях субпланов, поскольку ни одно действие не способно удалить лите- 527 Глава 11.

Основы планирования ралы, достигнутые другим действием. Стоимость решения полученной в конечном итоге ослабленной задачи задает то, что принято называть эвристикой с Ъ. пустым списком удаления. Эта эвристика является весьма точной, но для ее вычисления требуется действительно выполнить некоторый (простой) алгоритм планирования. Тем не менее на практике поиск в условиях ослабленной задачи часто происходит достаточно быстро для того, чтобы имело смысл применение этой оценки стоимости. Описанные здесь эвристики могут использоваться либо в прогрессивном, либо врегрессивном направлении.

Ко времени написания данной книги первые места врейтинге эффективности занимали прогрессивные планировшики, в которых применялась эвристика с пустым списком удаления. Такая ситуация вполне может измениться в результате исследования новых эвристик и новых методов поиска. Поскольку задачи планирования являются экспоненциально трудными', ни один алгоритм не может быть достаточно эффективным лля решения всех задач, но с использованием эвристических методов, описанных в этой главе, могут быть решены многие практические задачи, и таких задач стало гораздо больше по сравнению с теми, которые были решаемыми всего лишь несколько лет тому назад. 11.3. ПЛАНИРОВАНИЕ С ЧАСТИЧНЫМ УПОРЯДОЧЕНИЕМ Прямой и обратный поиск в пространстве состояний представляют собой особые формы поиска полностью упорядоченного плана. В них рассматриваются только строго линейные последовательности действий, непосредственно связанные с начальным или целевым состоянием.

Это означает, что такие методы поиска не позволяют воспользоваться преимуществами декомпозиции задачи. Вместо того чтобы обеспечить отдельную проработку каждой подзадачи, эти методы вынуждены всегда поддерживать принятие решений о том, как упорядочить действия, относящиеся ко всем подзадачам.

Но обычно более предпочтительным является подход, позволяющий работать над несколькими подцелями независимо, достигать их с помощью нескольких субпланов, а затем объединять эти субпланы. Подобный подход обладает также тем преимушеством, что позволяет добиться большей гибкости при определении последовательности, в которой составляется окончательный план. Это означает, что планировшик вначале может работать над "очевидными" или "важными" решениями, не будучи вынужденным прорабатывать все этапы в хронологическом порядке. Например, планируюший агент, который находится в Беркли и желает попасть в Монте-Карло, может вначале попытаться найти рейс из Сан-Франциско в Париж; получив информацию о времени отправления и прибытия этого рейса, он может затем заняться поиском способов того, как доехать и выехать из соответствующих аэропортов. Обшая стратегия, в которой в процессе поиска выбор определенных этапов откладывается на более позднее время, называется стратегией с Ъ.

наименьшим вкладом (1еам сопцпйгпепг). Формального определения стратегии с наименьшим вкладом не существует, поскольку очевидно, что на любом этапе поиска должен быть сделан т Формально процедура планирования в стиле 5тпрв является РьРАСЕ-полной, если только не рассматриваются действия, которые имеют только положительные прсдусловия и лишь один литерал результата 12г4] 528 Часть 1~(.

Планирование определенный вклад в окончательное решение, так как в противном случае поиск окажется непродуктивным. Несмотря на такую неформальность, наименьший вклад — это полезная концепция для анализа того, какие решения должны быть приняты в любой задаче поиска. Приведенный в этом разделе первый конкретный пример будет гораздо проше по сравнению с планированием отпуска, проводимого в Монте-Карло. Рассмотрим простую задачу надевания пары туфель. Ее можно описать как формальную задачу планирования следующим образом: Ооат(ддядсэдоеоп п ЬеГСБйоеоп) Гпзс () Асехоп(ЯДРДСБДое,Рсесопои ЕдяъсБосяоп,ЕГСесс: Ятддсддоеоп) Ассдоп(лдядСБос(с,вггесс: Лдяпсдос(гоп) АсСДоп(ъеГСБпое,Рсесопс(: ЬеЕСБос(гоп,ЕйгесС: ЬеЮСБЬоеоп) Асг' (ЬесСБ (с,дссесс: ЬесСБ Коп) Планировщик должен быть способен предложить последовательность из двух действий, ((зр)зсдос)с (надеть правый носок), затем дздпсБ(зое (надеть правую туфлю), чтобы достичь первого конъюнкта этой цели, и последовательность еегсБОО)с (надеть левый носок), затем еегс5(зое (надеть левую туфлю), чтобы достичь второго конъюнкта.

После этого эти две последовательности могут быть объединены для создания окончательного плана. В ходе этого планировщик будет манипулировать двумя подпоследовательностями независимо, не задумываясь над тем, должно ли какое-то действие в одной последовательности быть выполнено до или после некоторого действия в другой. Любой алгоритм планирования, способный включить в план два действия без указания того, какое из них должно быть выполнено первым, называется Ъ. планировщиком с частичным упорядочением (рап(а!- ог((ег р!аппег).

На рис. 11.2 показан план с частичным упорядочением, который представляет собой решение задачи надевания туфель и носков. Обратите внимание на то, что это решение представлено в виде графа, а не последовательности действий. Заслуживают также внимания "фиктивные" действия„называемые Бсагс и еупд Б)з, которые отмечают начало и конец плана. Назвав эти ситуации действиями, мы можем упростить структуру плана, поскольку теперь каждый этап плана становится действием. Это решение с частичным упорядочением соответствует шести возможным планам с полным упорядочением; каждый из них называется Ж линеаризацией плана с частичным упорядочением.

Планирование с частичным упорядочением может быть реализовано в виде поиска в пространстве планов с частичным упорядочением. (Начиная с этого момента, мы будем называть их просто "планами".) Это означает, что поиск начинается с пустого плана. После этого рассматриваются способы уточнения плана до тех пор, пока не удастся составить полный план, который решает данную задачу. Действия, рассматриваемые в этом поиске, являются не действиями в мире, а действиями в планах: добавление в план этапа; наложение упорядочения, согласно которому одно действие должно занять место перед другим; и т.д. В данном разделе будет определен алгоритм РОР (Ран(а1-Ог((ег Р1апп(пд) для планирования с частичным упорядочением.

В соответствии с об(цепринятой традицией алгоритм РОР оформляется в виде отдельной программы, но мы вместо этого определим задачу планирования с частичным упорядочением как экземпляр задачи поиска. Это позволит нам сосредоточиться на этапах уточнения плана, которые могут Глава 11. Основы планирования 529 Планы с полным Гпорялоченисм План с частичным Гиорялочением Ееутхаслоп Ятгят3асяпп Ееутхяоеоп, Лтгятхяаепп о иявь Рис. 11.2. План надевания туфель и носков с частичным упорядочением и шесть сооптветпсптвую- шил линеаризаиий в виде планов с полным упорядочением Напомним, что состояниями рассматриваемой задачи поиска должны быть планы (в основном незаконченные). Чтобы избежать путаницы с состояниями мира, мы будем вести речь о планах, а не о состояниях.

Каждый план имеет описанные ниже четыре компонента, где первые два определяют этапы плана, а последние два выполняют функции учета, позволяющие определить, как может быть дополнен план. ° Множество действий, из которых состоят этапы плана. Эти действия берутся из множества действий в задаче планирования. "Пустой" план содержит только действия 8сагс и рзпзн)т. Действие Всакс не имеет предусловий, а его результатом являются все литералы в начальном состоянии задачи планирования.

Действие Ыпйн)т не имеет результатов, а его предусловиями являются литералы цели в задаче планирования. ° Множество 'в.ограничений упорядочения. Каждое ограничение упорядочения находится в форме А ч В, которая читается как "А перед В ' и означает, что действие А должно быть выполнено в какое-то время перед действием в, но не обязательно непосредственно перед ним.

Характеристики

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6458
Авторов
на СтудИзбе
304
Средний доход
с одного платного файла
Обучение Подробнее