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

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

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.3.1 Интерфейс системы

.3.2 Входные и выходные данные

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

изменения;

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

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

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

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

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

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

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

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

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

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

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

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

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

.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 будут подробнее рассмотрены некоторые подходы к решению задачи планирования при классических допущениях на примерах работы конкретных алгоритмов.

.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), АТ(С,с), "u"x"y ((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 q-применимо в состоянии s, если Сq выполнимо в s, где С - предусловие правила R, q - подстановка на место каждой переменной в правиле R некоторых констант.

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

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

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

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

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

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

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

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

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

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

Plan:  

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

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

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

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

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

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

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

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

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

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

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

Дано:

Объекты:

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

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

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

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

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

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

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

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

Правила:

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

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

С (R2): holding (х)(R2): ontable (х), clear (х), handempty (R2): holding (х)

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

C(R3): holding (х) & clear (у)(R3): handempty, on (x,y), clear (x)(R3): holding (x), clear (y)4: unstack (x,y) - снять кубик с другою кубика

C(R4): handempty & on(x,y) & clear (x)(R4): holding (x), clear (y)(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 - Удовлетворение второй цели

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

(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)Действия имеют не более чем одно предусловие.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.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.

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

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

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

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

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

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

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

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

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

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

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

.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 создаёт множество действий, осуществляя для каждого правила RÎSR всевозможные варианты подстановки индивидов на места всех переменных. Имеется также специальный вид действия '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. Ассоциацию некоторого факта fÎF с узлом fnÎPG, будем обозначать как fn®f.

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

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

Любой ярус фактов FL_iÌPG (i>0) содержит узлы-факты fn®f, такие что, для любого anÎ AL_iÌPG справедливо (fÎD(act¬an) ИЛИ fÎA(act¬an)). Рёбра устанавливаются между узлами, расположенными на ярусах. Три типа рёбер PG таковы:

ребро-предусловие - устанавливается между узлом-фактом fh®f на некотором ярусе FL_i и узлом-действием an®act на ярусе AL_{i ,} если факт fÎC(act);

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

ребро-удаление - устанавливается между узлом-действием an®act на некотором ярусе AL_i и узлом-фактом fn®f на ярусе 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>iÎN.

Доказательство: Действительно, во-первых, из-за существования "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 проверяет следующее условие: "справедливо ли, что GNcÍFL_TCK и для каждой пары узлов gn_{1 ,} gn₂ ÎGN и gn₁, gn₂Ïmxf, где GN-множество целевых фактов, ассоциированных с узлами на ярусе FL_TCK "'.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.1 Архитектура комплекса инструментальных средств управления информационного роботизированного комплекса

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

Основным модулем динамической интеллектуальной системы (далее просто система) (рисунок 9.) является база знаний, в которой содержатся знания, планы, цели функционирования динамической интеллектуальной системы. В системе принят гибридный метод представления знаний, который сочетает системы фреймов и продукционные системы [14, 15].

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

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

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

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

) от внешнего интерфейса, например, в ходе опроса датчиков.

) от разработчика - через интерфейс разработчика.

) от пользователя - через интерфейс пользователя.

В начале работы системы, рабочая память содержит множество исходных фактов.

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

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

Рисунок 9. - Архитектура динамической интеллектуальной системы

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

Основной когнитивной структурой базы знаний является прототип.

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

Объект - сущность, обладающая свойствами и функциональным назначением. Большинство свойств объекта на протяжении большого промежутка времени не меняется. Пример: 'стул', 'стол', 'монитор', 'комната' и т.д.

Ситуация - поименованный набор элементов предметной области и отношений между ними в текущий момент времени. Пример, 'тревога', 'брак', 'пожар', 'стабильная работа', 'столкновение' и т.д.

Процесс - описание закономерностей изменения свойств объектов. Например 'подача топлива', 'вращение турбины', 'падение объекта' и т.д.

Объекты, ситуации, процессы обладают свойствами, и с ними могут быть связаны различные события. Например, свойствами объекта (ситуации, процесса) являются такие характеристики, как цвет, масса, объём, рост, длина, а событиями объекта (ситуации, процесса) - такие характеристики, как 'включен', 'выключен', 'сломан', 'нажат' и т.д. События могут быть определены на свойствах, например, событие "повышенная температура тела человека" определено на свойстве 'температура' с областью характерных значений от 38 до 42 градусов.

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

Формально прототип это:

Р = <NP, StrP>;

где NP - имя прототипа, StrP - структура прототипа

StrP: <Attr, Mark, Inst, Rel, Rule>; где Attr - множество атрибутов прототипа, Mark - множество оценок прототипа, Inst - множество примеров, Rel -множество отношений, Rule -множество правил.

Подобная структура позволяет описывать ситуацию реального уровня сложности.

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

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

Для описания прототипа с помощью других прототипов определён слот - пример прототипа. Пример является представлением конкретного объекта,
ситуации, процесса, созданного на основе прототипа. От родительского
прототипа пример наследует структурную часть.

Определены четыре категории правил:

) Правила замыкания.

) Правила переходов.

) Правила управления.

) Правила целеуказания.

Множество правил можно условно разделить на синхронные правила (категории 1, 3, 4), формирующие состояние системы s(t) на основе фактов в момент времени t, и диахронные (категория 2), формирующие состояние системы s(t+l) на основе фактов в момент времени t.

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

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

Правила целеуказания формируют множество целевых состояний системы.

Правила управления задают основные параметры управления системой для достижения целевого состояния.

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

Правила перехода и замыкания формируют динамику изменения предметной области.

Время в системе дискретно. Задаётся временная шкала Т, путём указания единицы измерения времени (с, час, сутки, дни, столетия и т.д.) и дискреты времени ∆t. Тогда состояния системы представляются как моменты времени кратные ∆t.

Перед запуском системы пользователь описывает цели системы на специальном языке. Цель содержит множество фактов, которые являются целевыми фактами. Состояние, которое содержит множество целевых фактов, называется целевым состоянием. Целевое состояние достигается в результате поиска и выполнения управления. Отсутствие управляющих воздействий рассматривается как один из вариантов управления. Целевые факты могут быть позитивными, при этом система добивается появления таких фактов, или же негативными, тогда система избегает появления таких фактов. Дополнительно можно потребовать от системы: оптимизации некоторого параметра, достижения целевого состояния за конечное время и т.д.

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

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

Схема функционирования системы такова:

Пока не достигнуты основные цели системы выполнять:

)Замыкание состояния.

)Установку текущих целей.

)Исполнение плана для достижения текущих целей.

)Переход состояния системы.

На этапе замыкания (1) на основе исходных фактов в рабочей памяти достраивается текущее состояние системы. По сути, здесь происходит выявление правил замыкания, применимых к множеству фактов в текущем состоянии, и исполнение этих правил.

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

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

На этапе перехода (3) формируется ядро следующего состояния системы, а именно, исполняется множество правил переходов, применимых в текущем состоянии, которые выводят множество фактов в следующем состоянии системы.

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

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

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

Пусть:

L - язык исчисления предикатов первого порядка;

Р = <, SR> - домен планирования;

Т = <Р, G> - задача планирования с классическими допущениями.

Введём определение. Факт f - это элементарная ППФ f из L без функциональных символов, либо отрицание f- Øf, либо дизъюнкция - fÚØf.

Далее, вместо термина "правило" будем употреблять формально-эквивалентный термин "действие".

Во избежание трудностей, введём некоторые ограничения на описание домена планирования Р:

)        для каждого действия RÎSR:

а)      предусловие C(R) задаётся множеством фактов типа f или Øf;

б)      список добавлений A(R) и список удалений D(R) задаётся множеством фактов типа f;

в) A(R)ÇD(R) = Æ.

)        Состояние s и цель G задаются множеством фактов типа f или Øf.

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

Любое действие RÎSR описано безотносительно к некоторому состоянию, к которому может быть применено. Действие RÎSR будем называть действием-прототипом.

Создадим бесконечное множество экземпляров действий А_exe. Каждый экземпляр снабдим уникальным идентификатором.

Экземпляр действия a_exeÎA_exe=<id, R>, где RÎSR -действие-прототип, которому соответствует действие-экземпляр, id -уникальный идентификатор действия-экземпляра.

Пара экземпляров действий a_exe и b_exe подобны, если соответствуют одному и тому же прототипу RÎSR. Подобие действий-экземпляров обозначим a_exe ~ b_exe .

Под проверкой применимости действия будем понимать проверку выполнимости предусловия некоторого экземпляра действия a_exeÎA_exe, соответствующего прототипу R в конкретном состоянии s.

Сформируем множество всевозможных последовательностей действий-экземпляров SEQ.

Множество SEQ - множество всевозможных
последовательностей   действий-экземпляров.         Длину некоторой последовательности seqÎSEQ обозначим через |seq|.

Отношение полного порядка, заданное на множестве действий некоторой последовательности seqÎSEQ будем называть отношением предшествования, и обозначать так: <.

Предположим, что в некоторой последовательности seqÎSEQ имеет место: a_exe <c_exe Однако, возможно, что существует действие b_exe Îseq такое, что a_exe<b_exe и b_exe<c_exe.

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

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

Введём для этих гипотетических множеств действий следующие обозначения - соответственно start и finish. Пополним множество SEQ этими действиями.

Действие start = <С=Æ, A=s₀, D=Æ>. Действие finish = <С=G, А=Æ, D=Æ>;

Добавим действие start в начало каждой последовательности множества SEQ, а finish в конец каждой такой последовательности. Последовательность (start, finish) Î SEQ будем называть начальной, и обозначать init. Нумерацию элементов последовательности seq будем вести, начиная с нуля. nÎN будем использовать для обозначения конечного элемента последовательности seq.

Таким образом, в любой последовательности seqÎSEQ начальное действие =start, конечное действие =finish. Действие start всегда применимо.

Опишем алгоритм APL применения последовательности действий seq=(a₀,..., a_i, a_i+1,..., a_n)ÎSEQ:

APL

вход: seq

выход: DM=<so, s₁ ..., s_n>

. начиная с a₀Îseq последовательно для каждого применимого действия aÎseq

применить a к s₀

На вход APL подаётся последовательность действий seq. Первое действие a₀ всегда применимо и формирует начальное состояние s₀. В результате работы APL возвращает динамическую модель среды DM - последовательность состояний <s₀, s₀, ..., s_n>, в которой каждое состояние s_t

(t=0..n) получено применением действия a_tÎseq.

Последовательность seq называется полностью применимой, если каждое действие a_tÎseq применимо. Иначе, последовательность seq называется не полностью применимой. Полностью применимая последовательность действий является решением задачи планирования Т, если состояние s_n, полученное в результате применения последнего действия a_n Î seq, является целевым состоянием, то есть GÌs_n.

Задача планирования - это задача поиска в множестве SEQ полностью применимой последовательности действий, которая преобразует начальное состояние s₀ в s_nÉ G, где G - цель задачи планирования.

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

Определения, данные в предыдущем разделе, позволяют рассмотреть

отношения между действиями в последовательности.

Взаимовлияние по факту между действиями a,χ,βÎseq, где a< χ, имеет место, если:

l)fÎΦ(a)

2)fÎΦ(χ)

3)      не существует действия βÎseq такого, что a<β<χ и (f(⌝f)Îeff(β) либо
f(⌝f)Îeff(β))

Взаимовлияние будем обозначать a⬍f⬍χ. INT(seq) - множество взаимовлияний последовательности seq.

Пара взаимовлияний int, int'Î INT(seq) подобны, если имеет место подобие фактов взаимовлияния.

Конфликт по факту f между действиями a,χÎseq - это тип взаимовлияния a⬍f⬍χ такой, что:

либо (1) fÎeff(a) & ⌝fÎpre(χ) & f ˅⌝f∉pre(χ),

либо (2) ⌝fÎeff(a) & fÎpre(χ) & f˅⌝f∉pre(χ).

Конфликт будем обозначать a↑f↓χ.

CF(seq) - множество конфликтов, в которых состоят действия последовательности seq.

Последовательность seq будем называть бесконфликтной, если CF(seq)=0.

Согласие по факту f между действиями a,χ Îseq - это тип взаимовлияния a⬍f⬍χ такой, что:

либо (1) fÎeff(a) & (fÎpre(χ) v (f˅⌝fÎpre(χ)) ),

либо (2) ⌝fÎeff(a) & (⌝fÎpre(χ) v (f˅⌝fÎpre(χ)) ).

Согласие будем обозначать a↑f↑χ .

CS(seq) - множество согласий, в которых состоят действия последовательности seq.

.2.3 Минимальные планы. Бесполезные действия

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

Пучок взаимовлияний подпоследовательностей  и subseq₂ последовательности seq - это некоторое множество взаимовлияний IS(, subseq₂)ÍINT(seq), в котором любое взаимовлияние a⬍f⬍bÎIS таково, что aÎи bÎsubseq₂, где , subseq₂Ìseq и  subseq₂ = Æ.

Пучок взаимовлияний IS(, subseq₂) подобен пучку взаимовлияний IS(subseq₃, subseq₄), если любая пара подобных взаимовлияний inteIS(subseqi,subseq₂) и int'ÎIS(subseq3,subseq₄) такова, что:

либо 1) int - согласие и intʹ - согласие;

либо 2) int - конфликт и - конфликт.

Подобие пучков взаимовлияний обозначим так: IS(, subseq₂) = IS(subseq₃,).

Замечание. Наиболее короткая подпоследовательность состоит из одного действия.

Выделим в seq некоторую подпоследовательность mseq, не включающую действия start и finish.

Некоторую подпоследовательность mseqÌseq будем называть собственной подпоследовательностью, если mseq не включает действий start и finish, то есть,  и . Подпоследовательность действий lseqÌseq такую, что для любых действий aÎlseq и bÎ mseq верно, что a<b и lseqÇmseq=Æ, будем называть левой подпоследовательностью для mseq.

Подпоследовательность действий rseqÌseq такую, что для любых действий aÎmseq и bÎrseq верно, что a<b и mseqÇrseq=Æ, будем называть правой подпоследовательностью для mseq

Собственную подпоследовательность mseq будем называть бесполезной подпоследовательностью действий и обозначать mseq→↻, если IS(lseq, mseq) ≡ IS(mseq, rseq), где lseq - левая подпоследовательность действий для mseq, rseq - правая подпоследовательность действий для mseq.

Удаление бесполезной собственной подпоследовательности mseq из seq приводит к последовательности seq' такой, что для любого взаимовлияния int=a⬍f⬍bÎINT(seq):

либо, 1) имеет место либо обычное преобразование, либо НЕ-преобразование int в такое взаимовлияние int=𝜒ʹ⬍f⬍𝛿ʹÎINT(seq'), что:

либо 1.а) int и int' являются конфликтами;

либо 1.6) int и int' являются согласиями,

либо, 2) имеет место нуль-преобразование int.

Если в некоторой последовательности seq существуют подпоследовательности mseq' и mseq" такие, что:

а)      mseq'Ìmseq", причём a=a", где a' - первое действие mseq', a" - первое
действие mseq",

б)      IS(lseq^,,mseq^,)=IS(lseq",mseq"), где lseq=lseq" - левая подпоследовательность
для mseq' и mseq",

в)      IS(mseq',rseq')≅IS(mseq", rseq"), где rseq' - правая подпоследовательность для
mseq', rseq" - правая подпоследовательность для mseq",

тогда собственная подпоследовательность mseqcÌseq такая, что mseqÌmseq" и

mseqÌmseq', является бесполезной.

При пошаговом преобразовании некоторой исходной последовательности seqÎSEQ путём добавления действий, существует шаг L, на котором будет сформирована последовательность seq'ÎSEQ, содержащая бесполезную подпоследовательность mseqÎseq'.

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

Приведём утверждение 1 сформулированное в [59].

Утверждение 1. Минимальный план planÎSEQ не содержит бесполезной подпоследовательности действий.

Доказательство: Предположим, plan содержит бесполезную собственную подпоследовательность действий mseq. Удалим бесполезную подпоследовательность действий из plan: plan' =Remove(plan,mseq↻). Получившаяся последовательность plan' также является планом, однако, содержит меньшее количество действий, чем plan. То есть, предположение неверно. Следовательно, plan не содержит бесполезную последовательность действий. Утверждение доказано.

Приведём утверждение 2 описанное в [59].

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

Доказательство: Приведём один пример, доказывающий утверждение. Пример.

Пусть дано:

В домене планирования Р существуют действия-прототипы: с эффектом eff()={ f₁, f₂}; действие а₂, с эффектом eff (а₂)= { f₁}; действие а₃ с эффектом eff(a₃)={f₂}.

В домене планирования Р возможно существование прочих действий, но не имеющих в своём описании фактов f₁, f₂, f₃.

Предположим теперь, что существуют:

)        Два неизоморфных плана Plan₁ и Р1аn₂, не содержащие бесполезные подпоследовательности действий.

Plan₁ и Plan₂ содержат схожие множества взаимовлияний (согласий), то есть каждому согласию по некоторому факту f в Plan₁ можно однозначно сопоставить согласие по факту f в Plan₂.

В Plan₁ имеется пара согласий cs¹₁ и cs¹₂, соответственно по фактам f₁ и f₂ - cs₁ и cs₂ расположены на одном интервале влияния.

В Plan₂ имеется пара согласий cs²₁ и cs²₂, сходная соответственно с cs¹₁и cs¹₂.

Тогда, возможно, что в плане Plan₁ в согласиях cs¹₁ и cs¹₂ левым членом является действие  В то время как в плане Plan₂ в согласиях cs²₁ и cs²₂ левыми членами являются, соответственно, действия  и - Из этого ясно, что в схожих согласиях в различных планах, в общем случае, может участвовать различное количество действий. То есть Plan₁ и Plan₂ могут содержать различное количество действий, несмотря на схожее множество взаимовлияний. Следовательно, один из планов не является минимальным. Утверждение доказано.

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

Опишем алгоритм поиска планов в множестве SEQ, который использует понятие взаимовлияния действий в последовательности. Назовём его ITPA (interference transformation planning algorithm).

Рис. 10 - Алгоритм ITPA

Изначально на вход алгоритма ITPA подаётся начальная последовательность initÎSEQ, содержащая наименьшее количество действий. На выходе алгоритма ITPA получается план.

В основе алгоритма ITPA лежит переход от текущей, поданной на вход последовательности seq, к рассмотрению одной из последовательностей itsÎITS, в которой множество взаимовлияний INT(its) отличается (не подобно) от множества взаимовлияний INT(seq).

Если входная последовательность seq не содержит конфликты, то seq является планом и ITPA возвращает seq.

Алгоритм ITPA можно улучшить.

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

Напомним, что в плане любая пара действий, состоящих во взаимовлиянии, согласована. Этот факт можно использовать для поиска планов.

Существует возможность преобразования конфликтного взаимовлияния в пару согласованных взаимовлияний. Определим это формально.

Разрешение конфликта cf=a⬍f⬍𝜒ÎCF(seq) - это обычное преобразование взаимовлияния a⬍f⬍𝜒ÎINT(seq) таким действием b', что: (fÎpre(b') или f∨⌝fÎpre(b')) и ⌝fÎeff(b').

Действие b' будем называть действием, разрешающим конфликт cf, или просто разрешающим действием.

Действия a и 𝜒 будем называть родительскими действиями для действия b'.

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

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

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

Определим операцию разрешения всех конфликтов в последовательности.

Разрешение всех конфликтов CF(seq) будем называть полным разрешением конфликтов в последовательности seq. Полное разрешение конфликтов обозначим: ResolveAll (seq).

RES^seq - множество последовательностей, возвращаемое операцией ResolveAll (seq).

Пусть ко всем конфликтам последовательности seq применяется операция полного разрешения, RES^seq =ResolveAll (seq).

Сформулируем и докажем теорему, которая показывает возможность использования операции полного разрешения конфликтов для поиска планов.

Пусть имеется последовательность seq, не являющаяся планом, и последовательность plan, являющаяся некоторым конкретным планом.

Приведём теорему 1 описанную в [59].

Теорема 1. Полное разрешение конфликтов последовательности seq такое, что ħ(seq)=plan и seq≠plan возвращает одну и только одну последовательность resÎ RES^seqÌSEQ такую, что ħ(res)=plan, либо res≅plan.

Доказательство:

А. Докажем существование последовательности действий res, такой что ħ(res)=plan.

Рассмотрим произвольный конфликт cf=a⬍f⬍𝜒Î CF(seq).

.        В соответствии с основным положением ħ(seq)=plan, существуют действия ħ(a)=a', ħ(𝜒)=𝜒' где a',𝜒'Îplаn Напомним, что в плане не существует конфликтных действий. Следовательно, должно существовать некоторое действие b', не позволяющее конфликтовать паре действий ħ(a)=a' и ħ(𝜒)=𝜒', такое, что: a'<b'<𝜒'Îplan.

.        По определению полного разрешения конфликтов некоторая
последовательность resÎRES^seq содержит действие b"Îres, которое подобно
b'Îplan и является действием, разрешающим конфликт cf=a⬍f⬍𝜒Î CF(seq).
Заметим, в множестве результирующих последовательностей RES^seq имеются всевозможные варианты расположения b" между действиями ħ(a'')=a и ħ(𝜒")=𝜒, где a",𝜒"Îres.

.        а) для любого действия 𝜇"≠b"Îres верно, что (𝜇")=𝜇Îseq,

б)      для любого действия 𝜇Îseq верно, что ħ(𝜇)=𝜇'Îрlan,

в)      из а) и б) следует что, 𝜇"~𝜇'.

. Количество альтернативных расположений b'Îplan среди действий plan'a, подобных действиям из res (имеется в виду подобие, выведенное в 3 пункте: 𝜇"~𝜇') и между действиями ħ(a)=a' и ħ(𝜒)=𝜒' конечно.

. из 2, 3, 4 и по определению гомоморфизма последовательностей следует, что существует такая последовательность действий resÎRES^seq, что ħ(res)=plan..         Единственность существования res, такого, что ħ(res)=plan, следует из того факта, что не существует альтернативного порядка следования действий в res, для которого сохранилось бы утверждение ħ(res)=plan. Следовательно, последовательность res единственна..      Докажем возможность res=plan.

В любой последовательности resÎRES^seq количество действий больше чем в seq.

Количество действий в плане конечно.

.        Тогда из А.5, C.l, С.2 следует, что в одном из вариантов пошагового
разрешения действительно имеет место res≅plan.

Теорема доказана.

Обратим внимание, на интересное свойство последовательности init. Начальная последовательность init такова, что ħ (I,it) = plan, где plan - это любой существующий план для задачи Т.

Очевидно. Теперь мы можем модифицировать алгоритм ITPA. Назовём его CRPA (conflict resolution planning algorithm).

Рис. 11 - Алгоритм CRPA

Основной идеей алгоритма CRPA является полное разрешение конфликтов некоторой исходной последовательности действий seq, дли которой справедливо ħ(seq)=plan. Полное разрешение конфликтов приводит к множеству последовательностей, которые в свою очередь могут также содержать конфликты. Разрешение конфликтов продолжается для очередных последовательностей, до тех пор, пока не будут получены бесконфликтные последовательности действий.

Алгоритм CRPA начинает свою работу с разрешения конфликтов в последовательности init=(start, finish). Более того, задача планирования Т может оказаться тривиально разрешимой, то есть GÌ, и как следствие eff(start)=pre(flnish) без каких-либо конфликтов. Множество взаимовлияний, порождаемое последовательностью init, будем называть первичными взаимовлияниями.

Приведём теорему 2 описанную в [59].

Теорема 2. Если для задачи планирования Т существует решение, то алгоритм CRPA найдёт план.

Доказательство:

l.Ha вход CRPA подаётся последовательность seq⁼init, обладающая свойством ħ (seq) = plan, где plan - это некоторый конкретный план.

. Алгоритм CRPA есть не что иное, как процедурная реализация пошагового полного разрешения конфликтов входной последовательности seq.

. Из 1 и 2, и в соответствии с теоремой 1. следует, что существует одна из рекурсивных ветвей алгоритма, которая возвращает конкретный план plan. Теорема доказана.

Опишем утверждение 3 приведённое в [59].

Утверждение 3. Если для задачи планирования Т существует решение, то алгоритм CRPA найдёт все планы.

Доказательство: Это так поскольку, относительно любого плана plan, решающего задачу планирования Т, справедливо утверждение ħ(init)=plan.

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

Затронем вопрос о конечности алгоритма в случае не существования плана.

Если для задачи планирования Т не существует решения, тогда для начальной последовательности init невыполнимо утверждение ħ(init)=plan. Из-за этого алгоритм CRPA будет работать бесконечно. Другими словами, говоря, последовательность init содержит конфликты, которые не могут быть преобразованы к некоторому множеству согласий путём пошагового преобразования конфликтов. Иначе говоря, последовательность init несогласуема. Определим понятие несогласуемой, последовательности в общем случае.

Некоторую последовательность seqeSEQ такую, что CF(seq)≠∅ будем называть несогласуемой последовательностью, если не существует последовательности seq'ÎSEQ такой, что ħ(seq)=seq' и CF(seq')≠∅.

Привидём описанное в [59] утверждение 4.

Утверждение 4. Любая последовательность resÎRES^seq, полученная из несогласуемой последовательности seq на основе полного разрешения конфликтов также несогласуема.

Доказательство. Разрешение конфликтов в несогласуемой последовательности seqÎSEQ не добавляет какие-либо новые последовательности в SEQ. По определению следует, что любая последовательность resÎRES^seq действительно несогласуема.

Утверждение доказано.

Заметим, что, вообще говоря, в одном из вариантов пошагового разрешения конфликтов в согласуемой начальной последовательности init на очередном шаге может быть сгенерирована несогласуемая последовательность seq.

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

Назовём модифицированный алгоритм CRPA, завершающийся за конечное время, - TCRPA (terminating CRPA).

Рис.12 - Алгоритм TCRPA

Так же как и в алгоритме CRPA, изначально на вход TCRPA подаётся начальная последовательность init. К любой входной последовательности, при рекурсивном вызове, применяется полное разрешение конфликтов. Докажем конечность TCRPA.

Приведём теорему 3 описанную в [59].

Теорема 3.

а)      Если существует решение задачи планирования Т, то TCRPA вернёт некоторый план за конечное число шагов.

б)      Если не существует решения задачи планирования Т, то TCRPA вернёт 0 за конечное число шагов.

Доказательство: Если план существует, то TCRPA найдёт его, так как CRPA находит.

Если план не существует, то начальная последовательность init несогласуема. Тогда, в соответствии с утверждением 2. рано или поздно в любом из вариантов пошагового полного разрешения конфликтов init появится бесполезная подпоследовательность действий. D этом случае TCRPA завершит работу вернув 0. Теорема доказана.

Приведём сформулированное в [59] утверждение 5.

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

Доказательство: Из пункта 1 алгоритма TCRPA вытекает, что если входная последовательность содержит бесполезную подпоследовательность, то даже если она является планом, алгоритм TCRA вернёт 0.

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

Из теоремы 1. следует, что для любого плана plan, не содержащего бесполезную подпоследовательность действий, существует такой вариант пошагового полного разрешения конфликтов, который приводит к плану plan. Этот вариант не генерирует на некотором шаге последовательность seq, содержащую бесполезную подпоследовательность действий, так как plan не содержит бесполезной подпоследовательности действий. Утверждение доказано.

Следствием из утверждения 6 является то, что если существует решение задачи планирования Т, то алгоритм TCRPA вернёт все минимальные планы. Доказательство следует непосредственно из утверждения 6.

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

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

В (1.2.4.) было показано, что решение задачи планирования требует экспоненциальных затрат памяти вычислительной системы. В связи с этим, представляется более эффективным использование техник, нацеленных преимущественно на сокращение емкостной сложности алгоритмов планирования. На практике это предположение, подтверждается тем, что алгоритмы, использующие представление пространства состояний без разделения [67, 43, 59], значительно эффективнее иных алгоритмов на ряде доменов планирования [25].

В (2.2.3) была представлена техника выявления бесполезных подпоследовательностей действий, используемая алгоритмом TCRPA (2.2.6), которая позволяет редуцировать емкостную сложность алгоритмов. Совершенно очевидно, что больший эффект от её использования может быть достигнут на задачах, в которых отношение количества последовательностей, содержащих бесполезные подпоследовательности действий (БПД), к количеству последовательностей без БПД, достаточно велико.

Обратимость домена планирования Р - это отношение

,

где  - количество последовательностей длины содержащих бесполезные подпоследовательности действий, |SEQ,| - общее количество последовательностей длины 𝓁.

На основании (2.2.3), можно заключить, что существует некоторое целое число к такое, что если длина 𝓁>k, то обратимость равна 1.

Для данной задачи планирования Т, в которой имеется m=|SR| прототипов действий можно определить общее количество последовательностей длины 𝓁: ||=.

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

Определим | | вероятностным способом.

Множество элементарных событий 𝛺 = {𝜛 | 𝜛 = <IS (lseq, mseq), IS (mseq, rseq)>}, где mseqÌseq - некоторая собственная подпоследовательность действий seq, lseq - левая подпоследовательность для mseq, rseq - правая подпоследовательность для mseq, seq - некоторая последовательность в SEQ, IS -пучок взаимовлияний.

Множество составных событий S - множество всех подмножеств элементарных событий Q.

Определим вероятностную схему домена планирования Р.

Для домена планирования Р вероятностная схема - тройка <𝛺, S, PROB>, где PROB - это распределение вероятностей, определяемое множеством пар <s, р>, в которых sÎS, р - вероятность появления события sÎS.

На множестве событий S представляет интерес подмножество событий U- "появление бесполезной подпоследовательности действий".

Множество событий U={𝜛 | ∀𝜛Î𝛺 𝜛(IS(lseq, mseq)) ≅ 𝜛(IS(mseq, rseq))}. Любое событие в U будем называть "появление бесполезной подпоследовательности действий".

Обозначим через  подмножество событий U таких, которые определены на последовательностях заданной длины |seq|, а также на подпоследовательностях заданных длин |lseq|, |mseq|, |rseq|, где mseqÌseq.

Вероятность prob()ÎPROB - это вероятность того, что в произвольной последовательности seqÎSEQ собственная подпоследовательность mseqÌseq, для которой существует левая и правая подпоследовательности lseq и rseq, является бесполезной. Дадим этой величине приблизительную оценку 0 (prob()).

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

Для некоторого взаимовлияния по факту f в левом пучке существует одно из пяти возможных взаимовлияний по факту f в правом пучке. То есть, число возможных исходов равно 5:

-       исход: конфликт по факту f типа (f, ⌝f);

-       исход: конфликт по факту f типа (⌝f, f);

-       исход: согласие по факту f типа (f, f);

-       исход: согласие по факту f типа (⌝f,⌝f);

-       исход: отсутствие взаимовлияния по факту f;

Примечание. В скобках первый элемент факт f(⌝f) - это факт в эффекте некоторого действия mseq, которое состоит во взаимовлиянии с некоторым действием rseq, имеющим в предусловии либо факт f, либо факт -⌝f.

Из этих пяти исходов, для некоторого взаимовлияния в леном пучке, лишь 2 исхода являются благоприятными. Следовательно, вероятность благоприятного исхода для любого взаимовлияния в левом пучке произвольной последовательности seq равна: 2/5.

Определим теперь в произвольной последовательности seq среднюю мощность пучка взаимовлияний подпоследовательностей lseq и mseqÌseq: М |IS(lseq, mseq)|.

Пусть,

М|a| - среднее количество фактов в описании любого действия домена Р;

F - количество фактов, используемых в описании домена Р;

|lseq| - длина подпоследовательности lseq;

|mseq| - длина подпоследовательности mseq;

Тогда,

 (1)

Здесь, abs-это операция, возвращающая модуль операнда.

Приближённая оценка вероятности G(prob( )), рассчитывается так:

 (2)

В расчетах приблизительной оценки 𝜃, нигде не встречается длина правой подпоследовательности rseq. Это неявляется ошибкой, так как мощность левого пучка подпоследовательности mseq всегда не меньше мощности правого пучка.

Будем считать, что подпоследовательности длины равной 1, всегда полезны, так как обычно в домене планирования действия описываются так, что при применении производят какие-либо изменения в состоянии. Поэтому, далее будем рассчитывать вероятность для подпоследовательностей длиной больше чем 1.

Множество  = {| |seq| = 𝓁} является множеством событий появления бесполезной подпоследовательности действий mseq↻ произвольной длины (|mseq|≤|seq|-2) в произвольной последовательности seq, при фиксированном |seq| = 𝓁.

Множество событий  :

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

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

Заметим, что мощность || = k, где k - количество собственных подпоследовательностей в некоторой последовательности seq, которое подсчитывается по формуле:

 (3)

Определим вероятность prob||), которая рассчитывается по формуле сложения вероятности k совместных и независимых событий.

Однако вначале для более удобной записи формулы упорядочим множество  в ряд из к элементов следующим образом: для каждого |mseq| = 2 до 𝓁-2 расположим в конце ряда  в произвольном порядке очередные (𝓁-|mseq|)+l событий  . Далее, запись  означает элемент с номером і ряда .

Ниже приведена формула вычисления prob():

Prob()

 (4)

Здесь, в квадратных скобках определены итераторы по тем элементам ряда UE', которые участвуют в произведении вероятностей.

В формуле prob() сумма на нижней строке вычитается, если k -чётное число, и прибавляется, если k - нечётное число.

Вычислим математическое ожидание М || количества последовательностей длины 𝓁, которые содержат бесполезные подпоследовательности действий:

М || =||*prob()

Охарактеризуем свойство обратимости, на примере следующих доменов планирования: "Мир кубиков", "Логистика",

"Задача о коммивояжёре".

Домен планирования "Мир кубиков" содержит:

действия (правил),

факта (предикатов).

Домен планирования "Логистика" содержит:

объектов,

действия,

фактов.

Домен планирования "Задача о коммивояжоре" содержит:

объектов (городов),

фактов,

действия.

Для данных доменов планирования построим графики зависимости мощностей | и || от длины 𝓁, где длина 𝓁 варьируется от 1 до 11 действий.

На графике: по горизонтальной оси отложена длина 𝓁, по вертикальной оси - мощность ||= (на рисунке - SEQ), а также - мощность || (на рисунке - SEQ (БПД)).

Рис.13 - "Мир Кубиков"

Рис. 14 - "Логистика"

Рис. 15 - "Задача о коммивояжёре"

Примечание.

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

Пример 1.

Для домена планирования "Мир кубиков" количество последовательностей длины 5 равно 144⁵ = 61 917 364 224. Из них количество последовательностей, содержащих БПД, равно 1 609 851 470, что составляет примерно 2% от общего количества.

Пример 2.

Для домена планирования "Логистика" количество последовательностей длины 3 равно 12 812 904. Из них количество последовательностей, содержащих БПД, равно 384 387, что составляет примерно 3% от общего количества.

Пример 3.

Для домена планирования "Задача коммивояжёра" количество последовательностей длины 8 равно 1 099 511 627 776. Из них количество последовательностей, содержащих БПД, равно 87 960 930 222, что составляет примерно 8% от общего количества.

