Разработка медицинского автоматизированного манипулятора

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Исследовательский раздел

1.1 Постановка задачи управления информационно робототизированным комплексом, как задачи интеллектуального планирования

1.2 Анализ методов интеллектуального планирования

1.2.1 Хронология подходов интеллектуального планирования при классических допущениях

1.2.2 Планирование как доказательство теорем

1.2.3 Поиск в пространстве состояний

12.4 Поиск в пространстве планов

1.2.5 Планирование как задача удовлетворения ограничений

1.3 Постановка задачи

2. Специальный раздел

2.1 Архитектура комплекса инструментальных средств управления роботизированным комплексом

2.1.1 Архитектура инструментальных программных средств

2.1.2 Средства представления знаний

2.1.3 Средства моделирования целенаправленного поведения

2.2. Разработка алгоритмов планирования

2.2.1 Описание задачи планирования

2.2.2 Взаимовлияния действий: конфликты и согласия

2.2.3 Минимальные планы бесполезные действия

2.2.4 Планирование на основе преобразования взаимовлияний

2.2.5 Планирование на основе полного разрешения конфликтов

2.2.6 Планирование за конечное время

2.2.7 Эффективность алгоритма TCRPA

2.3 Требования к интерфейсу

2.3.1 Интерфейс системы

2.3.2 Входные и выходные данные

3. Технологический раздел

3.1 Информационное обеспечение

3.1.1 Представление данных

3.1.2 Требования к информационному обеспечению

3.2 Программное обеспечение

3.2.1 Требования к программному обеспечению

3.2.2 Выбор языка программирования

3.3. Техническое обеспечение

4. Безопасность жизнедеятельности

4.1 Анализ вредных факторов при работе на клавиатуре ПЭВМ

4.2 Разработка мероприятий обеспечивающих снижение вредных факторов воздействующих на запястные каналы рук

4.2.1 Эргономика клавиатуры

4.2.2 Рациональная работа на клавиатуре

4.2.3 Рациональный режим труда и отдыха

4.2.4 Комплекс упражнений

4.3 Экологическая оценка материалов используемых в компьютерной технике (германий, платина, палладий, гадолиний, галий)

4.3.1 Экологическая оценка германия

4.3.2 Экологическая оценка галия и гадолиния

4.3.3 Экологическая оценка платины и палладия

5. Организационно экономический раздел

5.1 Планирование разработки программного продукта с построением графика

5.1.1 Определение трудоемкости и продолжительности работ по созданию ПП

5.1.2 Построение ленточного графика проведения исследования

5.2 Расчет сметы затрат на разработку программного продукта

5.3 Расчет технико-экономических показателей и эффективности использования программного продукта

5.3.1 Определение трудоемкости обработки информации по базовому и проектному вариантам

5.3.2 Расчет капитальных вложений

5.3.3 Расчет годовых текущих затрат

5.3.4 Расчет показателей экономической эффективности

Заключение

Список использованных источников



Введение

При рассмотрении проекта «Разработка медицинского автоматизированного манипулятора», возникла необходимость разработки системы управления.

В исследовательском разделе проводится анализ методов интеллектуального планирования. Эти методы рассматривают различные подходы к системам планирования целью которых является выполнение определённой задачи.

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

Технологический раздел посвящён описанию требований выдвигаемых к программной реализации информационно робототизированного комплекса. Выбирается язык программирования на котором необходимо разрабатывать систему. Описываются необходимые аспекты исследования предметной области. Также описывается структура представления данных. Выдвигаются требования к комплексу аппаратных составляющих комплекса.

В организационно-экономическом разделе сделаны выводы, о том, что данный проект является экономически целесообразным.

В разделе «Безопасность жизнедеятельности» будет рассмотрен анализ вредных факторов при работе на клавиатуре ПЭВМ, и проведена разработка мероприятий обеспечивающих снижение вредных факторов воздействующих на запястные каналы рук. А так же дана экологическая оценка материалов используемых в компьютерной технике, а именно для германия, платины, палладия, гадолиния, галия.



1. Исследовательский раздел

1.1 Постановка задачи управления информационно робототизированным комплексом, как задачи интеллектуального планирования

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

Планирование является основой интеллектуального управления, т.е. управления изменением среды в желаемом направлении. Работы по созданию эффективных алгоритмов синтеза плана уже около 35 лет сохраняют высокую степень актуальности в искусственном интеллекте, что привело в последние годы к появлению достаточно интересных результатов.

В задаче планирования можно выделить две фундаментальные составляющие - среда и агент:

1) Среда. Для построения плана и управления его выполнением необходимо построить формальное описание (модель) среды. Основные
способы, используемые для описания среды, базируются на таких методах
представления знаний, как продукционные системы, логические методы,
семантические сети, фреймовые структуры.

2) Агент - аппаратная или программная система, обладающая следующими свойствами:

автономность -- способность работать без внешнего управляющего воздействия;

реактивность - возможность воспринимать среду, реагировать на ее

изменения;

активность - способность ставить цели и инициативно действовать для достижения поставленной цели;

коммуникативность -- способность взаимодействовать с другими агентами (или людьми).

Примером интеллектуального агента является софтбот (программный
робот) - система, взаимодействующая с компьютерной средой
посредством выполнения команд и интерпретации результатов команд и других сообщений среды.

План - последовательность действий, формируемая агентом, исходя из общих целей, информации о текущем состоянии среды и динамике её изменения. медицинский автоматизированный манипулятор

Сложность задачи синтеза плана зависит от множества свойств среды и агента, в том числе:

Изменяется ли среда только в результате действий агента или вне зависимости от них;

Является ли состояние среды полностью или частично известным;

