Конспект лекций по дисциплине «Системы искусственного интеллекта»




НазваниеКонспект лекций по дисциплине «Системы искусственного интеллекта»
страница9/11
Дата05.09.2012
Размер1.15 Mb.
ТипКонспект
1   2   3   4   5   6   7   8   9   10   11

9.2. Планирование в пространстве состояний


Первым планировщиком, осуществляющим планирование в пространстве состояний, является STRIPS (STanford Research Institute Problem Solver) [Error: Reference source not found6], который предполагалось применить для решения задачи формирования плана поведения робота, перемещающего предметы через множество помещений.

Собственно, идея алгоритма STRIPS заимствована из системы GPS [57]. Метод, использованный в GPS, назывался анализ средств и целей (means-ends analysis). Он подразумевает рассмотрение в текущем состоянии тех действий, которые имеют отношение к цели. Однако, при таком подходе возникает следующая проблема: применять ли действия, связанные с целью, немедленно, как только они найдены или же приостановить применение действия до тех пор, пока не будут найдены все действия имеющие отношение к цели? STRIPS применяет действия не откладывая, достигая каждой цели по отдельности.

МакДермот [38] показал, что эффективность планирования с использованием метода анализа средств и целей может быть намного повышена задержкой применения действия до тех пор, пока не будут найдены все релевантные (относящиеся к цели действия) и повторением поиска релевантных действий заново, после каждого применения действия.

Для решения проблемы фрейма STRIPS предлагает в состоянии, к которому применяется правило (действие), изменять выполнимость лишь тех формул, которые описаны в эффекте действия, а выплнимость всех остальных оставлять неизменной.

Рассмотрим постановку задачи планирования при классических допущениях в терминах STRIPS.

Постановка задачи STRIPS-планирования


Как и выше, фактом будем называть замкнутую атомарную формулу языка исчисления предикатов 1-го порядка (ИПП), а состоянием – некоторое множество фактов. Неформально, состояние представляет модель среды, в которой действует интеллектуальный агент.

Приведём пример описания среды в терминах STRIPS:


s = {ATR(a), AT(B,b), AT(C,c), uxy ((AT(u,x)  (x ≠ y))  ¬AT(u,y)) }


Здесь, ATR(a) означает, что "робот находится в комнате a", AT(B,b) – "ящик B находится в комнате b", AT(C,c) – "ящик C находится в комнате c". Имена конкретных объектов из этого множества: 'a', 'b', 'c' – соответственно 'комната a', 'комната b', 'комната c'; 'A', 'B', 'C' – соответственно, 'ящик A', ' ящик B', 'ящик C'.

Действия агента будем описывать с помощью правил, при этом, для упрощения таких описаний, примем некоторые соглашения.

При описании STRIPS-задачи планирования как в множествах добавляемых, так и в множествах удаляемых фактов будем использовать лишь атомарные формулы без функциональных символов.

Пример правила.

Имя правила: Push (x, y, z)

Условие: C(R) = {ATR (y), AT(x, y)}

Список добавлений: A(R) = {ATR (z), AT(x, z)}

Список удалений: D(R) = {ATR (y), AT(x, y)}


В приведённом примере STRIPS-правило Push (x, y, z) описывает действие робота по перемещению ящика x из комнаты y в комнату z. Здесь, x, y, z – переменные.

Выполнение агентом действия сводится к применению правила. Применение правила модифицирует состояние s.

Определение применимости правила было приведено в Главе 1.

.Применение правила R преобразует состояние s в s' следующим образом:

s' = (s \ (D(R)))  (A(R))).

Это преобразование обозначается так: , где через θ обозначена подстановка элементов предметной области вместо переменных.


STRIPS-допущение

При применении некоторого правила R к состоянию s выполнимость факта fs изменяется, только если факт f описан либо в списке удалений D(R), либо в списке добавлений A(R).

Технически, при проверке применимости некоторого правила R, STRIPS выполняет полную подстановку на места всех переменных индивидов предметной области. Возможны различные варианты подстановок. Некоторые варианты подстановки могут давать примеры правил, применимых (или же неприменимых) в состоянии s. Однако, в алгоритм STRIPS можно внести незначительные модификации для применения неполностью означенных правил. В этом случае, в состоянии S появились бы факты с переменными в описании. Как будет видно далее, неполная подстановка активно используется планировщиками в пространстве планов. Соответствующее свойство этих планировщиков получило название малого связывания (least commitment).

Приведем постановку задачи STRIPS-планирования.

Определение 9.1. Будем называть доменом планирования P = 0, ΣR>, где s0 – начальное состояние, ΣR – конечное множество правил.

Определение 9.2. Будем называть задачей планирования T = , где G –описание целевого факта агента, или просто цель.

Решение задачи планирования T заключается в нахождении плана, который достигает цели G.


Определение 9.3. План Plan – это последовательность состояний s0, …, sn, последовательность правил R1, …, Rn, и последовательность подстановок 1,…, n, такая что, G выполнима в sn. Длина плана Plan равна n.


1   2   3   4   5   6   7   8   9   10   11

Похожие:

Конспект лекций по дисциплине «Системы искусственного интеллекта» iconКонспект лекций по дисциплине "Программное обеспечение интеллектуальных систем". Для магистров специальности 5А521902
Целью данного курса является приобретение знаний по разработки и реализации основных элементов систем искусственного интеллекта
Конспект лекций по дисциплине «Системы искусственного интеллекта» iconЛабораторная работа №1 по дисциплине “Системы искусственного интелекта
Исчисление предикатов первого порядка является теоретической основной множества формализмов методов искусственного интеллекта. Задачи...
Конспект лекций по дисциплине «Системы искусственного интеллекта» icon«шаг за шагом» создание искусственного интеллекта гашева Светлана
Интеллект рассматривают как прикладную область исследований, связанных с имитацией отдельных функций интеллекта человека [6]. Распознавание...
Конспект лекций по дисциплине «Системы искусственного интеллекта» iconУчебно-методический комплекс по дисциплине “основы искусственного интеллекта”
...
Конспект лекций по дисциплине «Системы искусственного интеллекта» icon«Основы искусственного интеллекта»
Рабочая учебная программа по дисциплине «Основы искусственного интеллекта» для ооп «050100 Физика и информатика по циклу б в. 13...
Конспект лекций по дисциплине «Системы искусственного интеллекта» iconРабочая программа дисциплины «Системы искусственного интеллекта»
Рабочая программа основана на требованиях Федерального государственного стандарта высшего профессионального образования по направлению...
Конспект лекций по дисциплине «Системы искусственного интеллекта» iconУчебно-методический комплекс по дисциплине “основы искусственного интеллекта” для специальности
...
Конспект лекций по дисциплине «Системы искусственного интеллекта» iconУчебно-методический комплекс по дисциплине “основы искусственного интеллекта” для специальности
...
Конспект лекций по дисциплине «Системы искусственного интеллекта» iconВ. К. Финн к структурной когнитологии: феноменология сознания с точки зрения искусственного интеллекта
Ки и искусственного интеллекта – полигона экспериментальной проверки научных средств имитации рациональности и продуктивного мышления....
Конспект лекций по дисциплине «Системы искусственного интеллекта» icon1. интеллектуальные системы
Системы искусственного интеллекта, решающие задачи по обработке знаний и при этом проявляющие черты, сходные с чертами естественного...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница