В. Н. БОНДАРЕВ

Ф.Г. АДЕ

ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ

Рекомендовано Министерством образования и науки Украины

в качестве учебного пособия для студентов высших учебных заведений

2002

ББК 32.813

Б811

УДК 004.8(075)+004.93(075)

Рецензенты:

Мохор В. В., д-р техн. наук, заведующий отделом специализированных средств

моделирования Института проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины;

Суворов А. М., д-р физ.-мат. наук, заведующий отделом морских информационных систем и технологий Морского гидрофизического института НАН Украины;

Теленик С.Ф., д-р техн. наук, профессор, заведующий кафедрой автоматики и управления в технических системах Национального технического университета Украины “Киевский политехнический институт“ Решение МОН Украины о присвоении грифа “Рекомендовано в качестве учебного пособия для студентов высших учебных заведений” № 14/18.2-1313 от 17.06. Бондарев В.Н.

Искусственный интеллект:Учеб. пособие для вузов/ В.Н. Бондарев, Ф.Г. Аде.Б Севастополь: Изд-во СевНТУ,2002. – 615с.: ил.

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

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

ISBN 966-7473-45-7 © Бондарев В.Н., Аде Ф.Г.,

СОДЕРЖАНИЕ

ПРЕДИСЛОВИЕ…….…………………………………………………... СПИСОК СОКРАЩЕНИЙ…………………………………………….. Глава 1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ….…………... 1.1. Понятие “искусственный интеллект”…….…………………. 1.2. Этапы развития искусственного интеллекта ……………….. 1.3. Основные направления исследований………………………. 1.3.1. Представление задач и поиск решений…………….. 1.3.2. Доказательство теорем………………………………. 1.3.3. Представление знаний……………………………….. 1.3.4. Экспертные системы…………………………………. 1.3.5. Обучение и выявление закономерностей…………… 1.3.6. Общение на естественном языке…………………….. 1.3.7. Распознавание образов……………………………….. 1.3.8. Компьютерное зрение………………………………… 1.3.9. Языки программирования……………………………. 1.4. Структура систем с искусственным интеллектом…………… Вопросы для самопроверки………………………………………… Глава 2. СПОСОБЫ ПРЕДСТАВЛЕНИЯ ЗАДАЧ И ПОИСК РЕШЕНИЙ……………………………………………………… 2.1. Общая характеристика способов представления задач……… 2.1.1. Представление задач в пространстве состояний……. 2.1.2. Сведение задач к подзадачам………………………… 2.1.3. Представление задач в виде теорем…………………. 2.2. Поиск решений задач в пространстве состояний……………. 2.2.1. Методы “слепого” поиска…………………………….. 2.2.1.1. Случайный поиск…………………………….. 2.2.1.2. Поиск “в глубину и ширину”……………….. 2.2.1.3. Алгоритм равных цен………………………… 2.2.2. Эвристический поиск…………………………………. 2.2.2.1. Алгоритм “подъема на гору”…………..…….. 2.2.2.2. Глобальный учет соответствия цели………… 2.2.2.3. А-алгоритм……………………………………. 4 Содержание 2.2.3. Поиск с распространением ограничений…………….. 2.3. Поиск решений при сведении задач к подзадачам………….. 2.3.1. Алгоритм поиска в глубину …………………..…….. 2.3.2. Алгоритм эвристического поиска в И-ИЛИ графе…. 2.3.3. Поиск решений в игровых программах……………… 2.3.3.1. Минимаксный метод………………………… 2.3.3.2. Альфа-бета поиск……………………………. Вопросы для самопроверки…………………………………………. Глава 3. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ……………………………….. 3.1. Знания и их представление в СИИ…………………………….. 3.2. Логические модели……………………………………………… 3.2.1. Формальные системы………………………………….. 3.2.2. Исчисление высказываний…………………………….. 3.2.3. Исчисление предикатов………………………………... 3.2.4. Логики высокого порядка и псевдофизические логики……………………………... 3.3. Продукционные модели………………………………………… 3.3.1. Продукционные системы………………………………. 3.3.2. Управление выводом в продукционных системах…… 3.4. Семантические сети…………………………………………….. 3.4.1. Общее понятие о семантических сетях………………. 3.4.2. Способы описания семантических сетей 3.5. Фреймы………………………………………………………….. 3.5.1. Структура фрейма……………………………………… 3.5.2. Управление выводом………………………………….. Вопросы для самопроверки ………………………………………… Глава 4. ОСНОВНЫЕ МОДЕЛИ ВЫВОДА…………………………. 4.1. Дедуктивный вывод в исчислении предикатов………………. 4.1.1. Формулировка задачи дедуктивного вывода………… 4.1.2. Стандартизация предикатных формул……………….. 4.1.3. Метод Эрбрана…………………………………………. 4.1.4. Принцип резолюции……………………………………. 4.1.5. Стратегии поиска………………………………………. 4.1.6. Применения принципа резолюции……………………. 4.1.6.1. Информационный поиск……………………… 4.1.6.2. Планирование перемещений робота…………. 4.1.6.3.Автоматическое написание программ……… Содержание 4.1.7. Принцип резолюции и система STRIPS………………. 4.1.8. Принцип резолюции и язык Пролог…………………... 4.2. Выводы в условиях ненадежных или неполных знаний…… 4.2.1. Виды неопределенности……………………………… 4.2.2. Ненадежные знания и выводы……………………….. 4.2.2.1. Байесовский метод…………………………… 4.2.2.2. Метод коэффициентов уверенности………… 4.2.2.3. Теория свидетельств Демпстера-Шефера…… 4.2.2.4. Нечеткие множества и нечеткая логика…….. 4.2.3. Неполнота знаний и немонотонный вывод………….. 4.3. Индуктивный вывод……………………………………………. 4.3.1. Основные понятия индуктивного обобщения……….. 4.3.2. Алгоритм Уинстона……………………………………. 4.3.3. Алгоритм Митчелла……………………………………. 4.3.4. Алгоритм обобщения ID3……………………………… Вопросы для самопроверки…………………………………………. Глава 5. ЯЗЫК ЛИСП……………………………………………………. 5.1. Общая характеристика языка………………………………… 5.2. Основные понятия языка…………………………………….. 5.3. Интерпретация Лисп-программ……………………………… 5.4. Арифметические функции…………………………………… 5.5. Основные функции обработки списков…………………….. 5.6. Присваивание значений……………………………………… 5.7. Предикаты…………………………………………………….. 5.8. Определение функций……………………………………….. 5.9. Связывание и область действия переменных………………. 5.10. Последовательные и условные вычисления………………… 5.11. Итерационные циклические вычисления…………………… 5.12. Рекурсивные функции………………………………………... 5.13. Структурно-разрушающие функции………………………… 5.14. Ассоциативные списки и списки свойств…………………… 5.15. Типы данных………………………………………………….. 5.16. Ввод-вывод…………………………………………………… 5.17. Функционалы…………………………………………………. 5.18. Макролитеры…………………………………………………. 5.19. Замыкания…………………………………………………….. 5.20. Структуры…………………………………………………….. 5.21. Объектно-ориентированное программирование…………… 5.22. Макросы………………………………………………………. 5.23. Пакеты………………………………………………………… 5.25. Программирование задач ИИ на языке ЛИСП…………….. 5.25.3. Эвристический поиск на основе А-алгоритма……. 5.25.5. Поиск в семантических сетях………………………. 6.1. Общая характеристика языка………………………………. 6.2. Основные понятия языка…………………………………… 6.3. Операторы…………………………………………………… 6.4. Арифметические выражения………………………………. 6.6. Управление возвратом (отсечение)………………………… 6.7. Отрицание в языке Пролог…………………………………. 6.8. Метаусловия…………………………………………………. 6.9. Организация циклов…………………………………………. 6.10. Встроенные предикаты……………………………………… 6.10.1. Предикаты ввода-вывода………………………….. 6.10.2. Предикаты обработки термов……………………… 6.10.3. Предикаты работы с базой данных………………… 6.11. Решение задач ИИ на языке Пролог………………………… 6.11.1. Создание и обработка бинарных деревьев………… 6.11.2. Поиск решений в пространстве состояний………… 6.11.2.2. Поиск в ширину……………………………. 6.11.2.3. Эвристический поиск………………………. 6.11.3. Поиск решений в И-ИЛИ графах………………….. 6.11.4. Поиск в пространстве версий………………………. 6.11.5. Поиск в сети фреймов………………………………. Вопросы для самопроверки ……………………………………….. 7.1. Основные функции и компоненты экспертных систем……. 7.2. Разработка экспертных систем………………………………. 7.4. Поиск и объяснение решений……………………………….. Содержание 7.5. Реализация экспертной системы на языке Лисп…………… 7.6. Реализация экспертной системы на языке Пролог………… 7.6.1. Представление знаний правилами…………………… 7.6.2. Представление знаний фреймами……………………. Вопросы для самопроверки…………………………………………. 8.1. Основные сведения о распознавании образов……………… 8.2. Геометрический метод распознавания……………………… 8.3. Байесовский метод распознавания………………………….. 8.4. Рекуррентные алгоритмы обучения 8.5. Распознавание и обучение на основе 8.5.4. Обучение с учителем в ИНС с прямыми связями…… 8.5.6. ИНС с фиксированными весами связей 8.5.7. Коннекционистские экспертные системы…………… 8.6. Синтаксический метод распознавания……………………… 9.3. ЕЯ-интерфейс доступа к базам данных……………………. 9.4. Распознавание речи………………………………………….. 9.4.2. Предварительная обработка и распознавание звуков. 9.4.3. Статистический подход к распознаванию речи…….. 9.5. Синтез речи по тексту………………………………………… 9.5.1. Основные понятия……………………………………… 9.5.2. Методы синтеза речевых сигналов…………………… 9.5.3. Определение управляющих параметров синтезаторов Вопросы для самопроверки……………………………………….. Глава 10. КОМПЬЮТЕРНОЕ ЗРЕНИЕ……………………………….. 10.1. Основные понятия……………………………………………. 10.2. Система зрения человека…………………………………….. 10.3. Системы компьютерного зрения…………………………….. 10.4. Выделение граничных элементов……………………………. 10.5. От граничных элементов к граничным сегментам…………. 10.5.1. Преобразование Хафа……………………………….. 10.5.2. Поиск при выделении контурных сегментов………. 10.5.3. Активные контурные модели……………………….. 10.6. Выделение областей изображения……..…………………… 10.7. Интерпретация контурных рисунков…..…………………… 10.8. Распознавание объектов в системах зрения роботов……… 10.8.1. Системы зрения роботов и компьютерное зрение… 10.8.2. 2D-модели……………………………………………. 10.8.3. 3D-методы……………………………………………. 10.9. Примеры методов распознавания изображений……………. 10.9.1. 2D-методы, использующие глобальные признаки… 10.9.2. 2D-методы, использующие локальные признаки….. 10.9.3. 2D-метод, использующий граф отношений……….. 10.9.4. Пример 3D-метода…………………………………… Содержание Вопросы для самопроверки…………………………………………. БИБЛИОГРАФИЧЕСКИЙ СПИСОК………………………………….. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ…………………………………………..