Достаточно ли датчиков агента для того, чтобы получить состояние среды;

Оказывают ли действия агента детерминированное или же
стохастическое воздействие на состояние среды.

Первый случай планирования возникает, когда среда статична (изменения в ней возникают лишь в результате действий агента) и состояние полностью известно, а действия агента производят детерминированное воздействие на состояние среды. Синтез плана для этих условий называется задачей планирования при классических допущениях.

Трудность разработки эффективного алгоритма планирования объясняется вычислительной сложностью задачи планирования, которая относится к классу PSPACE-полных задач. Более подробно об этом сказано в разделе 1.2.4.

Ещё один важный момент состоит в том, что работы в области планирования при классических допущениях способствуют пониманию проблем планирования с неклассическими допущениями, которое более адекватно задачам реального уровня сложности.

1.2 Анализ методов интеллектуального планирования.

1.2.1 Хронология подходов интеллектуального планирования при классических допущениях

На рисунке 1. представлена хронология подходов к решению задачи интеллектуального планирования при классических допущениях.

Рисунок 1 - Хронология подходов классического планирования

Начало исследованиям в области планирования положено работами [26,41,40, 25], в которых планирование рассматривалось как доказательство теорем.

Системам на основе доказательства теорем был присущ ряд недостатков. Наиболее существенными из них являлись: 1) крайне низкая производительность, 2) проблема фрейма.

Эти недостатки привели к созданию подходов, основанных на поиске в пространстве состояний [24, 49, 38,16].

Алгоритмы на основе поиска в пространстве состояний в некоторых случаях оказались негибкими, и в новом поколении методов задача планирования была сформулирована как поиск в пространстве частично-упорядоченных планов [20, 22, 34, 42].

Одновременно с развитием идеи частичных планов развивалась идея иерархического планирования [47, 46, 55], которое подразумевает создание планировщиком иерархии абстракций (подцелей). Это упрощает процедуру планирования -- вначале создается план в общих чертах, затем выполняется детализация -- спуск по иерархии. Это позволяет сосредочить вычислительные мощности на решении первостепенных задач. Иерархическое планирование также интересно тем, что лишь на основе этого подхода создано большинство реально работающих систем [51, 54].

Иерархическое планирование возможно как при поиске плана в пространстве состояний [46], так и при поиске планов в пространстве планов [47].

В начале 90-х годов, в связи с появлением высокопроизводительных алгоритмов решения задачи удовлетворения ограничений (CSP-задача), задачи проверки истинности в пропозициональной логике (SAT-задача), стала популярной постановка задачи планирования как CSP-задачи [17] и как SAT-задачи [31]. Это позволило значительно повысить скорость синтеза планов. Одновременно с этим появились работы, в которых задача планирования рассматривалась как задача целочисленного линейного программирования (ILP-задача) [33] или как задача построения бинарных диаграмм решений (BDD-задача) [48, 21].

Начиная с 1998 года, стали появляться первые планировщики, использующие эвристики для поиска плана [18, 27, 30, 44]. Конечно же, использование эвристик для решения задач не является свежей идеей. Но лишь недавно появились механизмы автоматизированного извлечения эвристик из описания домена планирования. В значительной степени, этому способствовало выделение некоторых свойств структур, используемых алгоритмами Graphplan и Satplan.

В разделах 1.2.3-1.2.6 будут подробнее рассмотрены некоторые подходы к решению задачи планирования при классических допущениях на примерах работы конкретных алгоритмов.

1.2.2 Планирование как доказательство теорем

Одним из примеров системы доказательства теорем, использовавшейся для решения задачи планирования, является система QA3 [26].

В системе QA3 одно множество утверждений использовалось для описания начального состояния, а другое - для описания эффектов действий. Чтобы следить за тем, какие факты являются истинными и в каком состоянии, в каждый предикат включаются переменные, отвечающие состоянию. Целевое условие описывалось формулой с переменной, связанной квантором существования.

Задача системы состоит в том, чтобы доказать существование состояния, в котором истинно целевое условие. В основе доказательства лежит метод резолюций [45].

Эксплуатация QA3 показала, что вывод в такой системе получается очень медленным.

Кроме того, для неё не существовало сколько-нибудь приемлемого решения проблемы фрейма [43]. Суть этой проблемы состоит в том, что действие может иметь нелокальный эффект, т.е., в общем случае, не ясно какие формулы, описывающие состояние системы, изменяются при применении действия. Это, приводило к тому, что в описание действия включались утверждения об изменении (не изменении) каждого факта, представленного в состоянии. Очевидно, что в сложных предметных областях описание эффектов действия значительно усложняется. Достаточно элегантное решение проблемы фрейма предложено в [7].

1.2.3 Поиск в пространстве состояний

Первым планировщиком, осуществляющим планирование в пространстве состояний, является STRIPS (STanforci Research Institute Problem Solver) [52].

STRIPS изначально разрабатывался для решения задачи формирования плана поведения робота, перемещающего предметы через множество помещений.

Идея алгоритма STRIPS заимствована из системы GPS (General Problem Solver), разработанной для доказательства теорем [41]. Метод, использованный в GPS, назывался «анализ средств и целей» (Cneans-ends analysis). Он подразумевает рассмотрение тех действий в текущем состоянии, которые имеют отношение к цели. Однако при таком подходе возникает следующая проблема: применять ли действия связанные с целью сразу же, как только они найдены или же приостановить применение действия пока не будут найдены все действия имеющие отношение к цели. STRIPS применяет действия сразу, достигая каждой цели по отдельности.

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

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

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

Пусть L - язык исчисления предикатов 1-го порядка (ИППП). Факт f некоторая правильно построенная замкнутая формула L. Состояние s - некоторое множество фактов.

По сути, состояние s - это эрбрановская интерпретация множества фактов. Таким образом, каждый факт из s выполним или невыполним в s, в соответствии с обычным определением понятия выполнимости в ИППП.

Неформально, состояние представляет модель среды, в которой действует агент.

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

s = {ATR(a), AT(B,b), АТ(С,с), uxy ((AT(u,x) (x у)) ? AT(u,y)) }

Здесь, ATR(a) означает, что "робот находится в комнате а", АТ(В,Ь) -"ящик В находится в комнате b", АТ(С,с) - "ящик С находится в комнате с", последняя сложная формула -- "один объект не может находиться в разных местах", х, у, и - переменные в области значений, охватывающей доступное множество объектов. Имена конкретных объектов из этого множества: 'а', b', 'с' - соответственно 'комната а', 'комната b', 'комната с'; 'А', 'В', 'С -соответственно 'ящик А',' ящик В', 'ящик С.

Действия агента описываются с помощью правил.

Правило R-это <C,A,D>, где С - предусловие правила, А -список добавлений, D - список удалений.

Предусловие С описывает множество фактов, которые должны быть выполнимы в состоянии s перед применением правила R. Список удалений D описывает множество фактов удаляемых из s при применении правила R. Список добавлений А описывает множество фактов, добавляемых в s при применении правила R.

Как оказалось, такое описание действий без дополнительных ограничений приводит к некоторым трудностям.

Во-первых, при описании правила R затруднительно или невозможно явно выразить все удаляемые факты в различных случаях применения R. Поэтому в STRIPS принято такое ограничение, что в списке удалений выражаются лишь атомарные факты. При этом после применения правила контролируется выполнимость сложных фактов из s, которые содержат в своём описании удалённые атомарные формулы. Однако, как показано в [35] это не уберегло STRIPS от некорректностей. Оказывается, для списка добавлений А также необходимо было ввести подобное ограничение. Вместе с тем, в предусловии сложные факты могут фигурировать.

Во-вторых, если в описании- домена планирования допустимы функциональные символы, то это приводит к полуразрешимой задаче планирования, так как в множество фактов в s может быть добавлено потенциально бесконечное количество формул [20].

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

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

Имя правила: Push (х, у, z);

Предусловие: C(R) = {ATR (у), АТ(х, у)};

Список добавлений: A(R) = {ATR (у), АТ(х, у)};

Список удалений: D(R) = {ATR (z), АТ(х, z)};

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

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

Правило R -применимо в состоянии s, если С выполнимо в s, где С - предусловие правила R, - подстановка на место каждой переменной в правиле R некоторых констант.

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

Это преобразование обозначается так: S S. можно видеть использование STRIPS-допущения для решения проблемы фрейма.

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

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

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

Будем называть доменом планирования Р = <, R>, где , - начальное состояние, R -- конечное множество правил.

Будем называть задачей планирования Т = <Р, G>, где G -описание целевого факта агента, или просто цель.

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

План Plan- это последовательность состояний , …, s_n, последовательность правил

, ..., , и последовательность подстановок ,..., , такая что, G выполнима в s_n. Длина плана Plan равна n.



Plan:

Опишем сам алгоритм STRIPS (Рисунок 2).

Изначально на вход алгоритма STRIPS подаётся множество правил R, начальное состояние So, цель G.

Будем полагать, что в множестве R. все правила полностью конкретизированы.

Рисунок 2 - Алгоритм STRIPS

Вначале в стек целей помещается главная цель G.

Если цель не является простой, т.е. содержит конъюнкцию литералов, то система STRIPS добавляет в стек в некотором порядке каждый из литералов составной цели (п. 1.1). Когда верхняя цель стока является однолитераьной,

система ищет действие (п. 1.2), которое содержит в списке добавлений литерал, сопоставимый с этой целью. Если такое действие не применимо к текущему состоянию, тогда его предусловие помещается в стек целей, иначе действие применяется к текущему состоянию (п. 1.5.) и помещается в план (plan). Если верхняя цель в стеке соответствует текущему состоянию, то она удаляется из стека. Алгоритм STRIPS завершается, когда стек пусть.

Существуют задачи, для которых STRIPS либо не может построить план, либо находит не минимальный план.

Причина этого кроется в том, что STRIPS удовлетворяет каждую компоненту составной цели по отдельности, без учёта их взаимосвязи. Особенность предметной области, где цели взаимосвязаны (взаимодействуют) получила название взаимосвязи целей.

Впервые некорректность STRIPS 'a была вскрыта в 1973 году Аленом Брауном в Массачусетском технологическом институте. Браун попытался решить задачу, рассматриваемую в этом разделе на планировщике HACKER. HACKER был создан Джеральдом Суссманом на основе планировщика STRIPS, поэтому задача получила название аномалия Суссмана (Sussman Anomaly).

Рассмотрим аномалию Суссмана [49].

Дано:

Объекты:

3 кубика - А, В, С.

Состояние описывается предикатами:

ontable (х) - кубик х на столе,

clear (х) - над кубиком х пусто,

handempty - рука агента пуста,

holding (х) - рука агента держит кубик х,

on (х,у) - кубик х находится на кубике у.

х, у -переменные.

Правила:

Rl: pickup (x) - поднять кубик со стола

С (Rl): ontable (х) & clear (х) handempty

A (Rl): holding (х)

D (Rl): ontable (х), clear (х), handempty R2: putdown (x) -- опустить кубик на стол

С (R2): holding (х)

A (R2): ontable (х), clear (х), handempty

D (R2): holding (х)

R3: stack (х,у) - положить кубик на другой кубик

C(R3): holding (х) & clear (у)

A(R3): handempty, on (x,y), clear (x)

D(R3): holding (x), clear (y)

R4: unstack (x,y) - снять кубик с другою кубика

C(R4): handempty & on(x,y) & clear (x)

A(R4): holding (x), clear (y)

D(R4): handempty, on(x,y), clear (x)

Начальное состояние s₀ и цель G изображены на рис.3.

Таким образом, цель G= {On (А,В) & On (В,С)}.

Поскольку цель G является составной, то STRIPS расщепляет её на отдельные компоненты - On (А,В) и On (В,С), которые помещаются в стек и удовлетворяются по очереди.

Рисунок 3 - Аномалия Суссмана

Положим, что On (А,В) наверху стека, тогда планировщик находит следующую последовательность правил для удовлетворения On (А,В):



UNSTACK(C,A), PUTDOWN(C), PICKUP(A), STACK (A,B).

Применяет найденную последовательность к состоянию So. Получается ситуация, изображённая на рис.4, в которой On (А,В) выполнима. Цель On (А,В) удаляется из стека целей. On (А.В) удовлетворено.

Далее, из ситуации на рисунке 4 , удовлетворяется следующая цель в стеке - On (В,С). В результате имеем: UNSTACK(C,A), PUTDOWN(C), PICKUP(A), STACK (A,B), UNSTACK(A.B). PUTDOWN(A) PICKUP(B), STACK (B.C).

Рисунок 4 - Удовлетворение первой цели

Применяем последовательность подчёркнутых правил. И, получаем ситуацию на рисунке 5. Цель On (В,С) удовлетворена и удаляется из стека. Однако цель Оn(А,В), удовлетворённая на предыдущем этапе, перестает быть выполнимой.

И, поэтому, теперь планировщик пытается из ситуации на рисунке 5 удовлетворить On (А,В). Это приводит к добавлению ещё двух правил к имеющейся последовательности.



Рисунок 5 - Удовлетворение второй цели

В результате получаем план:

UNSTACK(C,A), PUTDOWN(C),

PICKUP(A), STACK (A,B), UNSTACK(A,B), PUTDOWN(A), PICKUP(B),STACK (B,C), PICKUP(A), STACK (А.В)

Подчёркнутые правила применяются. Цель On (А,В) & On (В,С) достигается. План построен.

Однако существует другой план, содержащий меньше действий:

UNSTACK(C,A), PUTDOWN(C), PICKUP(B), STACK (B,C), PICKUP(A), STACK(A,B)

Рассмотрим вычислительную сложность задачи STRIPS-планирования.

Описание задачи классического планирования в терминах STRIPS допускается любым планировщиком. Поэтому рассмотрим вычислительную сложность задачи STRIPS-планирования [23,17, 22].

Далее будем рассматривать случай разрешимой задачи планирования, вычислительная сложность которой (таблица 1), варьируется от постоянного времени до EXPSPACE-полноты в зависимости от ограничений, накладываемых на язык домена, планирования Р.

Таблица 1 - Вычислительная сложность задачи планирования

предикаты не содержат функциональные символы	не априорно	есть	есть/нет	1	ExpSpase-полна	NExpTime-полна
		нет	есть	2	NExpTime-полна	NExpTime-полна
			нет	3	ExpSpase-полна	NExpTime-полна
			нет	4	Pspace-полна	PSpace-полна
	априорно	есть	есть/нет	5	Pspace	PSpace
		нет	есть	6	NP	NP
			нет	7	P	NP
			нет	8	NLogSpace	NP
Все предикаты 0-местные	не априорно	есть	есть/нет	9	PSpace-полна	PSpace-полна
		нет	есть	10	NP-полна	NP-полна
			нет	11	P	NP-полна
			нет	12	NLogSpace-полна	NP-полна
	априорно	есть/нет	есть/нет	13	постоянное время	постоянное время

Примечания:

1)Действия имеют не более чем одно предусловие.

2) Для некоторых множеств .

Пояснения к таблице 1:

в графе "ограничения языка" описаны ограничения, накладываемые на язык L домена планирования Р;

в графе "как заданы действия" -- "априорно" означает, что множество R в задаче планирования Т фиксировано, а параметрами являются s₀ и G;

в графе "существование плана" представлена вычислительная сложность следующей задачи: "Существует ли для задачи планирования Т= <s₀, R, G> план, который достигает цели G?";

в графе "существование плана длиной k" представлена вычислительная сложность следующей задачи: "Существует ли для задачи планирования Т= < s₀, R, G> и заданного целого числа к, план длиной меньшей либо равной к, который достигает цели G?"

Заметим, что задача "существование минимального по длине плана", как минимум, равна по сложности "задаче существовании плана длиной k".

Рассмотрим, каким образом входные параметры задачи планирования влияют на её сложность.

Если нет никаких ограничений на описание домена планирования Р, тогда любое конкретизированное действие может появиться несколько раз в плане. Количество конкретизированных действий экспоненциально. Размер каждого состояния в худшем случае является экспоненциальным. Таким образом, пространство состояний в котором необходимо осуществить поиск также экспоненциально. Это приводит к тому что, задача "существование плана" EXPSPASE-полна (строка 1).

(2) Если все действия имеют пустой список удалений (строка 2), тогда каждый факт, добавленный в состояние, остаётся истинным при последующих преобразованиях. Следовательно, нет необходимости использовать одно и то же действие дважды в одном плане. А поскольку, число полностью конкретизированных действий экспоненциальной длины. Таким образом, сложность планирования снижается до NEXPTIME-полноты.

