Точно Не проект 2 / Не books / Источник_1

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

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

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

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

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

Структурная схема рассмотренной ПСИИ является обобщенной. В схемах реальных ПСИИ могут отсутствовать некоторые из рассмотренных блоков. Наличие тех или иных связей в конкретной системе в значительной степени определяется её назначением.

Рассмотренная ПСИИ относится к группе организационноуправляющих систем, используемых при оперативном управлении, контроле качества, планировании и т.д. В этой группе систем выделяют три типа ИС [2]: вопросно-ответные системы, позволяющие взаимодействовать с базами данных на ограниченном ЕЯ; расчетно-логические системы, позволяющие пользователю, не являющемуся специалистом в области вычислительной техники, автоматически выбрать метод решения задачи и формировать программу ее решения в диалоге; экспертные системы – системыконсультанты, аккумулирующие знания и опыт экспертов в той или иной области и позволяющие менее квалифицированным пользователям получать консультации.

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

Интеллектуальные роботы (ИР) относятся к группе робототехнических систем. ИР представляет собой систему, обладающую способностью накапливать и корректировать знания на основе активного восприятия информации о внешнем мире, а также осуществлять целенаправленное поведение на основе накопленных знаний [35]. Обобщенная структурная схема интеллектуального робота изображена на рисунке 1.2 [2,29,35]. В ней указаны три основные подсистемы: восприятия внешней информации, представления знаний, планирования и исполнения действий. Рассмотрим каждую из этих подсистем.

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

Рисунок 1.2 – Структурная схема робота с искусственным интеллектом

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

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

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

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

Вопросы для самопроверки

1.Проанализируйте существующие определения понятия “искусственный интеллект”. Составьте собственное определение.

2.Объясните причину критики теста Тьюринга.

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

4.Перечислите основные направления ИИ, дайте их краткую характеристику.

5.Приведите обобщенную структурную схему системы ИИ и объясните функции всех блоков, входящих в её состав.

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

7.Может ли компьютер в настоящее время решать следующие задачи:

а) делать открытия и доказывать теоремы; б) сочинять забавные рассказы;

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

д) управлять движением автомобиля в центре крупного города?

ГЛАВА 2

СПОСОБЫ ПРЕДСТАВЛЕНИЯ ЗАДАЧ И ПОИСК РЕШЕНИЙ

Термин “решение задач” (problem solving) употребляется в искусственном интеллекте в весьма ограниченном смысле. Речь идет о хорошо определенных задачах, решаемых на основе поисковых алгоритмов.

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

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

Поскольку под решателем задач в искусственном интеллекте понимается компьютер, то в настоящей главе рассматриваются способы представления задач, удобные для их решения на ЭВМ. К ним относятся следующие наиболее часто используемые способы:

-представление задач в пространстве состояний;

-представление, сводящее задачу к подзадачам;

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

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

2.1. Общая характеристика способов представления задач

2.1.1. Представление задач в пространстве состояний

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

-задание начальных состояний задачи;

-задание конечных (целевых) состояний задачи;

-задание операторов, преобразующих одни состояния задачи в другие.

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

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

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

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

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

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

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

(S0, S, F, G),

где S – множество состояний;

S0 – множество начальных состояний, S0 S;

F – множество операторов, преобразующих одни состояния в другие; G – множество целевых состояний, G S.

Каждый оператор f F является функцией, отображающей одно состояние в другое – sj=f(si ) , где si, sj S. Решением задачи является последовательность операторов fi F, преобразующих начальные состояния в конечные, т.е. fn(fn-1(…(f2(f1(S0 )))…)) G . Если такая последовательность не одна и задан критерий оптимальности, то возможен поиск оптимальной последовательности.

Удобно поиск решений в пространстве состояний представлять в виде графа состояний. Множество вершин графа соответствует состояниям задачи, а множество дуг (ребер) – операторам. В этом случае поиск решения задачи может интерпретироваться как поиск пути на графе.

мального пути можно выбрать один из двух путей с минимальной стоимостью.

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

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

2.1.2. Сведение задач к подзадачам

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

Пространство задач представляется в виде направленного графа, который называется графом редукции задачи. С каждой вершиной этого графа связывается определенная подзадача, а дуги соответствуют операторам порождения подзадач. В графе редукции задачи существуют два типа вершин: конъюнктивные и дизъюнктивные. Конъюнктивные вершины, или вершины типа “И”, указывают, что для решения задачи требуется решить все ее подзадачи. Дизъюнктивные вершины – вершины типа “ИЛИ” – соответствуют альтернативным подзадачам. Для решения задачи, представляемой такой вершиной, достаточно решить только одну из ее подзадач.