ПРЕДИСЛОВИЕ

Дисциплина “Искусственный интеллект” играет фундаментальную роль в подготовке специалистов в области информатики и вычислительной техники. Различные учебные курсы, относящиеся к проблематике искусственного интеллекта (ИИ), включены в учебные планы многих университетов. Ассоциациями ACM, AIS и AITP разработана программа подготовки специалистов в области информационных систем, которая рекомендуется для международного использования1). Программой предусматривается в рамках дисциплины “Искусственный интеллект” рассмотрение следующих тем: история, основные понятия и направления развития ИИ; представления задач и пространства поиска решений; основные стратегии управления выводом (поиск в глубину и в ширину, прямой и обратный вывод); эвристический поиск; представление знаний; экспертные системы и оболочки;

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

Несмотря на обилие книг, посвященных вопросам ИИ, учебное пособие, в котором бы систематически рассматривались все указанные выше темы, на территории СНГ не издавалось. Большинство книг было издано в 70-е и 80-е годы, т.е. почти четверть века назад. Многие из них являются научными, справочными или научно-популярными изданиями и не подходят для использования в учебном процессе. Исключением является изданный недавно учебник Т. А. Гавриловой и В. Ф. Хорошевского (см. библиографический список). Однако он преимущественно посвящен вопросам инженерии знаний и системам ИИ, основанным на знаниях.