Если дополнительно к ограничениям в пункте (2) добавить ограничения на предусловия, так чтобы они не содержали негативных атомов (строка 3), тогда порядок действий в плане не имеет значения. Это снижает сложность задачи "существование плана" до EXPTIME-полноты. Однако, для задачи "существование плана k" сложность не снижается и остается NEXPTIME-полной (строка 1), так как из-за константы k приходится перебирать всё множество последовательностей длины к.

Если предусловие действия содержит не более одного литерала (строки 4, 8, 12), тогда использование техники обратного поиска позволяет снизить сложность планирования, так как количество подцелей в этом случае не увеличивается. В этом случае сложность варьируется от NLOGSPACE до PSPACE-полноты.

Все соображения, изложенные в пунктах 1-4 также справедливы для случая ограничения языка домена планирования Р нульместными предикатами (строки 9-13). Кроме того, заметим, что для этого случая, мощность |R|, а также размер любого состояния s, снижается с экспоненциального до полиномиального. Естественно, что планирование в этом случае существенно легче, чем в случае допущения k-местных предикатов. В общем случае, снижение сложности планирования можно добиться за счёт ограничения местности предиката некоторой постоянной j. При этом нульместное ограничение соответствует случаю, когда j=0.

(6) Когда множество действий R задано априорно, то местность
предикатов и количество переменных в каждом действии постоянно. В этом
случае сложность планирования снижается и варьируется в пределах от const до
PSPACE-полноты (строки 5,6.7,8,13).

Необходимость описания и решения задач в более сложных доменах привело к появлению языка описания действий ADL (Action Description Language), являющегося расширением STRIPS-языка. ADL позволяет выражать условные эффекты действий (эффекты, которые применяются только тогда, когда дополнительные условия истинны в момент применения действия), квантифицированные эффекты (эффекты применяются к группе объектов вместо одного), в предусловиях стало возможным выражать дизъюнкции, квантифицированные формулы, и прочие логические связки.

Одним из первых планировщиков, который поддерживал расширенный синтаксис языка ADL, являлся UCPOP.

1.2.4 Поиск в пространстве планов

Первым подобным планировщиком являлся NOAH (Nets Of Action Hierarchies) [97]. NOAH строил оптимальный план для аномалии Суссмана.

В 1991 году МакАлистер и Розенблитт [37] доказали полноту SNLP -алгоритма частично-упорядоченного планирования, что во многом предопределило направление дальнейших исследований.

Начнём с примера, демонстрирующего особенности частично-упорядоченных планов.

Пусть, агенту необходимо выполнить несколько задач в комнате А, и несколько задач в комнате В (рисунок 6.)

Рисунок 6 - Иллюстрация к частично упорядоченным планам

Агент способен выполнять:

действия Aj, ..., A_n, , ..., B_m, которые доставляют, соответственно, факты (і l...n) и (j l..m). Предусловие C() = IN(A), предусловие C() = IN(B).

действие GO (А), которое не имеет предусловий, но имеет в списке добавлений IN(A), а в списке удалений IN (В);

действие GO(B), которое не имеет предусловий, но имеет в списке добавлений IN(B), а в списке удалений IN (А).

Необходимо достичь цели G = {Р_b ..., P_n, ,..., Q_m}. Очевидно, что цель G может быть достигнута после исполнения плана

Plan = {GO(A); ; ...; A_n; GO(B); ; ...; B_m}.



Заметим, что порядок выполнения действий , и порядок выполнения действий не имеет значения, поскольку они выполняются в разных комнатах. Следовательно, план {GO(A), А_n;...; А₁, GO(B), B_m,...; } будет эквивалентен вышеприведённому плану.

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

Введём несколько базовых определений для описания алгоритма SNLP.

Шаг плана - это пара <№, R>, где № - уникальный номер шага, R -- некоторое правило.

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

В SNLP нелинейный план изначально всегда содержит два шага: 1) стартовый - START, соответствующий правилу, которое имеет список добавлений, задающих множество начальных фактов (начальное состояние среды), но не имеет предусловий и списка добавлений, и 2) конечный - FINISH, соответствующий действию, которое в качестве предусловий имеет целевые формулы, но не имеет списка добавлений и списка удалений.

Причинная связь - это тройка <S, f, W>, где f - некоторый факт, W - шаг, имеющий в предусловии атом f, S - шаг, имеющий факт f в списке добавлений.

Угроза V для причинной связи <S, f, W> -это шаг, который либо добавляет, либо удаляет факт f, и при этом не является ни шагом S, ни шагом W.

Защитное ограничение - это отношение порядка "<", заданное на шагах плана, при этом S<W означает, что шаг S должен быть

выполнен до шага W, и наоборот, S>W означает, что шаг S должен быть выполнен после шага W.

Нелинейный план Plan = <ST, CL, SO>, где ST-множество шагов, CL -- множество причинных связей, SC -- множество защитных ограничений.

Топологическая сортировка нелинейного плана Plan - это линейная последовательность всех шагов, которая удовлетворяет следующим условиям:

первый шаг в последовательности - START;

последний шаг в последовательности -- FINISH;

для каждой причинной связи <S, f, W> шаг S в последовательности предшествует шагу W;

для каждого защитного ограничения U<V шаг U в последовательности предшествует шагу V.

Топологическая сортировка нелинейного плана является решением, если применение последовательности действий шагов между шагами START и FINISH из начального состояния, которое задаётся списком добавлений шага START, приводит в состояние, в котором содержатся все предусловия шага FINISH.

8) Нелинейный план является противоречивым, если на нём невозможно осуществить топологическую сортировку.

Из этого следует, что противоречивый нелинейный план не является решением задачи планирования.

Алгоритм SNLP является систематичным в том смысле, что в процессе поиска, осуществляемого в пространстве частично-упорядоченных планов, один и тот же план или эквивалентные планы никогда не рассматриваются дважды.