В соответствии с пунктом (2.2.3.) графики SEQ и SEQ (БПД) сойдутся при некоторой длине L.

Очевидно, что график SEQ (БПД) всегда возрастает.

Алгоритм TCRPA, использующий технику выявления бесполезной подпоследовательности действий, будет осуществлять перебор в множестве SEQ' = / , где n - наибольшая длина плана, который не содержит бесполезные подпоследовательности действий,  - множество всех последовательностей длиной меньше либо равной n. Алгоритмы, не использующие соответствующей техники, будут искать план во всём множестве .

.3 Требования к интерфейсу системы

.3.1 Интерфейс системы

Интерфейс - совокупность средств, методов и правил взаимодействия между элементами системы.

Основным модулем системы, является база знаний в которой содержатся знания, планы, цели функционирования системы.

Структура разработанной системы (рисунок 9.), общается с компонентами ИРК с помощью внешнего интерфейса.

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

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

.3.2 Входные и выходные данные.

На вход системы поступают факты и состояния процессов внешней среды, а так же задачи необходимые к выполнению.

На основе данных полученных от внешних источников, система формирует представление о текущей ситуации и пополняет рабочую память системы. Более подробно процесс обработки данных и нахождения минимального плана действий для цели, описан в (2.1. , 2.2.).

На выход системы подаётся минимальный план, полученный в результате работы алгоритма TCRPA(2.2.7), виде логической последовательности действий.

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

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

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

В системе принят гибридный метод представления знаний, который сочетает системы фреймов и продукционные системы описанный в (2.1.2).

Данные в информационно робототизированном комплексе (ИРК), представляется на языке логики первого порядка(исчисления предикатов).

Язык <#"531146.files/image067.gif"> и множества предикатных символов . С каждым функциональным и предикатным символом связана арность <#"531146.files/image069.gif"> и т. д.),

Пропозициональные связки: ,

Кванторы <#"531146.files/image071.gif"> и существования ,

Служебные символы: скобки и запятая.

Перечисленные символы вместе с символами из  и  образуют алфавит логики первого порядка. Более сложные конструкции определяются индуктивно <#"531146.files/image073.gif">, где  - функциональный символ арности , а  - термы.

Атом <#"531146.files/image077.gif">, где  - предикатный символ арности , а  - термы.

Формула <#"531146.files/image079.gif">, где  - формулы, а  - переменная.

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

Логика первого порядка обладает рядом полезных свойств, которые делают ее очень привлекательной в качестве основного инструмента формализации математики <#"531146.files/image089.gif">

Рисунок 1 - Правильное положение запястья и кисти

Необходимо использовать клавиши «А» и «О» с более вогнутой формой по сравнению с остальными, что облегчает правильную постановку рук при машинописи.

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

Режим труда и отдыха при работе на клавиатуре на ПЭВМ выбирается согласно СанПиН 2.2.2/2.4.1340-03 [61].

При работе на ПЭВМ в течении 8 часов в конкретных условиях на клавиатуре пользователь выполняет работу, которая относится к группе А и категории работ с видеомонитором Ш.

Исходя из этих условий, общее время перерыва составляет 70 мин.

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

часа работы - 10 мин перерыв;

часа работы - обеденный перерыв 50 мин;

часа работы - 10 мин перерыв;

часа работы - окончание работы.

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

Согласно с материалом представленным в [60], с целью снятия утомления с плечевого пояса и рук предусматриваются динамические упражнения с чередованием напряжения и расслабления отдельных мышечных групп плечевого пояса и руководитель, улучшают кровоснабжение, снижают напряжение.

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

1 комплекс

1.И.п. - о.с. 1 - поднять плечи. 2 - опустить плечи. Повторить 6-8 раз, затем пауза 2 - 3 с, расслабить мышцы плечевого пояса. Темп медленный.

2.И.п. - руки согнуты перед грудью. 1 - 2 - два пружинящих рывка назад согнутыми руками. 3 - 4 - то же прямыми руками. Повторить 4-6 раз. Темп медленный.

3.И.п. - стойка ноги врозь. 1 - 4 - четыре последовательных крута руками назад. 5 - 8 - то же вперед. Руки не напрягать, туловище не поворачивать. Повторить 4-6 раз. Закончить расслаблением. Темп средний.

2 комплекс

1.И.п. - о.с. - кисти в кулаках. Встречные махи руками вперед и назад. Повторить 4-6 раз. Темп средний.

2.И.п. - о.с. 1 - 4 - дугами в стороны руки вверх, одновременно делая ими небольшие воронкообразные движения. 5 - 8 - дугами в стороны руки расслабленно вниз и потрясти кистями. Повторить 4-6 раз. Темп средний.

3.И.п. - тыльной стороной кисти на пояс. 1 - 2 - свести вперед, голову наклонить вперед. 3 - 4 - локти назад, прогнуться. Повторить 6-8 раз, затем руки вниз и потрясти расслабленно. Темп медленный.

3 комплекс

1. И.п. - стойка ноги врозь, руки в стороны, ладони кверху. 1 - дугой кверху расслабленно правую руку влево с хлопками в ладони, одновременно туловище повернуть налево. 2 - и.п. 3 - 4 - то же в другую сторону. Руки не напрягать. Повторить 6-8 раз. Темп средний.

2.      И.п. - о.с. 1 - руки вперед, ладони книзу. 2-4 зигзагообразными движениями руки в стороны. 5-6 - руки вперед. 7-8 - руки расслабленно вниз. Повторить 4-6 раз. Темп средний.

3. И.п. - о.с. 1 - руки свободно махом в стороны, слегка прогнуться.

2       - расслабляя мышцы плечевого пояса, "уронить" руки и приподнять их скрестно перед грудью. Повторить 6-8 раз. Темп средний.

4 комплекс

И.п. - о.с. 1 - дугами внутрь, руки вверх - в стороны, прогнуться, голову назад. 2 - руки за голову, голову наклонить вперед. 3 - "уронить" руки. 4 - и.п. Повторить 4-6 раз. Темп средний.

1.И.п. - руки к плечам, кисти в кулаках. 1-2 - напряженно повернуть руки предплечьями и выпрямить их в стороны, кисти тыльной стороной вперед.

3 - руки расслабленно вниз. 4 - и.п. Повторить 6-8 раз, затем расслабленно вниз и встряхнуть кистями. Темп средний.

2.И.п. - о.с. 1 - правую руку вперед, левую вверх. 2 - переменить положение рук. Повторить 3-4 раз, затем расслабленно опустить вниз и потрясти кистями, голову наклонить вперед. Темп средний.

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

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

Из материалов представленных в [62]. Германий (Ge) имеет атомный вес 72.59, его содержание в земной коре составляет 0.0007 вес. %. Германий представляет собой твёрдое вещество серо-белого цвета с металлическим блеском.

Как полезное ископаемое, германий встречается в природе в рассеянном виде в виде минералов, в которых этого элемента больше 1%. Это аргиродит, германит, ультрабазит и другие, включая открытые лишь в последнее десятилетия - реньерит, штотит, конфильдит и плюмбогерманит.

Германий используется для изготовления кристаллов в жидкокристалических мониторах.

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

Из материалов представленных в [62]. Гадалиниево-галиевые гранаты образуются в производстве компонентов запоминающих устройств. В ходе обработки около 80% материала превращается в отходы или отбраковывается. Они имеют высокую стоимость, поэтому выделение их из отходов представляет интерес с экономической точки зрения. Если процесс выделения приводит к достаточно чистым продуктам, то они могут повторно использоваться в качестве исходного материала.

Галий (Ga) имеет атомный вес 69.72, относится к числу редких металлов: содержание в земной коре составляет не более 0,001 вес. %. В свободном состоянии представляет собой серебристо-белый мягкий металл с температурой плавления 29.7°С. Галий можно получить из отходов цветной металлургии, главным образом из цинковых концентратов.

Гадолиний (Gd) имеет атомный вес 157.25, относится к лантаноидам, является металлом с плотностью в свободном состоянии 7.89 г/ и температурой плавления 1312°С. Из-за сложности получения галия и гадолиния из природного сырья особое значение приобретает утилизация этих металлов с целью повторного использования.

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

Из материалов представленных в [62]. Платина (Pt) имеет атомный вес 195.09, относится к драгоценный металлам, встречается в природе в россыпях в виде платиновых металлов (иридия, палладия, родия, ртутения, осмия). Наиболее богатые месторождения платины в Российской Федерации находятся на урале.

Платина представляет собой белый блестящий металл, не изменяющийся на воздухе даже при сильном нагреве, обладающий ковкостью, имеющий плотность 21.45 г/ и температуру плавления 1768°С. Эти свойства определили использование платины в радиоэлектронике.