Цель издания учебного пособия – обеспечить систематическое рассмотрение всего спектра тем, рекомендованных для изучения программой подготовки специалистов в области информационных систем, включая как изложение общих подходов и принципов ИИ, так и алгоритмических основ Davis G. B. IS’97 Model Curriculum and Guidelines for undergraduate Degree Programs in Information Systems / G.B. Davis, J.T. Gorgone, J.D. Couger, D.J. Feinstein, H.E. Longenecker – Park Ridge: AITP inc., 1997. – 94 p.

их реализации. Последнее обстоятельство представляется весьма важным.

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

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

В-третьих, широким использованием этих языков при создании прототипов интеллектуальных систем. В-четвертых, стремлением авторов наполнить пособие примерами реализации соответствующих принципов ИИ, и сделать его удобным для чтения широким кругом читателей. Во второй части рассматриваются различные направления ИИ (главы 7 - 10). При этом в зависимости от специализации студентов, слушающих курс, основные акценты могут быть сделаны на различных направлениях ИИ. Авторы рекомендуют изучать первую часть курса в рамках программы подготовки бакалавров, а вторую – в рамках программ подготовки специалистов или магистров. При чтении первой части рекомендуется следующий порядок изучения глав и параграфов: 1, 2, 5, 3, 4.1, 6.1 – 6.10, 4.2 – 4.3, 6.11. Это позволяет параллельно с лекционным курсом проводить занятия лабораторного практикума на языках Лисп и Пролог.