Опишем алгоритм SNLP (рисунок 7.)

На вход процедуры подаётся множество правил УR, а также,

нелинейный план Plan, не обладающий полнотой, который содержит шаги START и FINISH. Далее Plan уточняется путём добавления причинных связей и защитных ограничений, до тех пор, пока не обнаружится такое уточнение, что план либо противоречив, либо обладает полнотой.

Для случая абстрактного планирования, приведённая процедура может быть расширена следующим образом. Необходимо создать иерархию утверждений, которая будет отражать трудность достижения тех или иных условий. Для этого каждому утверждению сопоставляется некоторое число, характеризующее его иерархический уровень. Малые числа могут указывать на низкий уровень иерархичности, большие числа - на высокий уровень иерархичности. Для того чтобы процедура удовлетворяла предусловия, спускаясь с вершины иерархии утверждений, в процедуре SNLP на шаге 3 и 4 можно осуществлять выполнение пунктов а) и b), не произвольным образом, а с учётом более иерархичного предусловия f вовлечённого в причинную связь.

Рисунок 7 - Алгоритм SNLP



Очень часто нелинейные планировщики называют планировщиками, обладающими малой связностью (least commitment).

Неформальный принцип малой связности утверждает, что планировщику следует всегда осуществлять сначала выбор таких действий, которые его меньше связывают. Частичная подстановка - один из примеров малого связывания. Так, при поиске плана можно начать с анализа последствий более конкретного действия, например, MOVE (A, В), а можно выбрать менее связывающее действие, например, MOVE (А, х), где х -- некоторая переменная, вместо которой можно подставить любой объект. Нелинейность ещё один пример малого связывания, например, можно выбрать действие Put (А, х) в качестве первого шага плана, с другой стороны, мы можем предположить что Put (А, х) появляется где-то в середине плана без точного указания места.

Однако принцип малой связности не гарантирует нелинейным планировщикам значительного превосходства над линейными .

1.2.5 Планирование как задача удовлетворения ограничений

Многие задачи в ИИ, а также в других областях информатики, могут

быть рассмотрены как задачи удовлетворения ограничений [34, 39], для которых существует множество высокопроизводительных алгоритмов. В связи с этим стала популярной формулировка задачи планирования, как задачи удовлетворения ограничений [28, 32, 17].

CSP-задача предъявляет требования к переменным в форме ограничений. Множество возможных значений переменных конечно, и называется доменом. Ограничения указывают, какие кортежи значений допустимы для определённого множества переменных. Ограничение может быть задано явно, путём перечисления допустимых кортежей или неявно, в форме алгебраического выражения. Решением CSP-задачи является такое означивание переменных, при котором учтены все ограничения.

Задача удовлетворения ограничений -- это тройка <V, D, С>, где:

V = {,..., v_n} -множество переменных.

D = {D₁..., D_n} -- множество доменов. Каждый домен D; -- конечное множество, содержащее возможные значения, соответствующей переменной.

С = {,..., } - множество ограничений. Ограничение С - отношение, определённое на подмножестве всех переменных, то есть x...xD_n .

Заданное (частичное или полное) означивание переменных удовлетворяет ограничению Q, если каждая переменная получила такое значение, что соответствующий кортеж значений принадлежит . Множество всевозможных означиваний всех переменных является пространством, содержащим решение CSP-задачи.

Решением CSP-задачи является такое означивание всех переменных, при котором все ограничения удовлетворены. Если для некоторой задачи имеется, по крайней мере, одно решение, то задача является разрешимой, иначе неразрешимой, или же противоречивой, или же переограниченной.

В некоторых случаях необходимо получить все решения. Иногда, может быть сформулирована задача ограниченной оптимизации, а именно: найти такое решение, в котором значения переменных оптимизировали бы некоторый заданный функционал. Иногда необходимо просто выяснить, разрешима ли задача. В любом случае вычислительная сложность CSP-задачи NP-полная .

Далее рассмотрим алгоритм планирования -- Graphplan [17], который использует технику прямого распространения ограничений.

На момент своего создания (1994) Graphplan показал впечатляющие результаты для ряда тестовых задач классического планирования. По производительности он превзошёл планировщики Prodigy [53], UCPOP [42], SNLP'[37], TOCL, POCL, ТОРІ [9].

Создатели Graphplan'a Блюм и Фёст объясняют этот успех способностью Graphplan'a анализировать множество планов одновременно. Однако, как показал Камбхампати [29] производительность Graphplan'a объясняется тем, что он обрабатывает компоненты множества планов без разделения, используя уточнения дизъюнктивных планов.

Graphplan оказал сильное влияние на последующие работы в области планирования. Его алгоритм был модернизирован многими независимыми исследователями. На сегодня популярными постреализациями являются: 1) IPP (Interference Progression Planner) [33] - включена поддержка языка ADL, 2) STAN (STate ANalysis planner) [36] - повышена производительность в сравнении с GraphPlan'oM, 3) TGP (Temporal GraphPlan) [106] - добавлена возможность обработки темпоральных зависимостей, 4) SGP (Sensory) Graphplan принимает на вход стандартное STRIPS-описание задачи планирования и переводит это описание в компактную структуру, которая называется граф планирования (Planning Graf), из которой впоследствии извлекает частично-упорядоченный план. Важно отметить, что граф планирования это не граф состояний, который получается при работе планировщика в пространстве состояний.

Graphplan сочетает в себе свойства как планировщика в пространстве состояний, так и планировщика в пространстве планов. Т.е. он не обладает свойством малого связывания и при этом строит частично-упорядоченные планы.

При изложении Graphplan'a будем пользоваться терминологией из оригинальной работы [17].

