Описаны фундаментальные вопросы из области искусственного интеллекта, лежащ) в основе многих приложений к обработке естественного языка, автоматическому Щ граммированию, "интеллектуальным" системам извлечения информации, эксперты системам и планированию действий. Показано, что большинство современных сист! искусственного интеллекта (ИИ) может быть описано в виде глобальной базы даннц к которой применяются правила продукций под контролем некоторой управляю^ системы. Выделение базы данных, правил продукций и блока управления в систе( ИИ дает возможность изучения разнообразных механизмов использования в вычис| тельном процессе дополнительной информации о предметной области, обеспечиваю^ в конечном счете эффективное решение задач реальной сложности. Приводятся мно! численные примеры и программы, поясняющие и детализирующие общий подход к м« симальному использованию знаний при решении задач. j
Автор книги — известный американский ученый, руководитель работ по искус| венному интеллекту в Станфордском исследовательском институте, разработчик сис^ мы STRIPS, предназначенной для управления автономным робожом. J
Для научных работников, специализирующихся в области искусственного HHT«J лекта.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
В предисловии к русскому изданию в 1973 г. книги "Искусственный интеллект. Методы поиска решений" (по-английски она называлась "Problem-Solving Methods in Artificial Intelligence") Н. Нильсон отмечал, что вопросы эвристического поиска перестали быть в центре внимания в исследованиях по искусственному интеллекту (ИИ). Для этого имелись две причины: с одной стороны, эта область уже достаточно разработана, так что не следует ожидать существенного повышения эффективности поиска, а с другой — одних эффективных методов поиска (перебора), как показал опыт, недостаточно для решения по-настоящему сложных задач. Он говорил, что хорошо бы написать книгу под названием "Как вкладывать знания в программы для ЭВМ" или "Как ЭВМ могут усваивать знания".
Тем не менее эта небольшая книга Н. Нильсона, посвященная в основном эвристическому поиску и доказательству теорем методом резолюции, сыграла свою важную роль, став настольной книгой по теории искусственного интеллекта — направлению, которое Н. Нильсон относит к числу инженерных дисциплин, "поскольку его первоначальной целью является создание конструкций".
Сегодня советскому читателю предлагается перевод новой книги Н. Нильсона, которая просто называется "Принципы искусственного интеллекта". Она вышла сначала в США в 1980 г., а затем была переиздана в Западной Европе и сейчас является одним из наиболее популярных пособий (в ряде учебных заведений — обязательным) для студентов и аспирантов, специализирующихся в области искусственного интеллекта.
Отвечает ли эта книга на вопрос о том, как вкладывать знания в программы для ЭВМ?
Дело в том, что последние десять лет вопрос представления знаний в ЭВМ был практически основным, над которым работали во всех ведущих научных центрах. В широком смысле это вопрос о том, как усваивать, хранить, обновлять и обрабатывать большие объемы данных, имеющих развитую внутреннюю структуру. В ходе этих работ был получен целый ряд важных результатов "инженерного свойства" — создание экспертных систем и бога-™х баз знаний в разнообразных проблемных областях, разработка эффек-ных методов программирования задач искусственного интеллекта и соответствующих языковых средств, разработка новых структурных схем Ранения и использования знаний (фреймов и т. п.), создание систем планирования порядка выполнения действий в сложной ситуации (например,
я робота), гетерархических систем анализа сцен, восприятия речевых, мешенных и других сообщений и т .д.
^ а это время значительно изменился и характер вычислительных машин. °и ст°роны, они стали более производительными и располагают боль-
5
ОГЛАВЛЕНИЕ
Стр.
Предисловие редактора перевода................................ 5
Предисловие............................................ . 9
Выражение благодарности..................................... 11
Пролог................................................. 12
0.1. Некоторые приложения искусственного интеллекта.................. 13
0.2. Содержание книги....................................... 19
0.3. Библиографические и исторические замечания..................... 20
Глава 1. Системы продукций и искусственный интеллект............... 25
1.1. Системы продукций.....................................,. 25
1.2. Специализированные системы продукций........................ 38
1.3. Комментарии к различным типам систем продукций................. 48
1.4. Библиографические и исторические замечания..................... 49
Упражнения. . ......................................... 51
Глава 2. Стратегии поиска для систем продукций в искусственном интеллекте. . 51
2.1. Стратегии с возвращением................................: . 53
2.2. Стратегии поиска на графе.................................. 58
2.3. Неинформированные процедуры поиска на графе................... 64
2.4. Эвристические процедуры поиска на графе........................ 65
2.5. Другие алгоритмы......................,. . ............... 80
2.6. Различные меры качества работы.............................. 82
2.7. Библиографические и исторические замечания..................... 84
Упражнения.................................•.......... 86
S
Глава 3. Стратегии поиска для разложимых систем продукций............ 86
3.1. Поиск на графах типа И/ИЛИ................................ 86
3.2. АО* - эвристическая процедура поиска на графах типа И/ИЛИ........... 89
3.3. Некоторые соотношения между разложимыми и коммутативными системами . 94
3.4. Поиск на игровых деревьях................................. 97
3.5. Библиографические и исторические замечания.....................108
Упражнения. . . . .'......................................109
Глава 4. Исчисление предикатов в области искусственного интеллекта.......110
4.1. Неформальное введение в исчисление предикатов...................110
4.2. Резолюция............................................ 121
4.3. Использование исчисления предикатов в искусственном интеллекте........126
4.4. Библиографические и исторические замечания.....................129
. Упражнения...........................................130
Глава 5. Системы опровержения на основе резолюции.................131
5.1. Системы продукций для опровержения на основе резолюции............132
5.2. Стратегии управления для методов резолюции.....................133
5.3. Стратегии упрощения.....................................141
372
5.4. Извлечение ответа из опровержения, основанного на резолюции.........143
5.5. Библиографические и исторические замечания.....................153
Упражнения..........................................153
Глава 6. Системы дедукции на основе правил.....................155
6.1. Прямая система дедукции..........................-.......157
6.2. Обратные системы дедукции...............................169
6.3. "Резолюция" внутри графов типа И/ИЛИ........................185
6.4. Вычислительные дедукции и синтез программ.....................190
6.5. Комбинация прямой и обратных систем........................200
6.6. Управляющие знания в системах дедукции на основе правил............203
6.7. Библиографические и исторические замечания . ...................211
Упражнения..........................................213
Глава 7. Основные системы построения планов....................215
7.1. Решение задач с роботом..................................215
7.2. Прямая система продукций................................220
7.3. Способ представления планов............................... 222
7.4. Обратная система.продукций................................226
7.5. Система STRIPS .......................................235
7.6. Использование систем дедукции для выработки планов для роботов......243
7.7. Библиографические и исторические замечания....................251
Упражнения...........................................252
Глава 8. Развитые системы построения планов.....................253
8.1. Система RSTRIPS....................................... 253
8.2. СистемаОСОМР....................................... 263
8.3. Совершенствование планов................................270
8.4. Иерархическое планирование...............................276
8.5. Библиографические и исторические замечания....................283
Упражнения..........................................283
Глава 9. Представления для структурированных объектов.............285
9.1. От исчисления предикатов к блокам...........................286
9.2. Представление в форме графов: семантические сети.................292
9.3. Установление соответствия................................299
9.4. Дедуктивные операции над структурированными объектами...........306
9.5. Неточные описания и противоречивая информация..................324
9.6. Библиографические и исторические замечания....................327
Упражнения..........................................328
Глава 10. Проспект......................................329
10.1. Архитектура систем искусственного интеллекта..................329
10.2. Усвоение знаний......................................331
10.3. Формальные системы для представления знаний...................333
Список литературы........................................338
Список литературы, переведенной на русский язык.................'• • • 371
Дополнительный список литературы.............................371
Цена: 300руб.