Из материалов представленных в [62]. Палладий (Pd) имеет атомной массой 106,42. Палладий представляет собой серебристо-белый благородный металл по внешнему виду схожий с серебром, на этом их сходство не заканчивается, ведь палладий самый легкий из платиновых металлов. Имеющий 12,02 г/палладий ближе к серебру (10,49 г/с г/), чем к родственной платине (21,45 г/). Палладий тяжелый тугоплавкий пластичный ковкий металл, который легко прокатывается в фольгу и протягивается в тонкую проволоку.

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

Выводы по разделу безопасность жизнедеятельности

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

. ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКИЙ РАЗДЕЛ

.1 Планирование разработки программного продукта

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

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

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

Согласно ГОСТ 23501.1-79 регламентируются следующие стадии проведения исследования:

-       техническое задание - ТЗ (ГОСТ 23501.2 - 79);

-       эскизный проект - ЭП (ГОСТ 23501.5 - 80);

-       технический проект - ТП (ГОСТ 23501.6-80);

-       рабочий проект - РП (ГОСТ 23501.11-81);

-       внедрение - ВП (ГОСТ 23501.15-81).

Планирование стадий и содержания работ осуществляется в соответствии с [65]. На всех стадиях проведения исследования выполняются следующие виды работ, перечень которых показан в таблице 5.1.

Таблица 5.1. - Состав работ и стадии разработки ПП

Трудоемкость выполнения работ по созданию ПП на каждой из стадий определяется в соответствии с [64] и [65].

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

Трудоемкость каждого вида работ определяется, в соответствии с методическими указаниями [65], по формуле:

                                               (5.1)

где  ¾ минимально возможная трудоемкость выполнения отдельного вида работ;

 ¾ максимально возможная трудоемкость выполнения отдельного вида работ.

Продолжительность каждого вида работ в календарных днях (T_i) определяется по формуле [65]:

                                                       (5.2)

где  ¾ трудоемкость работ, [человеко-дни];

 ¾ численность исполнителей, [чел.]

 ¾ коэффициент, учитывающий выходные и праздничные дни:

где  ¾ число календарных дней;

 ¾ число рабочих дней;

Для расчета принимается среднее значение равное .

Полный список видов и этапов работ по созданию ПП, экспертные оценки и расчетные величины их трудоемкости, а также продолжительность каждого вида работ, рассчитанные по формулам (5.1) и (5.2), представлены в таблице 5.2. В разработке ПП принимают участие два человека: руководитель работы и инженер - программист.

Таблица 5.2. - Расчет трудоемкости и продолжительности работ по созданию ПП.

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

5.1.2 Построение ленточного графика разработки ПП

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

Ленточный график разработки ПП, построенный по данным таблицы 5.2, приведен на рисунке 5.1.

Рисунок 1. - Ленточный график разработки ПП.

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

Сметная стоимость проектирования и внедрения программного продукта включает в себя следующие затраты, определяемые по формуле (5.3):

, (5.3)