Факты F -- множество элементарных ППФ без переменных из домена планирования Р.

Перед основной стадией работы Graphplan создаёт множество действий, осуществляя для каждого правила RSR всевозможные варианты подстановки индивидов на места всех переменных. Имеется также специальный вид действия 'no-op' - "ничего не делать".

Действия Acts - множество полностью конкретизированных правил из SR, а также действие 'no-op'. Действие 'no-op' имеет предусловие C('no-op')=f, список добавлений А('по-op')=f, и пустой список удалений D('no-op')=0, где f- произвольный факт из F.

Граф планирования PG - ориентированный ярусный граф с двумя типами узлов и с тремя типами рёбер.

Два типа узлов в PG таковы: 1) FN - множество узлов, ассоциированных с фактами F, и 2) AN - множество узлов, ассоциированных с действиями Acts. Ассоциацию некоторого факта fF с узлом fnPG, будем обозначать как fnf.

Ассоциацию некоторого действия act Acts с узлом anAN PG, будем обозначать как anact.

Множество узлов PG разбито на непересекающиеся подмножества <FLo, ALo, FL_1, AL₁, ... AL_n.₁ FL_n>, где FL - ярус, содержащий узлы-факты, AL - ярус, содержащий узлы-действия, FL₀ содержит узлы-факты, соответствующие фактам So-

Любой ярус AL_iPG содержит узлы-действия anact, такие что Nodes(C(actan)) FL_i и не существует fiii, fn₂ eNodes(C(act<-an)) и <fr»i, fn₂>eMXF, где Nodes(C(act<-an)) - узлы на ярусе FL_i, ассоциированные, с фактами из предусловия C(act).

Любой ярус фактов FL_iPG (i>0) содержит узлы-факты fnf, такие что, для любого an AL_iPG справедливо (fD(actan) ИЛИ fA(actan)). Рёбра устанавливаются между узлами, расположенными на ярусах. Три типа рёбер PG таковы:

ребро-предусловие - устанавливается между узлом-фактом fhf на некотором ярусе FL_i и узлом-действием anact на ярусе AL_{i ,} если факт fC(act);

ребро-добавление - устанавливается между узлом-действием an->act на некотором ярусе AL_i и узлом-фактом fhf на ярусе FL_i+1, если f A(act);

ребро-удаление -- устанавливается между узлом-действием anact на некотором ярусе AL_i и узлом-фактом fnf на ярусе FL_i+1, если f D(act).

Из определения видно, что ярусы PG чередуются так: ярус фактов | ярус действий и т.д. Первый ярус графа содержит факты, характеризующие начальное состояние. Ярусы в PG от самого первого до последнего содержат:

По сути, граф планирования PG позволяет представлять пространство состояний без разделения. Точнее, множество состояний хранящиеся совместно, например, на ярусе FL_i+1, получаются в результате всевозможных альтернативных вариантов применения действий, расположенных в ярусах AL_i по AL_j (i<j), к некоторому состоянию s, представленному на ярусе фактов FL_i. Однако, ясно, что альтернативная перестановка к действий может привести к тому, что одно из действий может удалять эффект, либо предусловие другого действия. Для обработки подобных ситуаций используются, так называемые мьютексы между действиями и мьютексы между фактами. Это позволяет при необходимости, например, на этапе извлечения плана, выделить из графа PG альтернативные компоненты пространства состояний.

Планировщики, использующие такой способ представления пространства состояний, получили название дизъюнктивных планировщиков.

Дадим формальное определение понятию мьютекс.

Мьютекс - это отношение взаимоисключения между двумя узлами на одном ярусе. Существуют мьютексы между действиями и между фактами.

Мьютексы MXF - отношения взаимоисключения между

узлами-фактами < fn₁, fn₂>, где fn₁ fn₂ - узлы-факты, находящиеся на одном

ярусе, такие, что: либо, 1) все действия на предыдущем ярусе, добавляющие факт fn₁|, удаляют факт fn₂; либо, 2) все действия на предыдущем ярусе добавляющие факт fn₂, удаляют факт fn₁.

Мьютексы МХА -- отношения взаимоисключения между

узлами-действиями <аn₁ аn₂>, где аn₁ аn₂ - узлы-действия, находящиеся на одном ярусе, такие, что: либо, 1) действие аn₁ удаляет предусловие или же эффект действия аn₂ либо, 2) предусловие действия аn₁ и предусловие действия аn₂ состоят в мьютексе mxf MXF.

Заметим, что мьютекс между парой узлов n₁ и n₂, может иметь место на некотором ярусе L, и не иметь место на некотором последующем ярусе L, С другой стороны, если между парой узлов n₁ и n₂ на некотором ярусе L не существует мьютекса, то и на последующих ярусах после L, пара узлов n₁ и n₂ не будут состоять в мьютексе.

Мьютексы превращают граф планирования в граф ограничений в смысле CSP-задачи. Метод, который используется для построения графа планирования, называется прямым распространением ограничений.

Пара ярусов фактов FL_i и FL_j - идентичны, если FL_i и FL_j содержат: 1) одинаковые факты, И 2) одинаковые мьютексы.

Граф Планирования PG является стабилизированным, если существуют пара смежных ярусов фактов FL_i и FL_i+1 и FL_j идентичен FL_i+1.

Пусть граф PG стабилизирован, и имеется пара идентичных ярусов-фактов FL_i, FL_i+1 PG. Тогда ярус фактов FL_k PG идентичен ярусу фактов FL_i PG, где k>iN.

