Планирование по ряду
причин является сложной проблемой,
не малую роль в этом играет
размер пространства возможных
последовательностей шагов. Даже
очень простой робот способен
породить огромное число различных
комбинаций элементарных движений.
Представьте себе, к примеру, робота,
который может передвигаться
вперед, назад, влево и вправо,
и вообразите, сколькими различными
путями он может двигаться
по комнате. Представьте также,
что в комнате есть препятствия,
и что робот должен выбирать
путь вокруг них некоторым
оптимальным образом. Для написания
программы, которая могла бы
разумно определить лучший путь
из всех вариантов, и не была
бы при этом перегружена огромным
их числом, потребуются сложные
методы для представления пространственного
знания и управления перебором
в пространстве альтернатив.
Одним из методов,
применяемых человеческими существами
при планировании, является иерархическая
декомпозиция задачи (hierarchical problem decomposition).
Планируя путешествие в Лондон, вы, скорее
всего, займетесь отдельно проблемами
организации перелета, поездки до аэропорта,
самого полета и поиска подходящего вида
транспорта в Лондоне, хотя все они являются
частью большого общего плана. Каждая
из этих задач может сама быть разбита
на такие подзадачи, как, например, покупка
карты города, преодоление лабиринта линий
метро и поиск подходящей пивной. Такой
подход не только эффективно ограничивает
размер пространства поиска, но и позволяет
сохранять часто используемые маршруты
для дальнейшего применения.
В то время как
люди разрабатывают планы безо
всяких усилий, создание компьютерной
программы, которая бы занималась
тем же - сложная проблема. Казалось
бы, такая простая вещь, как разбиение
задачи на независимые подзадачи,
на самом деле требует изощренных
эвристик и обширного знания
об области планирования. Не менее
сложная проблема - определить, какие
планы следует сохранить, и
как их обобщить для использования
в будущем.
Робот, слепо выполняющий
последовательности действий, не
реагируя на изменения в своем
окружении, или неспособный обнаруживать
и исправлять ошибки в своем
собственном плане, едва ли
может считаться разумным. Зачастую
от робота требуют сформировать
план, основанный на недостаточной
информации, и откорректировать
свое поведение по мере его
выполнения. Робот может не располагать
адекватными сенсорами для того, чтобы
обнаружить все препятствия на проектируемом
пути. Такой робот должен начать двигаться
по комнате, основываясь на "воспринимаемых"
им данных, и корректировать свой путь
по мере того, как выявляются другие препятствия.
Организация планов, позволяющая реагировать
на изменение условий окружающей среды,
- основная проблема планирования [Lewis
и Luger, 2000].
Наконец, робототехника
была одной из областей исследований
ИИ, породившей множество концепций,
лежащих в основе агентно-ориентированного
принятия решений (см. подраздел 1.1.4). Исследователи,
потерпевшие неудачу при решении проблем,
связанных с большими пространствами
представлений и разработкой алгоритмов
поиска для традиционного планирования,
переформулировали задачу в терминах
взаимодействия полуавтономных агентов
[Agre и Chapman, 1987], [Brooks, 1991a]. Каждый агент отвечает
за свою часть задания, и общее решение
возникает в результате их скоординированных
действий. Элементы алгоритмов планирования
будут представлены в главах 6, 7 и 14.
Исследования в области
планирования сегодня вышли за
пределы робототехники, теперь
они включают также координацию
любых сложных систем задач
и целей. Современные планировщики
применяются в агентских средах
[Nilsson, 1994], а также для управления ускорителями
частиц [Klein и др., 1999, 2000].
1.2.7. Языки и
среды ИИ
Одним из наиболее
важных побочных продуктов исследований
ИИ стали достижения в сфере
языков программирования и средах
разработки программного обеспечения.
По множеству причин, включая
размеры многих прикладных программ
ИИ, важность методологии "создания
прототипов", тенденцию алгоритмов
поиска порождать чересчур большие
пространства и трудности в
предсказании поведения эвристических
программ, программистам искусственного
интеллекта пришлось разработать
мощную систему методологий программирования.
Средства программирования
включают такие методы структурирования
знаний, как объектно-ориентированное
программирование и каркасы экспертных
систем (они обсуждаются в части
III). Высокоуровневые языки, такие
как LISP и PROLOG (см. часть IV), которые
обеспечивают модульную разработку,
помогают управиться с размерами
и сложностью программ. Пакеты
средств трассировки позволяют программистам
реконструировать выполнение сложного
алгоритма и разобраться в сложных структурах
эвристического перебора. Без подобных
инструментов и методик вряд ли удалось
бы построить многие известные системы
ИИ.
Многие из этих методик
сегодня являются стандартными
методами разработки программного
обеспечения и мало соотносятся
с основами теории ИИ. Другие же,
такие как объектно-ориентированное программирование,
имеют значительный теоретический и практический
интерес. Наконец, многие алгоритмы ИИ
сейчас реализуются на таких традиционных
для вычислительной техники языках, как
C++ и Java.
Языки, разработанные
для программирования ИИ, тесно
связаны с теоретической структурой
этой области. В данной книге
рассматривается и LISP, и PROLOG, и
мы старались удержаться от
религиозных прений об их относительных
достоинствах, склоняясь, скорее, к
той точке зрения, что "хороший
работник должен знать все
инструменты". Главы, посвященные
языкам программирования (14 и 15),
рассматривают преимущества применения
различных языков для решения
конкретных задач.
1.2.8. Машинное
обучение
Обучение остается "крепким
орешком" искусственного интеллекта.
Важность обучения, тем не менее,
несомненна, поскольку эта способность
является одной из главных
составляющих разумного поведения.
Экспертная система может выполнять
долгие и трудоемкие вычисления
для решения проблем. Но, в отличие
от человеческих существ, если
дать ей такую же или подобную
проблему второй раз, она не
"вспомнит" решение. Она каждый
раз вновь будет выполнять
те же вычисления - едва ли это
похоже на разумное поведение.
Большинство экспертных
систем ограничены негибкостью
их стратегий принятия решений
и трудностью модификации больших
объемов кода. Очевидное решение
этих проблем - заставить программы
учиться самим на опыте, аналогиях
или примерах.
Хотя обучение является
трудной областью, существуют некоторые
программы, которые опровергают
опасения о ее неприступности.
Одной из таких программ является
AM - Автоматизированный Математик,
разработанный для открытия математических
законов [Lenat, 1977, 1982]. Отталкиваясь от
заложенных в него понятий и аксиом теории
множеств, Математику удалось вывести
из них такие важные математические концепции,
как мощность множества, целочисленная
арифметика и многие результаты теории
чисел. AM строил теоремы, модифицируя свою
базу знаний, и использовал эвристические
методы для поиска наилучших из множества
возможных альтернативных теорем. Из недавних
результатов можно отметить программу
Коттона [Cotton и др., 2000], которая изобретает
"интересные" целочисленные последовательности.
К ранним трудам, оказавшим
существенное влияние на эту
область, относятся исследования
Уинстона по выводу таких структурных
понятий, как построение "арок"
из наборов "мира блоков"
[Winston, 1975a]. Алгоритм ID3 проявил способности
в выделении общих принципов из разных
примеров [Quinlan, 1986a]. Система MetaDENDRAL выводит
правила интерпретации спектрографических
данных в органической химии на примерах
информации о веществах с известной структурой.
Система Teiresias - интеллектуальный "интерфейс"
для экспертных систем - преобразует сообщения
на высокоуровневом языке в новые правила
своей базы знаний [Davis, 1982]. Программа Hacker
строит планы для манипуляций в "мире
блоков" посредством итеративного процесса
работки плана, его испытания и коррекции
выявленных недостатков [Sussman, 1975]. Работа
в сфере обучения, основанного на "пояснениях",
продемонстрировала эффективность для
обучения априорному знанию [Mitchell и др.,
1986], [DeJong и Mooney, 1986]. Сегодня известно также
много важных биологических и социологических
моделей обучения. Они будут рассмотрены
в главах, посвященных коннекционистскому
и эмерджентному обучению.
Успешность программ
машинного обучения наводит на
мысль о существовании универсальных
принципов, открытие которых позволило
бы конструировать программы,
способные обучаться в реальных
проблемных областях. Некоторые
подходы к обучению будут представлены
в главах 9-11.
1.2.9. Альтернативные
представления: нейронные сети
и генетические алгоритмы
В большей части
методик, представленных в этой
книге, для реализации интеллекта
используются явные представления
знаний и тщательно спроектированные
алгоритмы перебора. Совершенно отличный
подход состоит в построении интеллектуальных
программ с использованием моделей, имитирующих
структуры нейронов в человеческом мозге
или эволюцию разных альтернативных конфигураций,
как это делается в генетических алгоритмах
и искусственной жизни.
Схематическое представление
нейрона (рис. 1.2) состоит из клетки,
которая имеет множество разветвленных
отростков, называемых дендритами,
и одну ветвь - аксон. Дендриты
принимают сигналы от других
нейронов. Когда сумма этих импульсов
превышает некоторую границу,
нейрон сам возбуждается, и импульс,
или "сигнал", проходит по аксону.
Разветвления на конце аксона образуют
синапсы с дендритами других нейронов.
Синапс - это точка контакта между нейронами.
Синапсы могут быть возбуждающими (excitatory)
или тормозящими (inhibitory), в зависимости
от того, увеличивают ли они результирующий
сигнал.
Такое описание нейрона
необычайно просто, но оно передает
основные черты, существенные
в нейронных вычислительных моделях.
В частности, каждый вычислительный
элемент подсчитывает значение
некоторой функции своих входов
и передает результат к присоединенным
к нему элементам сети. Конечные
результаты являются следствием
параллельной и распределенной
обработки в сети, образованной
нейронными соединениями и пороговыми
значениями.
Нейронные архитектуры
привлекательны как средства
реализации интеллекта по многим
причинам. Традиционные программы
ИИ могут быть слишком неустойчивы
и чувствительны к шуму. Человеческий
интеллект куда более гибок
при обработке такой зашумленной
информации, как лицо в затемненной
комнате или разговор на шумной
вечеринке. Нейронные архитектуры,
похоже, более пригодны для сопоставления
зашумленных и недостаточных
данных, поскольку они хранят
знания в виде большого числа
мелких элементов, распределенных
по сети.
С помощью генетических
алгоритмов и методик искусственной
жизни мы вырабатываем новые
решения проблем из компонентов
предыдущих решений. Генетические
операторы, такие как скрещивание
или мутация, подобно своим
эквивалентам в реальном мире,
вырабатывают с каждым поколением
все лучшие решения. В искусственной
жизни новые поколения создаются
на основе функции "качества"
соседних элементов в прежних
поколениях.
И нейронные архитектуры,
и генетические алгоритмы дают
естественные модели параллельной
обработки данных, поскольку каждый
нейрон или сегмент решения
представляет собой независимый
элемент. Гиллис [Hillis, 1985] отметил, что
люди быстрее справляются с задачами,
когда получают больше информации, в то
время как компьютеры, наоборот, замедляют
работу. Это замедление происходит за
счет увеличения времени последовательного
поиска в базе знаний. Архитектура с массовым
параллелизмом, например человеческий
мозг, не страдает таким недостатком. Наконец,
есть нечто очень привлекательное в подходе
к проблемам интеллекта с позиций нервной
системы или генетики. В конце концов,
мозг есть результат эволюции, он проявляет
разумное поведение и делает это посредством
нейронной архитектуры. Нейронные сети,
генетические алгоритмы и искусственная
жизнь рассматриваются в главах 10 и 11.
1.2.10. Искусственный
интеллект и философия
В разделе 1.1 мы представили
философские, математические и
социологические истоки искусственного
интеллекта. Важно осознавать, что
современный ИИ не только наследует
эту богатую интеллектуальную
традицию, но и делает свой
вклад в нее.
Например, поставленный
Тьюрингом вопрос о разумности
программ отражает наше понимание
самой концепции разумности. Что
такое разумность, как ее описать?
Какова природа знания? Можно
ли его представить в устройствах?
Что такое навыки? Может ли
знание в прикладной области
соотносится с навыком принятия
решений в этой среде? Как
знание о том, что есть истина
(аристотелевская "теория"), соотносится
со знанием, как это сделать
("практика")?
Ответы на эти вопросы
составляют важную часть работы
исследователей и разработчиков
ИИ. В научном смысле программы
ИИ можно рассматривать как
эксперименты. Проект имеет конкретную
реализацию в виде программы,
и программа выполняется как
эксперимент. Разработчики программы
изучают результаты, а затем перестраивают
программы и вновь ставят эксперимент.
Таким образом возможно определить, являются
ли наши представления и алгоритмы достаточно
хорошими моделями разумного поведения.
Ньюэлл и Саймон [Newell и Simon, 1976] предложили
этот подход к научному познанию в своей
тьюринговской лекции 1976 г.
Ньюэлл и Саймон также предложили
более сильную модель интеллекта в своей
гипотезе о физической символьной системе:
физическая система проявляет разумное
поведение тогда и только тогда, когда
она является физической символьной системой.
В главе 16 подробно рассматривается практический
смысл этой теории, а также критические
замечания в ее адрес.