Учебное пособие основано на материалах лекций, прочитанных авторами для студентов старших курсов Севастопольского национального технического университета и Швейцарского федерального технологического университета (ETH, г. Цюрих). Книга предназначена для студентов, обучающихся по направлению “Компьютерные науки”, специальность “Информационные управляющие системы и технологии”. Она будет полезна студентам, обучающимся по направлениям “Компьютерная инженерия” и “Компьютеризированные системы автоматики и управления”, а также разработчикам интеллектуальных систем.

Предисловие В заключение авторы благодарят профессора Г. Сцекели и администрацию ЕТН за помощь в издании книги, а также рецензентов – д-ра техн.

наук B. B. Мохора, д-ра физ.-мат. наук А.М. Суворова и д-ра техн. наук, профессора С.Ф. Теленика за доброжелательную критику и полезные замечания, которые способствовали улучшению книги. Особую благодарность авторы выражают д-ру техн. наук, профессору В.К. Маригодову за его большой труд по редактированию рукописи, а также канд-ту техн. наук Карлусову В.Ю. за внимательное первое чтение рукописи и многочисленные замечания. Авторы признательны доктору Дж. Кризу, любезно предоставившему материалы, использованные в 6 и 7 главах книги.

Введение, главы 1,3,4,6,7,8,9 написаны В.Н. Бондаревым, глава написана Ф.Г. Аде, главы 2 и 5 написаны авторами совместно.

Отзывы и предложения просьба направлять по адресу: Украина, 99053, г. Севастополь, Студгородок, Севастопольский национальный технический университет, НМЦ.

СПИСОК СОКРАЩЕНИЙ

АМ – акустическая модель АРР – автоматическое распознавание речи АРТ – теория адаптивного резонанса АСУП – автоматизированная система управления производством БД – база данных БЗ – база знаний ЕЯ – естественный язык ЗКР – список закрытых вершин ИИ – искусственный интеллект ИНС – искусственная нейронная сеть ИР – интеллектуальный робот ИС – интеллектуальная система ЛНЭ – линейный непрерывный элемент ЛПК – линейное предиктивное кодирование ЛПР – лицо, принимающее решение ЛПЭ – линейный пороговый элемент МР – магнитный резонанс НОУ – наиболее общий унификатор НЭ – нейроподобный элемент ОТК – список открытых вершин ПЗС – приборы с зарядовой связью ПО – программное обеспечение ППФ – правильно построенная формула ПрО – предметная область ПСИИ – производственная система с искусственным интеллектом ПЭ – процессорный элемент РСП – расширенная сеть переходов СИИ – система искусственного интеллекта СММ – скрытая Марковская модель СПЗИ – система поддержания значений истинности СУБД – система управления базой данных ТДШ – теория Демпстера-Шефера УК – правило универсальной конкретизации ФС – формальная система ЦФ – цифровой фильтр ЭК – правило экзистенциональной конкретизации ЭС – экспертная система ЯПЗ – язык представления знаний

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

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

В главе рассматриваются наиболее распространенные определения понятия “искусственный интеллект”, описываются этапы развития ИИ, анализируются основные направления исследований.

1.1. Понятие “искусственный интеллект” Несмотря на все попытки дать точное определение понятию “искусственный интеллект”, строгого определения не существует. Поэтому будет полезным, по крайней мере, обозначить границы этого понятия. С этой целью рассмотрим наиболее распространенные определения. Так, И.

Рич полагает, что ИИ – это область исследований, направленная на создание компьютеров, которые выполняют такие функции, которые в настоящий момент человек выполняет лучше [84]. Речь идет о функциях, связанных с умением воспринимать, анализировать, рассуждать, использовать знания, планировать свои действия и т.д., в которых естественно проявление интеллекта. Характерной особенностью этого определения являет ся указание на то, что эти функции, в настоящий момент времени, хорошо выполняются человеком и плохо компьютером. Это означает, что проблематика ИИ меняется со временем. В этом смысле, близким к рассмотренному определению является определение, предложенное Дж. Аленом: “ИИ – это наука о создании машин, решающих задачи, которые могут решать люди…”[57]. Можно отметить, что данное определение охватывает многие исследования, выполняемые в области компьютерных наук. Например, сложение чисел – задача, которую могут решать люди. Тем не менее, мы сейчас вряд ли назовем эту задачу интеллектуальной. Однако если суммирующее устройство было бы предъявлено человечеству в средние века, то оно, безусловно, было бы отнесено к разряду интеллектуальных. Это говорит о том, что наши представления о “думающей машине” эволюционируют во времени. Поэтому в фокусе искусственного интеллекта оказываются те задачи, которые успешно решаются человеком и плохо – компьютером.

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