Доказательство: Действительно, во-первых, из-за существования "nо-ор"-действий, факт f однажды появившись на некотором ярусе фактов, будет иметь место во всех последующих ярусах фактов. Во-вторых, множество фактов, которые могут быть созданы STRIPS-правилами конечно. Следовательно, должен существовать такой ярус фактов Q, содержащий факты, которые будут иметь место во всех последующих ярусах фактов. В-третьих, если два факта р и q, появившиеся на одном ярусе, не состоят в мьютексе, то и в последующих ярусах они также не будут состоять в мьютексе. Таким образом, должен существовать такой ярус фактов Р после Q, что все последующие ярусы фактов имеют множества мьютексов идентичные тем, что в Р. Утверждение доказано.

Цель G является разрешимой (достижимой) в 2-х случаях: 1) если она удовлетворяется тривиальным образом, т.е. компоненты цели G имеют место в начальном ярусе фактов, 2) если в графе PG существует подграф Plan, который состоит из множества путей, идущих от начального яруса фактов к ярусу фактов, содержащему G, и в этом множестве путей нет ни одной пары узлов, состоящих в мьютексе.

Пусть задача планирования Т имеет план длиной n . План длиной n можно извлечь из графа планирования PG, содержащего n ярусов-действий [17]. Алгоритм GraphPlan возвращает "план не существует", только если цель G не достижима [17]. Алгоритм GraphPlan обладает полнотой [17].

Опишем алгоритм GraphPlan (рисунок 8.1., рисунок 8.2.).

В начале Graphplan формирует первичный ярус фактов FL₀. Graphplan работает по стадиям (переменная t в алгоритме). В каждой стадии выполняется:

- расширение графа планирования PG,

- поиск плана в графе PG.

На этапе расширения графа PG на основе текущего яруса фактов создаётся новый ярус действий, а затем, на основе нового яруса действий, формируется новый ярус фактов. Во вновь сформированных ярусах выявляются мьютексы MXF и МХА (процедура Расширение Графа Планирования).

Graphplan строит частично-упорядоченный план. Извлечение плана осуществляется с помощью техники обратного хода от текущего яруса к начальному ярусу. Как утверждает автор Graphplan'a, эта техника позволяет более эффективно использовать информацию о мьютексах между действиями и фактами в графе PG.

Опишем эту технику.

Перед поиском плана Graphplan проверяет следующее условие: "справедливо ли, что GNcFL_TCK и для каждой пары узлов gn_{1 ,} gn₂ GN и gn₁, gn₂mxf, где GN--множество целевых фактов, ассоциированных с узлами на ярусе FL_TCK "'.

Если это так, тогда возможно план существует, и Graphplan приступает к поиску.

Суть поиска плана сводится к тому, чтобы от целевых фактов в текущем ярусе GNFL_TCK, выделить путь, ведущий к ярусу FL₀. В пути не должны содержаться мьютексные действия. На основе выделенного пути формируется план.

Более точно происходит следующее.

Изначально формируется множество GS - хранилище (под)целевых наборов GS _i ^t. GS _i ^t -- множество целей, выбираемые из яруса фактов с номером і, при поиске плана на стадии t. Начиная с текущего яруса FL_i (вначале i=t) в GS i t заносятся целевые факты GNFL_i. Далее на ярусе действий с номером і-l выделяются всевозможные комбинации действий (А_comb), доставляющие GS _i ^t (множество Comb). Устанавливается подцель GS _i-1 ^t, в которую помещаются предусловия выделенных действий, расположенные на ярусе фактов FL_m. Для каждой из комбинаций действий А_combComb процесс продолжается рекурсивно, до тех пор, пока GS _i-1 ^t окажется тривиально разрешимой, либо не найдётся комбинации действий, доставляющей GS _i-1 ^t, т.е. Comb = .

Если подцель GS _i-1 ^t оказывается разрешимой, то при возврате из рекурсии в план Plan помещаются тройки < GS _i-1 ^t, A_comb, GS _i ^t , в которой для каждого действия из A_comb, известно какие (под)цели из GS_i^t достигает действие, и какие цели из GS _i-1 ^t необходимо достичь, прежде чем выполнить действие. Для получения линейного плана необходимо выполнить топологическую сортировку нелинейного плана Plan, с учётом целевых ограничений GS_i^t.



Рисунок 8.1 - Алгоритм GraphPlan

Рисунок 8.2 - Алгоритм GraphPlan



Опишем ещё одну незначительную, но интересную особенность Graphplan'a.

В практической реализации алгоритма для повышения эффективности обратной техники извлечения плана, используется хеширование. В хеш-таблице на каждой стадии t запоминаются целевые наборы GS_i^t , которые оказались НЕ разрешимыми в ярусе фактов і. На каждой стадии при поиске плана проверяется наличие в хэш-таблице разрешаемой подцели GS _i-1 ^t . Если подцель GS _i-1 ^t в хеш-таблице, то поиск плана немедленно прекращается, и исходная цель GS_i^t, также помещается в хеш, как неразрешимая.

1.3 Постановка задачи

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

Анализ работ в области интеллектуального планирования при классических допущениях позволяет выделить следующие подходы:

1)планирование как доказательство теорем;

2)планирование как поиск в пространстве состояний;

3)планирование как поиск в пространстве планов;

4)иерархическое планирование;

5)планирование как CSP-задача, SAT-задача, ILP-задача, BDD-задача;

В качестве ключевых работ в области классического планирования следует отметить: STRIPS [24] -- решение проблемы фрейма, SNLP [37] -- доказательство полноты алгоритма частично-упорядоченного планирования, GRAPHPLAN [17] - значительное повышение производительности за счёт использования техники удовлетворения ограничений, SATPLAN [32] -- использование эффективных методов решения задачи выполнимости пропозициональных формул, HSP [18] - для повышения скорости поиска планов использована эвристика, извлекаемая из описания задачи планирования.