где:

 ¾ стоимость разработки ПП;

 ¾ основная заработная плата исполнителей;

 ¾ дополнительная заработная плата исполнителей, учитывающая потери времени на отпуска и болезни (принимается в среднем 10% от основной заработной платы);

 ¾ единый социальный налог (ЕСН), представляющий собой отчисления во внебюджетные фонды государственного социального страхования (пенсионный фонд, фонд обязательного медицинского страхования, фонд социального страхования). Рассчитывается в соответствии с установленной ставкой ЕСН равной 34% от основной и дополнительной заработной платы;

 ¾ затраты на используемые материалы;

 ¾ стоимость машинного времени;

 ¾ накладные расходы включают затраты на управление, уборку, ремонт, электроэнергию, отопление и др. (принимаются в размере 60% от основной и дополнительной заработной платы.

Основная заработная плата исполнителей

На статью «Заработная плата» относят заработную плату научных, инженерно-технических и других работников, непосредственно участвующих в разработке ПП. Расчет осуществляется по формуле (5.4):

         (5,4)

где:

 ¾ заработная плата исполнителей (руб.);

 ¾ средняя тарифная ставка работника организации разработчика ПП (руб./чел./дни);

 ¾ трудоемкость разработки ПП (чел.дни).

Средняя тарифная ставка работника организации разработчика ПП() определяется по формуле (5.5):

  (5.5)

где:

 ¾ месячная зарплата работника [руб./мес.];

 ¾ среднее количество рабочих дней в месяце (равно 20) [дни].

Расчет затрат на основную заработную плату разработчиков ПП приведен в таблице 5.3.

Таблица 5.3. - Затраты на заработную плату

Дополнительная заработная плата

Дополнительная заработная плата на период разработки ПП рассчитывается относительно основной и составляет 10% от ее величины:

 (руб.).

Расчет отчислений на социальное страхование

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

 (5.6)

 39083 (руб.).

Расчет расходов на материалы

На эту статью относят все затраты на электронные носители данных, бумагу для печатных устройств (принтер), канцтовары и др. Затраты по ним определяются по экспертным оценкам. Расчет расходов на материалы приведен в таблице 5.4.

Таблица 5.4. - Расходы на материалы

Накладные расходы

На статью «Накладные расходы» относят расходы, связанные с управлением и организацией работ. Накладные расходы рассчитываются относительно основной заработной платы. Величина накладных расходов принимается равной 60% от основной заработной платы исполнителем. Формула расчета (5.7):

,        (5.7)

где:

 ¾ накладные расходы(руб.);

 ¾ основная заработная плата (руб.);

 ¾ коэффициент учета накладных расходов (К=0,6).

Таким образом, накладные расходы будут равны:

 62700 (руб.).

Расчет себестоимости машинного времени

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

,    (5.8)

где:

 ¾ тарифная стоимость одного часа машинного времени
(К_{маш. вр.}=40 руб./час);

 ¾ машинное время, используемое на проведение работ.

Необходимое количество машинного времени для реализации проекта по разработке программы рассчитывается по формуле:

,     (5.9)

где:

 ¾ трудоемкость работ (чел.дни);

 ¾ продолжительность рабочей смены (при пятидневной рабочей неделе Т_см=8);

 ¾ средний коэффициент использования ПК ().

Тогда:

=543,2 (час.).

Стоимость машинного времени составит:

21728 (руб.)

Результат расчета на проектирование программного продукта представлены в таблице 5.5.

Таблица 5.5. - Смета затрат на разработку и внедрение ПП.

Таким образом, себестоимость разработки ПП составляет 243101 руб.

Данная программа может быть реализована на рынке. При расчётном количестве реализованных программ - n, оптовая цена программы (Ц_опт) может быть рассчитана по формуле:

,

где:

- себестоимость разработки программы;

 - прибыль, определяется по формуле:

,

где:  - средний уровень рентабельности, принимается ;

Таким образом, при среднем расчётном количестве реализованных программ оптовая цена ПП составит:

 (руб.)

Отпускная оптовая цена реализации программы потребителям должна включать налог на добавленную стоимость (НДС) и рассчитывается по формуле:

,

где НДС - налог на добавленную стоимость, рассчитывается в соответствии с действующей ставкой этого налога - 18% от оптовой цены программы:

 (руб.)

 (руб.)

Таким образом, отпускная цена программы составит 114745 руб., в том числе НДС - 17504 (руб.).

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

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

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

·        Возможность обездвиженным людям не прибегать к помощи персонала, а выполнять некоторые задачи на компьютере самим.

Разработанный ПП позволяет решить данные задачи с меньшими затратами и более эффективно.

Базовый вариант

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

Проектный вариант

Количество сотрудников, которые будут выполнять данный объем работ с использованием разработанного ПО - 1 человек и 1 ПЭВМ.

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

Расчет трудоемкости по обработке данных на ЭВМ, в человеко-часах, для обоих вариантов осуществляется по формуле (5.10):

,         (5.10а)

где:

 - действительный годовой фонд времени работы одного работника, чел. час;

 - количество работников по данному варианту, чел.;

, (5.10б),

 - номинальный фонд рабочего времени 1 работника в 2011 году в чел. час.;

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

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

, где

 - число рабочих дней в году;

 - продолжительность рабочей смены ();

 - число предпраздничных дней в году;

 - количество часов, на которые сокращается рабочий день в предпраздничные дни ();

 - число смен работы в сутки, в общем случае для оборудования от одной до трех смен, для работников - одна смена.

В 2011 году по календарю число рабочих дней: = 248 дн, число сокращённых на 1 час предпраздничных дней рабочих дней: = 3 дн. Принимаем число смен работы оборудования  = 1.

Подставляем данные в формулы, получаем:

 (ч);

Действительный фонд времени работы одного работника в 2011 году составит:

 (чел. час);

Трудоемкость обработки информации при среднем годовом действительном фонде времени работы одного работника за год, равного

 (чел./час), составит:

Базовый вариант

(чел.час)

Проектный вариант

(чел.час)

В проектном варианте будет использоваться оборудование с применением разработанных программных средств. При среднем коэффициенте использования персонального компьютера для решения задачи по проектному варианту, равном 0,7, трудоемкость обработки информации на персональном компьютере за год вычисляется по формуле (5.11):

          (5.11)

Вычислим трудоемкость обработки информации  (маш.час)

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

Базовый вариант

Капитальные вложения складываются из стоимости производственных помещений, необходимых для размещения 2 работников без ПК, исходя из расчета по норме 3 кв.м. на человека и балансовой стоимости 1 кв.м. площади - 15000 руб.

 (руб.)

Проектный вариант

Капитальные вложения складываются из:

-       Стоимости производственных помещений из расчета 6 кв.м на 1 работника с ПК и балансовой стоимости 1 кв.м площади - 7500 руб.:

(руб.)

-       Стоимость технических средств - ЭВМ и периферии:

-       системный блок:

-          Процессор Intel Atom N425 1,8 ГГц,

-       Модуль оперативной памяти DDR3 1Гб Kingston,

-       Жесткий диск 200 Gb Western Digital “Caviar SE WD 2000AAJC”

Стоимость системного блока: 5380 руб.

-       монитор 19” LG Flatron L1910B, стоимостью 3840 руб.;

-       лазерный принтер/сканер/копир HP DeskJet 2050 , A4, печать: 20ppm, 1200x1200 dpi, USB2.0, стоимостью 8350 руб.;

-       приобретение программного обеспечения:

− операционная система MS Windows 7 Professional, стоимостью 6340 руб.;

Общая стоимость технических средств:

 (руб.)

-   Стоимости разработанной программы:

 руб.

Общие капитальные вложения рассчитываются по формуле (5.12):

       (5.12)

где:

 - стоимость производственных помещений;

- стоимость приобретаемого оборудования.

 (руб.)

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

Расчёт годовых текущих затрат производится по формуле:

;

где:

 - затраты на используемые материалы (руб.);

 - основная заработная плата исполнителей за год (руб.);

 - дополнительная заработная плата работников, учитывающая потери времени на отпуска и болезни (принимается в среднем 10% от основной зарплаты работников) (руб.)

 - отчисления во внебюджетные фонды государственного социального страхования (пенсионный фонд, фонд обязательного медицинского страхования, фонд социального страхования), рассчитываются как 0,26% от основной и дополнительной заработной платы (руб.);

- накладные расходы включают затраты на управление, уборку, ремонт, электроэнергию, отопление и др. (принимаются в размере 60% от основной и дополнительной заработной платы) (руб.);

 - годовая сумма амортизационных отчислений по соответствующим группам основных производственных фондов и нематериальных активов (рассчитывается исходя из следующих норм амортизации: 12,5% - от стоимости оборудования; 2,5% - от стоимости производственных площадей и 33% - от стоимости программного обеспечения, исходя из расчетного срока службы ПО - три года) (руб.).

Базовый вариант

Текущие затраты состоят из:

-       Заработная плата работников (по 20000 руб. в месяц) - 20000 * 12 * 2 = 480000 (руб.);

-       Дополнительная заработная плата (10% от основной заработной платы) - 480000 * 0,1= 48000 (руб.);

-       Отчисления на социальное страхование (34% от основной и дополнительной заработной платы) - (480000 + 48000) * 0,34 = 179520 (руб.);

-       Накладные расходы (60% от основной и дополнительной заработной платы) - (960000 + 96000) * 0,6 = 633600 (руб.)

-       Амортизационные отчисления (2,5% от стоимости помещений) - 90000 * 0,025 = 2250 (руб.)

 = 480000 + 48000 + 179520 + 63360 + 2250 = 773130 (руб.)

Проектный вариант

-       Заработная плата работников (по 25000 руб. в месяц) - 25000 * 12 * 1 = 300000 (руб.);

-       Дополнительная заработная плата (10% от основной заработной платы) - 300000 * 0,1 = 30000 (руб.);

-       Отчисления на социальное страхование (34% от основной и дополнительной заработной платы) - (300000 + 30000) * 0,34 = 112200 (руб.);

-       Накладные расходы (60% от основной и дополнительной заработной платы) - (300000 + 30000) * 0,6 = 198000 (руб.);

Амортизационные отчисления

 = 90000 * 0,025 + 23910 * 0,125 + 243101 * 0,33 = 85462 (руб.)

= 300000 + 30000 + 112200 + 198000 + 85462 = 725662 (руб.)

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

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

Годовая экономия текущих затрат рассчитывается по формуле (5.14):

,      (5.14)

где:

 - годовые текущие затраты на обработку данных в базовом варианте;

 - годовые текущие затраты на обработку данных в проектном варианте;

Сm = 773130 - 725662 = 47468 (руб.)

Годовые приведенные затраты для базового и для проектного варианта рассчитываются по формуле (5.15):

,     (5.15)

где:

 - годовые текущие затраты для базового и проектного варианта соответственно;

- нормативный коэффициент сравнительной экономической эффективности капитальных вложений (= 0,15);

 - капитальные вложения для базового и проектного варианта соответственно.

Базовый вариант

 (руб.)

Проектный вариант

 (руб.)

Годовой экономический эффект рассчитывается по формуле (5.16):

,      (5.16)

где:

 - годовые приведенные затраты по базовому варианту;

 - годовые приведенные затраты по проектному варианту.

Э = 786630 - 759961 = 26669 (руб.)

Основные технико-экономические показатели проекта приведены в таблице 5.6.

Таблица 5.6. - Основные технико-экономические показатели проекта

Выводы по организационно-экономическому разделу

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

Согласно проведённым расчетам трудоёмкость разработки ПП составляет 98 чел.дня, продолжительность разработки ПП - 121 календарный день, себестоимость разработки ПП - 243101 руб., отпускная цена - 114745.

Внедрение проектных организационно-технических мероприятий и ПП позволит получить годовой экономический эффект в сумме 26669 рубля и снизить:

-        годовые приведенные затраты труда на 50%;

-       годовые текущие затраты на обработку информации на 50%;

-       количество работников сократить в 2 раза.

Заключение

В работе получены следующие результаты:

.        Исследованы существующие подходы к решению задачи планирования при классических допущениях.

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

.        Описаны требования к информационному, программному и техническому обеспечению комплекса.

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

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

1.   Аверкин А.Н. Нечёткая модель обобщенного решателя проблем // Семиотика и информатика. - 1979. - Вып.12. - с.103-108

2.   Вагин В.Н., Еремеев А.П. Конструирование интеллектуальных систем поддержки принятия решений реального времени //Труды международной конференции "Интеллектуальное управление: Новые интеллектуальные технологии в задачах управления" (ICIT-99), стр.27-33. - М.:Наука, Физматлит, 1999

3.   Виноградов А.Н. Разработка и исследование моделей и методов построения архитектуры и инструментальных средств для динамических интеллектуальных систем // Диссертация, ИПС РАН, Переславль-Залесский, 2001

4.   Горбатенко С.А., Макашов Э.М., Полушкин Ю.Ф., Шефтсль Л.В. Инженерный справочник. Механика полета (общие сведения, уравнения движения) // М.: Машиностроение, 1969

5.   Ежкова И.В. Обобщение схем логического вывода в задачах планирования и диагностики. Диссертация на соискание учёной степени к.ф.-м.н., Москва, МФТИ, 1978,150с.

6. Еремеев А.П., Троицкий В.В.. Основные способы формализации временных зависимостей при построении интеллектуальных систем. КИИ-2000. стр.652-661

7. Ковальски Р. Логика в решении проблем. - М.: Наука, 1990. - 280с.

8. Месарович М., Такахара Я. Общая теория систем. Математические основы. - М.: Мир, 1978.-311с.

9. Минский М. Фреймы для представления знаний // М.: Мир, 1979

10.Осипов Г.С. Искусственный интеллект: состояние исследований и несколько слов о будущем // Новости искусственного интеллекта. - М.: Анахарсис, 2001. - №1. - с. 3-13

11.Осипов Г.С, Виноградов А.Н., Динамическое целеполагание в системах, основанных на знаниях // Сборник трудов VII национальной конференции по искусственному интеллекту, с.272-279. - М.: Физматлит, 2000

12.Осипов Г.С, Жилякова Л.Ю., Виноградов А.Н. Динамические интеллектуальные системы. Представление знаний и основные алгоритмы. Моделирование целенаправленного поведения // Известия РАН "Теория и системы управления". -2002. -№б.-с.119-127

Результаты соревнования алгоритмов планирования IPC 2002 / <http://www.cis.strath.ac.uk/~derek/IPC/main.html>

13.Тарханов Т.С. Использование гибридного подхода к представлению знаний на основе фреймов и семантических сетей для задач классификации // Труды XXVIII международной конференции "Информационные технологии в науке, образовании, телекоммуникации, бизнесе" (IT+SE'2001) // Гурзуф, 2001, с.89-92

14.Тарханов Т.С. Представление знаний в динамических базах знаний для предметных областей со сложной структурой //Труды VII национальной научной конференции с международным участием КИИ-2000 // М., Физматлит, 2000, с.290-298

15.Barrett A., Weld D. Partial-order planning: Evaluating possible efficiency gains. Artificial Intelligence, 67:71-112,1994.

16.Blum A., Furst M. Fast planning through planning graph analysis // Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI - 95). - Montreal, Canada. -1995.- с 1636-1642

Bonet В., Geffner H. Planning as heuristic search. // Artificial Intelligence. -2001. <http://citeseer.ni.nec.com/bonet01planning.html>T. The computational complexity of propositional STRIPS planning // Artificial Intelligence, 69:161-204,1994. <http://citeseer.ni.nec.com/bylander94computational.html>

16.Chapman D. Planning for Conjunctive Goals // Artificial Intelligence. - 1987. - №32(3). -c.333-377

17.Edelkamp S., Reffel F. Deterministic State Space Planning with BDDs. ECP, 1999, pp 381-382, LNAI, Springer

18.Erol K., Nau D., Subrahmanian V. Complexity, Decidability and Undecidability Results for Domain-Independent Planning. A Detailed Analysis // Технический отчёт Университета Мэрилэнд №CS-TR-2797

19.Erol К., Nau D., Subrahmanian V. On the complexity of domain-independent planning. In Proceedings of the Tenth National Conference on Artificial Intelligence, July 1992.

20.Fikes R.E., Nilsson N.J. STRIPS: a new approach to application of theorem proving to problem solving // Artificial Intelligence 1971,2

21.Gelerntner H. Realization of a Geometry-Theorem Proving Machine. In E.A. Fcigenbaum and J. Feldman eds., Computers* and Thought, New York: McGrawHill, 1959.

22.Green C.C. Theorem proving by resolution as a basis for question answering systems. In Bernard Meltzer and Donald Michie, editors // Machine Intelligence, Edinburgh University Press, Edinburgh, Scotland, 1969,4

23.Hoffmann J., Nebel B. The FF planning system: Fast plan generation through heuristic search // Journal of Artificial Intelligence Research, 2001

24.Joslin D., Pollack M. Is "Early Commitment" in Plan Generation Ever a Good Idea? II Proceedings of the Thirteenth National Conference on Artificial Intelligence. - Mcnlo Park, Calif.-1996.-с 1188-1193

25.Kambhampati S. Refinement Planning as a Unifying Framework For Synthesis Plan II AI Magazine, Vol.18, №2,1997

26.Kambhampati S., Nigenda R., Nguyen X. AltAlt: Combining the advantages of Graphplan and Heuristic State Search. //ASU Technical Report

27.Kautz H., Selman B. Planning as Satisfiability // Proceedings of the Tenth European Conference on Artificial Intelligence ({ECAI}'92)'\ c.359-363,1992.

28.Kautz H., Selman B. Pushing the Envelope: Planning Propositional Logic and Stochastic Search II Proceedings of the Thirteenth National Conference on Artificial Intelligence. -Menlo Park, Calif. - 1996. - с 1194-1201

29.Koehler J., Nebel В., Hoffmann J., Dimopoulos Y. Extending Planning Graphs to an ADL Subset, ECP-97, pages 273-285, Springer LNAI 1348

Kumar V. Algorithms for constraint-satisfaction problems: A survey. //AI Magazine, 13(1):32--44,1992. <http://citeseer.ni.nec.com/kumar92algorithms.html>

30.Lifschitz V. On the Semantics of STRIPS. In Reasoning About Actions & Plans, Morgan Kaufmann Publishers: San Mateo, CA, 1986

31.Long D., Fox M. Efficient Implementation of the Plan Graph in STAN, Volume 10, pages 87-115,1999

32.McAHester D., Rosenblit D. Systematic nonlinear planning // Proceedings of AAAI-91, Anaheim, Ca, 1991

33.McDermott, D. A Heuristic Estimator for Means-Ends Analysis in Planning // In Proceedings of the Third International Conference on AI Planning Systems. - 1996. -c.142-149. Menlo Park, Calif.: AAAI Press

34.Nadel B. Some Applications of the Constraint-Satisfaction Problem /Технический отчёт № CSC-90-008, Computer Science Dept., Wayne State Univ.

35.Newell A., Shaw J. Programming the logic theory machine // In Proceedings of the Western Joint Computing Conference, c.230-240,1957.

36.Newell A., Simon H. GPS, a program that simulates human thought // Computers and Thought, eds: E.A. Feigenbaum and J. Feldman, McGraw Hill, NY, 1963

37.Penberthy S., Weld D. UCPOP: A Sound, Complete, Partial-Order Planner for ADLII Proceedings of the Third International Conference on the Principles of Knowledge Representation. - San Francisco, Calif. - 1992. - c. 103-114

38.Raphael B. The frame problem in problem solving systems // Artificial Intelligence and Heuristic Programming. -1971, c.159-169. Edinburgh Univ. Press, Edinburgh, Scotland

39.Refanidis I., Vlahavas I. "The GRT Planner: Backward Heuristic Construction in Forward State-Space Planning", Journal of Artificial Intelligence Research, 15 (2001), c. 115-161 (Postscript, gzipped Postscript, PDF, HTML, OnlineAppendix)

40.Robinson J.A. A machine-oriented logic based on the resolution principle // Journal of the ACM, 12(1):23-41., 1965.

41.Sacerdoti E.D. Planning in a hierarchy of abstraction spaces // Artificial Intelligence. -1974.-№5.-C.l 15-1350

42.Sacerdoti E.D. The nonlinear nature of plans II Proceedings of the Fourth International Joint Conference on Artificial Intelligence (UCAI-75). - Tbilisi, Georgia. - 1975. - c.206-214

Stoerr H. BDDPlan // <http://www.ki.inf.tu-dresden.de/~stoerr/bddplan.html>

42.Sussman G. A Computational Model of Skill Acquisition. // PhD thesis, MIT, Cambridge, Massachusetts, August 1973

43.Tate A. Generating Project Networks // Proceedings of the Fifth International Joint Conference on Artificial Intelligence. - Menlo Park, California. - 1977. - c.888-893

44.Tate A., Currie K. O-Plan: The Open planning architecture // Artificial Intelligence. -1991.-№52.-c.49-86

Veloso M., Carbonell J. Integrating planning and learning" // Journal of Experimental and Theoretical Artificial Intelligence, Том 7, № 1. - 1995 If <http://citeseer.nj.nec.com/veloso95integrating.html>

50.Weld D., Smith D. Temporal Planning with Mutual Exclusion Reasoning // In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. 1999.

51.Wilkins D. Can AI planners solve practical problems? // Computational Intelligence. - 1990. - Tom 6. -№4. - c.232-246

52.Yang Q., Tenenberg J.D. ABTWEAK: Abstracting a nonlinear least commitment planner II Proceedings of the Eighth National Conference on Artificial Intelligence. -Boston, MA. - 1990. - с 204-209

53.Википедия свободная энциклопедия. Теорема Гёделя о неполноте. http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D1%8B_%D0%93%D1%91%D0%B4%D0%B5%D0%BB%D1%8F_%D0%BE_%D0%BD%D0%B5%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B5

54.Информационноый портал Propedia. Язык логического программирования Visual Prolog. http://progopedia.ru/implementation/visual-prolog

55.Чистякова М.А. Учебное пособие по дисциплине «Теоретические основы автоматизированного управления». МГУПИ. Москва. 2007г. С 14-21

56.Тарханов Т.С. Интеллектуальная система приобретения знаний // Материалы региональной научно-практической конференции "Компьютерные технологии в науке, экономике и образовании" (CT+SEE2000) // Махачкала, 2000, с. 135-139

57.Гетия И.Г. Безопасность при работе на ПЭВМ, И. - М.: МГУПИ, 2005, 73с.

58.СанПиН 2.2.2/2.4.1340-03 «Гигиенические требования к персональным электронно-вычислительным машинам и организации работы». 2003 г.

59.Гетия И.Г., Шумилин В.К., Леонтьева И.Н., Гетия С.И., Кривенцов С.М., Комиссарова Т.А., Скребенкова Л.Н., Костюченко В.Е. Экология компьютерной техники. - Учебное пособие. - М.: МГУПИ, 2007 г. - 69 с.

60.Шалимов Б.С. Методические указания по выполнению организационно-экономической части дипломных проектов для студентов всех специальностей, разрабатывающих интегрированные производственные системы. Учебное пособие. ¾ М.: МИП, 1989.

61.Капелюш Г.С., Шестоперов С.Б. Технико-экономическое обоснование дипломных проектов по созданию программных средств вычислительной техники и информатики. Учебное пособие для студентов специальности 22.01. ¾ М.: МИП, 1993.

62.Организация, планирование и управление предприятием машиностроительной промышленности. Методические указания по выполнению курсовой работы для студентов специальности 22.02. ¾ М.: МИП, 1989.

63.Прайс-лист ООО «Неррис» 20.02.2011.