Введенные выше определения ИИ являются сравнительными. Они сопоставляют возможности человека и машин. В 1950 году был предложен эмпирический тест А. Тьюринга для определения уровня интеллектуальности машин. В соответствии с тестом эксперт с помощью телетайпа мог вступать в диалог либо с компьютером, либо с человеком. Тьюринг предложил считать поведение компьютера интеллектуальным, если в диалоге участвовал компьютер, а эксперт был не в состоянии определить, с кем он ведет диалог. Тест Тьюринга не рассматривает механизмы формирования ответов на вопросы эксперта, и, следовательно, позволяет исключить все вопросы об “истинной” природе интеллекта. Несмотря на ряд недостатков, тест Тьюринга создал основу для оценки многих современных систем ИИ.

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

Под воздействием указанной критики были предложены иные определения ИИ, например:

- ИИ – ветвь информатики, которая связана с автоматизацией интеллектуального поведения [77];

- ИИ – это наука о вычислениях, которые делают возможными восприятие, логический вывод и действие [95];

- ИИ – это информационная технология, связанная с процессами логического вывода, обучения и восприятия [91].

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

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

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

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

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

Рассмотрим подробнее этапы развития ИИ.

1.2. Этапы развития искусственного интеллекта Исследования в области ИИ начались сразу же после появления первых электронных компьютеров. За 50 лет ИИ прошел в своем развитии несколько этапов. Опишем их в хронологическом порядке.

Становление искусственного интеллекта (1943 - 1956 гг.). Работы в области искусственного интеллекта начались с зарождения нейрокибернетики. Связано это было с тем, что основу мозга образуют нервные клетки – нейроны. Поэтому исследователи в ранний период развития ИИ пытались строить разумные машины, имитируя поведение коллектива нейронов. В 1943 г. У. Маккаллох и У. Питтс предложили модель формального логического нейрона, который мог находиться в двух устойчивых состояниях. Д. Хебб (1949 г.) разработал простое правило, позволяющее изменять веса связей между нейронами с целью их обучения. В 1951 году М.

Минский и Д. Эдмондс разработали нейрокомпьютер, который содержал 40 нейронов. Эти первые работы в области ИИ обозначили два основных подхода к разработке СИИ – логический и коннекционистский.

Термин “искусственный интеллект” был предложен на семинаре с аналогичным названием, который проходил в Дартсмутском колледже (США) летом 1956 года. Семинар был организован М. Минским и Дж.

Маккарти. Среди участников семинара были Г. Саймон и А. Ньюэлл, которые разработали программу “Логик-теоретик”, предназначенную для доказательства теорем в исчислении высказываний. Именно этих четырех исследователей считают “отцами” ИИ. М. Минский и Дж. Маккарти основали лабораторию ИИ в Массачусетском технологическом институте, а Г.

Саймон и А. Ньюэлл в университете Карнеги-Меллона. Позже Дж. Маккарти перешел в Стэнфордский университет. В этих трех университетах, а также в Эдинбургском университете выполнялись первые работы, обеспечившие становление ИИ.

Эвристический поиск и доказательство теорем (1956 – 1969 гг.).

Работы Г. Саймона и А. Ньюэлла по созданию программы “Логиктеоретик” были завершены в 1957 г. С помощью этой программы был успешно доказан ряд теорем из книги Уайтхеда и Рассела “Principia mathematica”. Один из недостатков программы состоял в том, что она неэффективно осуществляла поиск решений. А. Ньюэлл и Г. Саймон заинтересовались общими методами поиска решений, приступив к созданию следующей программы, которую назвали “Универсальный решатель задач”. Эту программу обычно называют GPS по первым буквам английского названия General Problem Solver. GPS разрабатывалась с целью имитации процесса решения задач человеком и базировалась на идеях эвристического поиска.

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

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

В этот же период Дж. Маккарти создает язык Лисп, который становится доминирующим языком программирования систем ИИ. В 1958 году Маккарти публикует статью “Программы и здравый смысл”, в которой описывает гипотетическую программу “Advice Taker”, центральной идеей которой было представление знаний и логический вывод.

Идея Маккарти использовать логику для построения СИИ была развита в работах Дж. Робинсона. В 1965 г. Робинсон разрабатывает метод резолюций, который позволяет автоматизировать процесс доказательства теорем при наличии исходных аксиом. Логические представления кладутся в основу вопросно-ответной системы, разработанной К. Грином (1969 г.), и в основу робота “Шейки”, который был создан в 1969 г. в Стэнфордском исследовательском институте.

В начале 60-х годов интенсивно развивались исследования в области нейронных сетей. Правило адаптации весов связей нейронных элементов, предложенное Д. Хеббом, было усовершенствовано в работах Б. Уидроу (1962 г.), который разработал нейронную сеть под названием Adaline, а также в работах Ф. Розенблатта, создавшего персептрон (1962 г.). Персептрон Розенблатта представлял собой устройство, предназначенное для распознавания зрительных образов. В частности, с помощью персептрона можно было различать буквы алфавита. Розенблатт доказал теорему сходимости персептрона, обеспечившую теоретическую базу алгоритмам обучения персептрона. Однако возможности персептрона Розенблатта оказались весьма ограниченными. Он не мог распознавать частично закрытые буквы, а также буквы иного размера, нежели те, которые предъявлялись ему в процессе обучения. Вскоре М. Минский в соавторстве с С. Пейпертом (1969 г.) написал книгу, в которой доказал, что персептрон Розенблатта не в состоянии выполнять многие функции, предсказанные Розенблаттом. Это привело к сокращению ассигнований, выделяемых на развитие нейроинформатики, о чем позже Минский высказывал сожаление.

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

Представление знаний (1969 – 1979 гг.). К концу 60-х годов было обнаружено, что для решения практически важных задач недостаточно одних знаний общего характера (общих стратегий поиска решений). Успешное решение прикладных задач возможно только при наличии хорошо структурированных специальных знаний.

Программа DENDRAL, разработанная в 1969 году Э. Фейгенбаумом, Б. Букхененом и Э. Ледербергом, содержала детальные сведения из области органической химии и помогала химикам определять молекулярную структуру неизвестных органических соединений по данным, получаемым с помощью масс-спектрометра. Масс-спектрометр, разделяя молекулы на фрагменты, измеряет массу и электрический заряд каждого из фрагментов.

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

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

Вдохновленные успехом программы DENDRAL Э. Фейгенбаум, Б.

Букхенен и Э. Шортлифф разрабатывают экспертную систему MYCIN.

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

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

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

Семантические сети были предложены в 1967 году М. Куиллианом.

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

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

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

В дальнейшем в сотрудничестве с Р. Абельсоном он разработал модель представления знаний, называемую “скриптами”, или сценариями. Шенк использовал скрипты в программе SAM, которая могла интерпретировать рассказы. В 1973 году В. Вудс создает систему LUNAR, которая позволяла геологам задавать вопросы на естественном языке относительно образцов пород, доставленных с Луны. LUNAR была первой используемой на практике системой с естественно-языковым интерфейсом доступа к базе данных.

Расширение приложений СИИ требовало развития моделей представления знаний. В рассматриваемый период были разработаны различные языки представления знаний. Некоторые из них базировались на логике. Так, в 1973 году А. Колмероэ создает язык логического программирования Пролог, ставший популярным в Европе. В США создается язык PLANNER, поддерживающий предикатный уровень представления знаний.

Часть языков использовала теорию фреймов, предложенную М. Минским (1975 г.). Фрейм представляет информационную структуру, состоящую из слотов, в которых собраны характеристики и соответствующие значения, обеспечивающие описание объектов или понятий. Фреймы организуются в иерархические сети, что позволяет экономно представлять знания в памяти ЭВМ. Для работы с фреймовыми моделями представления знаний были разработаны языки FRL, KRL, GUS и др.

Коммерческий успех (1979 – 1988 гг.). Первой интеллектуальной системой, нашедшей применение в промышленности, стала экспертная система К1, разработанная Мак-Дермоттом (1982 г.). Система К1 применялась для определения конфигурации компьютерных систем семейства VAX. Коммерческая версия системы, разработанная корпорацией Digital Equipment совместно с университетом Карнеги-Меллона (США), получила название XCON. К 1986 году система XCON позволяла корпорации Digital Equipment экономить 70 млн. долларов ежегодно. Кроме этого, применение системы сократило число ошибок с 30% до 1%.

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

В 1981 году Япония объявляет о начале проекта машин V поколения, базирующихся на принципах ИИ. Проект был рассчитан на 10 лет и преду сматривал, среди многих целей, создание Пролог-машины с возможностями общения на естественном языке. Этот проект способствовал активизации исследований в области ИИ во многих странах. К разработке интеллектуальных систем подключились многие компании – Texas Instruments, Xerox, Symbolics и др. Объемы финансирования проектов в области ИИ за 1980-1988 гг. выросли с нескольких миллионов до 2 млрд. долларов в году.

Возрождение нейроинформатики ( с 1986 г. по настоящее время).

После доказательства М. Минским ограниченных возможностей первых нейронных сетей исследования в этом направлении выполнялись учеными других областей знаний. В 1982 г. физик Дж. Хопфилд опубликовал работу, в которой проанализировал методами статистической механики свойства однослойной нейронной сети с симметричными связями. Хопфилд обнаружил возможность применения такой сети в задаче распознавания образов. Психологи Д. Румельхарт и Г. Хинтон, изучавшие модели нейросетевой памяти, заново открыли в 1986 году алгоритм обучения многослойного персептрона, названный алгоритмом обратного распространения ошибки. Ранее этот алгоритм был открыт Брайсоном и Хо в 1969 году [84].

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

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

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

Коллективистские модели ИИ (с 1996 г. по настоящее время).

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

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

Выделение и гиперболизация отдельных свойств интеллекта способствовали противопоставлению и расхождению различных школ ИИ. К на Основные понятия и определения чалу 90-х годов исследователи начали осознавать, что подобные трактовки ИИ носят весьма ограниченный характер и не учитывают реалии развития интеллекта человека. Во-первых, естественный интеллект интегрирует в себе весь спектр свойств интеллекта. Во-вторых, интеллектуальное развитие человека происходит в обществе, в процессе выполнения им определенной деятельности. В отрыве от взаимодействия с себе подобными развитие естественного интеллекта проблематично. Поэтому, начиная с начала 90-х годов, в ИИ стали преобладать две основные тенденции – интеграция и децентрализация [41,77,84,95].

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

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

В основе распределенного (децентрализованного) интеллекта лежит функционально-структурная единица – агент, способная [41]:

- воздействовать на других агентов и самих себя;

- образовывать свои собственные цели;

- общаться с другими агентами;

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

- воспринимать часть среды своего функционирования;

- строить локальное представление среды;

- выполнять обязанности и оказывать услуги;

- самовоспроизводиться.

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

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

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

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

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

- в пространстве состояний;

- в пространстве подзадач;

- в виде доказательства теорем.

Если задача представляется в пространстве состояний, то задают начальное и конечное состояние задачи, множество операторов, обеспечивающих перевод задачи из одного состояния в другое. Решение задачи сводится к поиску последовательности операторов, осуществляющих перевод задачи из начального состояния в конечное. Такой поиск осуществляется различными методами. Наиболее интересными являются методы эвристического поиска, в частности, А*- алгоритм, применяемый при решении многих задач: восстановление контуров изображений, распознавание речи, игровые задачи, планирование поведения роботов. Подробнее вопросы представления задач и поиска решений рассмотрены в главе 2.

Основные понятия и определения Доказательство теорем является чрезвычайно важной областью ИИ.

Рождение этого направления началось с создания программы “Логиктеоретик”, которая доказала ряд теорем математической логики. Однако ранние подходы к автоматизации доказательства теорем были не эффективны. Связано это было с экспоненциальным ростом числа логических выражений в процессе доказательства. Для ограничения количества выражений предлагались различные методы, но наиболее эффективным оказался метод резолюций, предложенный Робинсоном.

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

Это один из центральных вопросов ИИ. В системах искусственного интеллекта знания не могут быть представлены непосредственно в том виде, в котором они используются человеком. Необходим поиск таких форм отображения знаний, которые были бы подходящими для хранения в памяти компьютера. Эти формы знаний, которые называют моделями представления знаний, должны обладать достаточной выразительностью, удобством использования, эффективностью манипулирования. Выразительность означает способность модели одинаково хорошо представлять как обобщенные, так и конкретные знания, как из универсальных, так и из специальных предметных областей. Она также предполагает способность модели отражать неполные знания. Удобство использования означает, что модель представления знаний должна базироваться на понятиях, которые используют эксперты и пользователи. Это упрощает приобретение знаний и оценку их корректности. Эффективность манипулирования связана с возможностью быстрого извлечения необходимых порций знаний и выполнения на их основе соответствующих выводов. Поэтому под знаниями в СИИ понимают формализованные сведения, данные, на которые ссылаются в процессе логического вывода [37].

Знания, представляемые в СИИ в виде самостоятельных информационных компонент, хранятся в базе знаний.

Имеются четыре основные модели представления знаний:

- логическая модель;

- продукционная модель (модель, основанная на правилах);

- модель семантической сети;

- фреймовая модель.

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

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

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

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

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

Основные понятия и определения Перечень типовых задач, решаемых ЭС, включает: интерпретацию, диагностику, прогнозирование, мониторинг и др.

Узким местом в разработке ЭС является получение знаний. Направление ИИ, занимающееся проблемами получения и структурирования знания специалистов с целью последующей разработки баз знаний, называется инженерией знаний. Подробнее проблемы разработки ЭС рассмотрены в главе 7.

1.3.5. Обучение и выявление закономерностей В процессе испытаний экспертных систем выяснилось, что их возможности ограничены объемом информации, хранимой в базе знаний.

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

Проблема создания обучающихся систем интересовала исследователей с момента зарождения ИИ. Так, уже персептрон Ф. Розенблата использовал простейшие правила обучения. А. Сэмюэль (1962 г.) создал программу игры в шашки, которая могла накапливать опыт игры и действовать, исходя из него. Идеи Сэмюэля были восприняты другими исследователями. В 1973 г. П. Уинстон увлекся проблемой обучения на примерах и составил программу “Арки”, которая могла на примерах обучаться простейшим понятиям. Крупным шагом вперед в машинном обучении стала программа AQ11, разработанная Р. Михальским (1976 г.). Программа AQ11 могла по данным выводить правила “если-то” для определения заболеваний растений.

Существенный вклад в решение проблемы обучения внес Д. Ленат, создав программу “Автоматический математик” (АМ). Эта программа была снабжена определенными знаниями из области чисел и набором эвристических правил, позволяющих устанавливать закономерности. Программа АМ повторно открыла около 200 важных понятий теории чисел. Позже Д. Ленат создал обучающуюся программу EURISKO, которая открыла новый способ построения логического элемента для сверхбольших интегральных схем – трехмерный элемент типа И/ИЛИ.

Другими важными исследованиями, выполненными в этой области, стали работы Т. Митчелла и Дж. Квинлана.

Характерной особенностью обучающихся систем является использование индуктивных умозаключений. Индукция – способ рассуждения от частного к общему. Индукция противоположна дедукции – суждению от общего к частному. Применение индуктивных схем рассуждений позволя ет программам обучаться на примерах путем их обобщения. Данные вопросы обсуждаются в главе 4.

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

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

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

- морфологический анализ – поиск основ слов с отнесением их к определенным грамматическим категориям, обнаружение и исправление орфографических ошибок;

- синтаксический анализ – грамматический разбор предложений и определение их лингвистической структуры;

- семантический анализ – формирование смысла предложений на внутреннем языке системы;

- прагматический анализ – выявление взаимосвязи между предложениями текста.

В последнее время в задачах обработки ЕЯ все чаще применяют эмпирический подход, базирующийся на использовании методов статистики и машинного обучения. В этом случае подсистема понимания высказываний обучается на больших объемах реальных языковых данных. Это по Основные понятия и определения зволяет автоматизировать процесс формирования необходимых баз знаний (см. главу 9).

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

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

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

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

Более 85% информации человек получает с помощью зрения. Для современного компьютера этот канал ввода информации также играет важную роль. Но ввести изображение в память ЭВМ нетрудно. Для машины намного сложнее понять изображение. Поэтому главная задача, которую приходится решать при построении систем машинного зрения, – это не создание устройств ввода изображений, а разработка методов и алгоритмов анализа визуальной информации. Проблема создания систем ком пьютерного зрения тесно связана с такими направлениями ИИ, как представление знаний, обучение, распознавание образов (см. главу 10).

1.3.9. Языки программирования систем искусственного интеллекта В рамках этого направления разрабатываются специальные языки для решения задач ИИ. Важной особенностью этих языков является использование более высоких уровней абстракции данных, а также ориентация на обработку символьной информации. Наиболее популярными языками, применяемыми при создании исследовательских прототипов СИИ, являются языки Лисп и Пролог.

Кроме этого, создаются специальные инструментальные средства, ориентированные на промышленную разработку СИИ, например, G2, ART, KEE, Knowledge Craft и др. [12,63]. В книге подробно рассматриваются языки Лисп и Пролог (см. главы 5 и 6).

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

- синтез изображений по моделям;

- интеллектуальные роботы;

- генетические алгоритмы;

- многоагентные системы;

- когнитивное моделирование;

- игры и машинное творчество, и многое другое.

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

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

Структурная схема ПСИИ изображена на рисунке 1.1 [2]. Такая ПСИИ может решать несколько характерных задач: управление, прогнози Основные понятия и определения рование, мониторинг, диагностика и др. Основным элементом ПСИИ является база знаний (БЗ), в которой хранятся знания о предметной области, представленные в компьютерно интерпретируемой форме.

Рисунок 1.1 – Производственная система с искусственным интеллектом Знания в БЗ представляются фактами и правилами. Факты – данные, характеризующие конкретные объекты, явления, ситуации предметной области. Применяя правила к фактам, можно получать новые факты, которых не было в системе. Для того чтобы из известных фактов получать новые факты, правила необходимо применять в соответствии с некоторыми принципами управления, которые реализуются машиной вывода.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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