Популярно об ИИ
Продолжаем серию материалов по искусственному интеллекту (ИИ). Честно сказать, ваш покорный слуга — практик. Поэтому с моей точки зрения позиция некоторых оппонентов в плане выделения ИИ как чего-то фундаментального с глубинным философским смыслом ошибочно и надуманно. Это прикладная дисциплина с устоявшимися правилами и понятиями, которые используются повсеместно. Интеллектуальные системы и комплексы разрабатываются для решения конкретных задач — в частности, обеспечения сложных технологических и вычислительных процессов. Насчет "молодости" этой науки… ИИ, кибернетика, теория информации — практически ровесники, а многие направления, обсуждаемые нами на страницах ИТ-изданий, гораздо моложе. Но все это уже реально используется на практике и является более-менее устоявшимся.
Для чего же было нужно внедрение понятия агентов?
В прошлом материале мы рассмотрели основные теоретические выкладки по агентам — структурным модулям, которые находятся в определенной среде и преобразуют результаты собственного восприятия в собственное же действие. Как было указано, само понятие агентов достаточно абстрактно, причем в различных источниках их определения и классификация представлены неоднозначно. Но на самом деле существенной проблемы в такой разнородности мнений нет. Для описания работы того же агента можно воспользоваться представлением в виде стандартной формулы:
у=f(x1,…, xn);
где y — это требуемый результат/действие (или результаты/действия), который выдается в среду или производится там либо сообщается другим агентам;
f — абстрактное математическое описание функции агента, которая конкретно реализуется программой;
x1,…, xn — поступающие для обработки данные.
На самом деле ничего сложного в этом нет. Единственное, что важно понимать — под агентами могут подразумеваться структурные модули для различных иерархических уровней от микро до макро. Например, некую большую многозадачную программу для пользовательского уровня (того же рабочего стола Windows) можно описать данной формулой, ведь она (эта программа) существует в рамках определенной среды, получает из нее необходимые данные, обрабатывает их и производит требуемое действие либо выводит нужный результат. Вместе с тем, понижая иерархический уровень, можно сказать, что по отношению к ней ее структурные блоки также являются агентами. В свою очередь, и их самих можно раздробить на отдельные функции, и практически… это тоже будут агенты. На самом деле само понятие достаточно удобно в обращении. Это, кстати, очень близко по концепции к объектноориентированным моделям, используемым в современном программировании. Хотя нередко в ИИ вы можете встретить схожий термин — агентноориентированные системы. В некоторых научных работах вы можете найти описание того, что ИИ является результатом взаимодействия множества агентов (их сообщества), как автономных, так и полуавтономных. И если мы говорим об искусственном интеллекте как об имитации разумного поведения и его иерархическом уровне, то он подразумевает под собой целое сообщество агентов различных типов, а именно модулей, собирающих, фильтрующих, обрабатывающих поступающую информацию, вырабатывающих решения, координирующих совместные действия всех агентов и т.д. То есть в дальнейшем под агентами мы будем чаще всего подразумевать именно этот уровень, то есть структурных элементов ИИ. Но при этом… и сам искусственный интеллект подразумевает схожую абстракцию. То есть, с одной стороны, мы можем говорить как о выполнении конкретных операций — например, имитации разумного поведения на уровне отдельного "индивида" (робот-водитель, робот-пылесос и т.п.), так и об управлении группой таких индивидов (система роботов- охранников, роботов-исследователей) и т.д. В тех же компьютерных играх ИИ может реализовываться как на уровне отдельных героев-персонажей, так в рамках управления армией, обществом и т.п.
И главное, что следует понимать в данном вопросе: ИИ — это не просто программа, которая в ответ на 2х2 дает решение 4. Это самый примитивный уровень. Под ИИ в большей мере понимаются системы, которые могут вырабатывать решения, чаще всего находясь в рамках некоей неопределенности. А теперь имеет смысл посмотреть на вопрос с несколько другой стороны.
Основные стратегии поиска решений
Давайте рассмотрим простейший и понятный каждому человеку, работающему на компьютере, пример — пасьянс "Паук". На самом деле при первой и последующих раскладках карт из стопок (кроме последней) игрок находится в рамках неопределенности и не может гарантировать правильность своих действий для достижения победы. Но при этом он выбирает наиболее оптимальные варианты решений, первая часть из которых могут оказаться успешными на данный конкретный момент, а вторая дает задел на будущее. Данная игра относится к недетерминированному типу, то есть неопределенному, подразумевает наличие случайностей. При этом те же шахматы, шашки и другие подобные игры в силу того, что они хорошо изучены, часто называют детерминированными. На самом деле все это весьма условно с точки зрения не современной компьютерной программы и чемпионов мира, а обычных людей. Особенно тех, кто начинает учиться играть. По существу, не имея знаний и опыта, они находятся в ситуации полной неопределенности.
Основоположник теории информации Клод Шеннон в 1951 году написал свою первую статью по программированию шахмат. Причем еще тогда он отметил два ключевых момента: лучший ход теоретически существует, но практически найти его невозможно. Напомним, что это был 1951-й год. Причем в рамках своего труда Шеннон не видел за своими выкладками какого-либо практического значения, а подразумевал только чисто теоретический интерес. Э-эх, эти ученые. Генрих Рудольф Герц, передав и получив электромагнитную волну беспроводным способом, тоже не видел за своим опытом чего-то интересного для практики. Это сейчас, слушая радио, смотря телевизор, пользуясь множеством беспроводных устройств, включая мобильные телефоны, человечество с благодарностью оценивает реализации научно-технического прогресса. Так и Клод Шеннон… Чем же интересен его труд по программированию шахмат? Дело в том, что одной из основных задач современного ИИ является выработка решений в рамках ограниченных ресурсов и процессорных мощностей, при этом далеко не всегда сам ИИ базируется на опыте. В шахматах ситуация схожа, ведь просчитать всю партию наперед практически невозможно. На это не хватит аппаратных ресурсов даже у современных моделей компьютеров, а в начале 50-х прошлого столетия таких перспектив не было в принципе, поэтому Шеннон вывел две основные стратегии поиска лучшего решения, а именно:
. Полный перебор всех возможных ходов на определенную глубину (под глубиной подразумевается количество просчитанных наперед полуходов). При этом для анализа используется специальная оценочная функция.
. Выделение только интересных для решения строк с обрезанием неинтересных ветвей.
Последний вариант виделся Шенноном как наиболее оптимальный и соответствующий человеческому мышлению. Хотя на самом деле он имеет место практически во всей живой природе. Например, если перед неким представителем определенного биологического вида стоит цель, то он выбирает только оптимальные маршруты и действия к ее достижению, неперспективные он отметает. При этом в большинстве случаев просчитать все от и до наперед (то есть гарантировать успешность выбранной ветки) не удается, посему движение идет поэтапно с расчетом дальнейших действий на определенную глубину. Согласитесь, что сама ситуация весьма схожа с игрой в пасьянс "Паук":). То есть, когда решались чисто шахматные задачи, на самом деле разрабатывались первые модели искусственного интеллекта как такового. Кстати, когда мы писали о "бумажной машине Тьюринга", то тогда не отметили, а сейчас скажем, что его алгоритмы работали по второму принципу, то есть учитывались только ветви, предусматривающие взятия (это называется статической или материальной оценкой). В принципе, в современных системах ИИ часто используется и третий тип выработки решений, который также имеет прямую связь с биологической природой, особенно подразумевающей более-менее разумные особи. Как отметили биологи, и что даже часто можно наблюдать в научно-популярных телепрограммах о животных, очень многое передается от одного индивида к другому путем копирования поведенческих моделей, подражания.
В рамках основополагающих областей применения искусственного интеллекта рассматриваются экспертные системы, основанные на том же принципе — знания передаются от человека-эксперта (медика, математика, физика, экономиста и т.п.). Они структурируются и приобретают форму кода. Причем написание таких систем возлагаются не на плечи самих экспертов — их задача состоит только в передаче собственного опыта. За придание всему программной формы отвечает специалист по искусственному интеллекту — если переводить эту специальность на русский — инженер знаний (knowledge engineer). Также это направление сейчас активно прорабатывается в области компьютерных игр, поскольку NPC (несобственные герои, или, простыми словами, искусственные персонажи) должны обладать своими ИИ. А как этого можно достичь наиболее оптимальным способом? Правильно! Повторить действия какого-либо игрока, используя его опыт. А по существу большинство современных программ и специализированных программно-аппаратных комплексов можно считать экспертными системами.
Несколько слов об алгоритмах…
Одной из основных задач программистов ИИ является оценка алгоритмов вложенных агентов либо их сообщества, которые по существу должны отвечать трем ключевым требованиям:
1. Качество результатов.
2. Быстродействие.
3. Оптимальность.
Под первым пунктом следует понимать возможность выбора наиболее правильного решения, минимизацию ошибок, которые зачастую возникают не только за счет неправильности применяемых алгоритмов, но в сложных случаях решения крупных задач и из-за аппроксимирования вычислений (простыми словами — упрощения расчетов, то есть замены основных функций более простыми, упрощенными). Второй пункт — быстродействие, если его относить к программной части — обычно просто подсчитывается по количеству выполняемых операций. При этом на данный вопрос нужно смотреть очень внимательно, понимать суть самих вычислений. Мы уже приводили в прошлом материале этой серии пример с таблицей умножения. Ее можно хранить в виде базы данных с заранее введенными результатами, а можно использовать обычную формулу, что гораздо удобнее и проще. Под оптимальностью нужно понимать соответствие сложности алгоритмической модели по отношению к требованиям в рамках поставленной задачи. При этом среди основных сопутствующих целей могут выступать как качество, так и быстродействие, а иногда — и компромисс между ними.
Приведем конкретные примеры. Первый. На протяжении многих лет в студенческих соревнованиях наземных автономных роботов IGVC, о которых мы часто пишем, машины должны проехать по трассе, ограниченной белыми линиями. Выезд за их пределы "награждается" штрафными очками, мало того, после этого робот может и вовсе не вернуться на трассу. Решение простое — видеосъемка, выделение белого, указание программного "табу". При этом в большинстве случаев, раз уж такие правила, командами была применена аппроксимация. То есть входные изображения преобразовывались (упрощались) до бинарного вида, то есть в них присутствовали только черный и белый цвета. Таким образом, оставалось ввести необходимые if… then. Для усложнения задания изначально на трассе находились и бочонки/препятствия с белыми полосками, которые обрабатывались роботами также. Но… обратите внимание на неоднозначность сделанного упрощения. Ведь в режиме съемки могут произойти казусы с тем, что изменится освещение (облачность) либо на определенном участке трассы будет затененная область. То есть в первую очередь страдало качество выработки решений. Хотя в определенный момент проблему стали решать практически все, и главным моментом стало время достижения финиша. Несколько лет назад полоски на препятствиях заменили однородными, но разноцветными. Но это на самом деле не сильно усложнило задачу, поскольку поступающие изображения также можно упрощать до 16- или 256-цветного представления. Более сложные автономные роботы, разрабатываемые в военных целях, предусматривают машины, оснащенные системами лазерных сканеров для определения препятствий и составления представления о ландшафте местности. Если сама машина большая по размерам, то аппроксимация применяется по отношению к другому. Например, мелкий камень не может оказаться критическим препятствием, поэтому он в учет при выработке решений не берется. Пример третий. Трехмерные миры в компьютерных играх. Основное — это то, что видит пользователь, соответственно, для того, чтобы показать 3D-объекты. Вполне достаточно реализовать алгоритм, который отчленяет видимую часть от невидимой, и, соответственно, обрабатываться (например, освещение и т.п.) будет только то, что необходимо.
Все эти три случая показывают примеры оптимальности. На самом деле программисты-разработчики, выбирая тот или иной алгоритм либо алгоритмический комплекс, нередко сами существуют в некоей неопределенности. То есть, по существу, оказываются в положении игрока в пасьянс "Паук". Далеко не редка ситуация, когда разработчик написал программу, вычисляющую что-либо существенное и решающую крупную задачу, соответственно, после шел этап тестирования, нашлись ошибки, которые проявлялись в определенных ситуациях. Что делать? Пересматривать сам алгоритм либо сделать заплатки специально для выявленных ситуаций? Хорошо, если быстро удается решить первое, но далеко не всегда это так просто, к тому же, может привести к ухудшению положения, ведь новый алгоритм может проявиться с другими ошибками. И чаще всего при наличии небольшого процента критических моментов делаются заплатки для ситуаций. Это очень часто бывает при решении крупных задач. Компьютер DeepBlue, выигрывающий у чемпионов мира по шахматам… В его алгоритмической основе практически не используется человеческий опыт, кроме базы данных эндшпилей (завершений партий). Ключевым модулем для принятия решений является очень сложная оценочная функция, которая учитывает около шести тысяч специфических шахматных показателей. В результате выбираются наиболее выгодные ветви, которые высчитываются с большим продлением. Причем в рамках тестирования с Deep Blue играл гроссмейстер, который следил за компьютером и выявлял моменты неправильной оценки последним ситуации. Когда ошибка была найдена, собирался коллектив разработчиков, обсуждал причину, после чего менялись коэффициенты в оценочной функции.
Продолжение следует.
Кристофер, christopher@tut.by
Для чего же было нужно внедрение понятия агентов?
В прошлом материале мы рассмотрели основные теоретические выкладки по агентам — структурным модулям, которые находятся в определенной среде и преобразуют результаты собственного восприятия в собственное же действие. Как было указано, само понятие агентов достаточно абстрактно, причем в различных источниках их определения и классификация представлены неоднозначно. Но на самом деле существенной проблемы в такой разнородности мнений нет. Для описания работы того же агента можно воспользоваться представлением в виде стандартной формулы:
у=f(x1,…, xn);
где y — это требуемый результат/действие (или результаты/действия), который выдается в среду или производится там либо сообщается другим агентам;
f — абстрактное математическое описание функции агента, которая конкретно реализуется программой;
x1,…, xn — поступающие для обработки данные.
И главное, что следует понимать в данном вопросе: ИИ — это не просто программа, которая в ответ на 2х2 дает решение 4. Это самый примитивный уровень. Под ИИ в большей мере понимаются системы, которые могут вырабатывать решения, чаще всего находясь в рамках некоей неопределенности. А теперь имеет смысл посмотреть на вопрос с несколько другой стороны.
Основные стратегии поиска решений
Давайте рассмотрим простейший и понятный каждому человеку, работающему на компьютере, пример — пасьянс "Паук". На самом деле при первой и последующих раскладках карт из стопок (кроме последней) игрок находится в рамках неопределенности и не может гарантировать правильность своих действий для достижения победы. Но при этом он выбирает наиболее оптимальные варианты решений, первая часть из которых могут оказаться успешными на данный конкретный момент, а вторая дает задел на будущее. Данная игра относится к недетерминированному типу, то есть неопределенному, подразумевает наличие случайностей. При этом те же шахматы, шашки и другие подобные игры в силу того, что они хорошо изучены, часто называют детерминированными. На самом деле все это весьма условно с точки зрения не современной компьютерной программы и чемпионов мира, а обычных людей. Особенно тех, кто начинает учиться играть. По существу, не имея знаний и опыта, они находятся в ситуации полной неопределенности.
Основоположник теории информации Клод Шеннон в 1951 году написал свою первую статью по программированию шахмат. Причем еще тогда он отметил два ключевых момента: лучший ход теоретически существует, но практически найти его невозможно. Напомним, что это был 1951-й год. Причем в рамках своего труда Шеннон не видел за своими выкладками какого-либо практического значения, а подразумевал только чисто теоретический интерес. Э-эх, эти ученые. Генрих Рудольф Герц, передав и получив электромагнитную волну беспроводным способом, тоже не видел за своим опытом чего-то интересного для практики. Это сейчас, слушая радио, смотря телевизор, пользуясь множеством беспроводных устройств, включая мобильные телефоны, человечество с благодарностью оценивает реализации научно-технического прогресса. Так и Клод Шеннон… Чем же интересен его труд по программированию шахмат? Дело в том, что одной из основных задач современного ИИ является выработка решений в рамках ограниченных ресурсов и процессорных мощностей, при этом далеко не всегда сам ИИ базируется на опыте. В шахматах ситуация схожа, ведь просчитать всю партию наперед практически невозможно. На это не хватит аппаратных ресурсов даже у современных моделей компьютеров, а в начале 50-х прошлого столетия таких перспектив не было в принципе, поэтому Шеннон вывел две основные стратегии поиска лучшего решения, а именно:
. Полный перебор всех возможных ходов на определенную глубину (под глубиной подразумевается количество просчитанных наперед полуходов). При этом для анализа используется специальная оценочная функция.
. Выделение только интересных для решения строк с обрезанием неинтересных ветвей.
Последний вариант виделся Шенноном как наиболее оптимальный и соответствующий человеческому мышлению. Хотя на самом деле он имеет место практически во всей живой природе. Например, если перед неким представителем определенного биологического вида стоит цель, то он выбирает только оптимальные маршруты и действия к ее достижению, неперспективные он отметает. При этом в большинстве случаев просчитать все от и до наперед (то есть гарантировать успешность выбранной ветки) не удается, посему движение идет поэтапно с расчетом дальнейших действий на определенную глубину. Согласитесь, что сама ситуация весьма схожа с игрой в пасьянс "Паук":). То есть, когда решались чисто шахматные задачи, на самом деле разрабатывались первые модели искусственного интеллекта как такового. Кстати, когда мы писали о "бумажной машине Тьюринга", то тогда не отметили, а сейчас скажем, что его алгоритмы работали по второму принципу, то есть учитывались только ветви, предусматривающие взятия (это называется статической или материальной оценкой). В принципе, в современных системах ИИ часто используется и третий тип выработки решений, который также имеет прямую связь с биологической природой, особенно подразумевающей более-менее разумные особи. Как отметили биологи, и что даже часто можно наблюдать в научно-популярных телепрограммах о животных, очень многое передается от одного индивида к другому путем копирования поведенческих моделей, подражания.
Несколько слов об алгоритмах…
Одной из основных задач программистов ИИ является оценка алгоритмов вложенных агентов либо их сообщества, которые по существу должны отвечать трем ключевым требованиям:
1. Качество результатов.
2. Быстродействие.
3. Оптимальность.
Под первым пунктом следует понимать возможность выбора наиболее правильного решения, минимизацию ошибок, которые зачастую возникают не только за счет неправильности применяемых алгоритмов, но в сложных случаях решения крупных задач и из-за аппроксимирования вычислений (простыми словами — упрощения расчетов, то есть замены основных функций более простыми, упрощенными). Второй пункт — быстродействие, если его относить к программной части — обычно просто подсчитывается по количеству выполняемых операций. При этом на данный вопрос нужно смотреть очень внимательно, понимать суть самих вычислений. Мы уже приводили в прошлом материале этой серии пример с таблицей умножения. Ее можно хранить в виде базы данных с заранее введенными результатами, а можно использовать обычную формулу, что гораздо удобнее и проще. Под оптимальностью нужно понимать соответствие сложности алгоритмической модели по отношению к требованиям в рамках поставленной задачи. При этом среди основных сопутствующих целей могут выступать как качество, так и быстродействие, а иногда — и компромисс между ними.
Приведем конкретные примеры. Первый. На протяжении многих лет в студенческих соревнованиях наземных автономных роботов IGVC, о которых мы часто пишем, машины должны проехать по трассе, ограниченной белыми линиями. Выезд за их пределы "награждается" штрафными очками, мало того, после этого робот может и вовсе не вернуться на трассу. Решение простое — видеосъемка, выделение белого, указание программного "табу". При этом в большинстве случаев, раз уж такие правила, командами была применена аппроксимация. То есть входные изображения преобразовывались (упрощались) до бинарного вида, то есть в них присутствовали только черный и белый цвета. Таким образом, оставалось ввести необходимые if… then. Для усложнения задания изначально на трассе находились и бочонки/препятствия с белыми полосками, которые обрабатывались роботами также. Но… обратите внимание на неоднозначность сделанного упрощения. Ведь в режиме съемки могут произойти казусы с тем, что изменится освещение (облачность) либо на определенном участке трассы будет затененная область. То есть в первую очередь страдало качество выработки решений. Хотя в определенный момент проблему стали решать практически все, и главным моментом стало время достижения финиша. Несколько лет назад полоски на препятствиях заменили однородными, но разноцветными. Но это на самом деле не сильно усложнило задачу, поскольку поступающие изображения также можно упрощать до 16- или 256-цветного представления. Более сложные автономные роботы, разрабатываемые в военных целях, предусматривают машины, оснащенные системами лазерных сканеров для определения препятствий и составления представления о ландшафте местности. Если сама машина большая по размерам, то аппроксимация применяется по отношению к другому. Например, мелкий камень не может оказаться критическим препятствием, поэтому он в учет при выработке решений не берется. Пример третий. Трехмерные миры в компьютерных играх. Основное — это то, что видит пользователь, соответственно, для того, чтобы показать 3D-объекты. Вполне достаточно реализовать алгоритм, который отчленяет видимую часть от невидимой, и, соответственно, обрабатываться (например, освещение и т.п.) будет только то, что необходимо.
Все эти три случая показывают примеры оптимальности. На самом деле программисты-разработчики, выбирая тот или иной алгоритм либо алгоритмический комплекс, нередко сами существуют в некоей неопределенности. То есть, по существу, оказываются в положении игрока в пасьянс "Паук". Далеко не редка ситуация, когда разработчик написал программу, вычисляющую что-либо существенное и решающую крупную задачу, соответственно, после шел этап тестирования, нашлись ошибки, которые проявлялись в определенных ситуациях. Что делать? Пересматривать сам алгоритм либо сделать заплатки специально для выявленных ситуаций? Хорошо, если быстро удается решить первое, но далеко не всегда это так просто, к тому же, может привести к ухудшению положения, ведь новый алгоритм может проявиться с другими ошибками. И чаще всего при наличии небольшого процента критических моментов делаются заплатки для ситуаций. Это очень часто бывает при решении крупных задач. Компьютер DeepBlue, выигрывающий у чемпионов мира по шахматам… В его алгоритмической основе практически не используется человеческий опыт, кроме базы данных эндшпилей (завершений партий). Ключевым модулем для принятия решений является очень сложная оценочная функция, которая учитывает около шести тысяч специфических шахматных показателей. В результате выбираются наиболее выгодные ветви, которые высчитываются с большим продлением. Причем в рамках тестирования с Deep Blue играл гроссмейстер, который следил за компьютером и выявлял моменты неправильной оценки последним ситуации. Когда ошибка была найдена, собирался коллектив разработчиков, обсуждал причину, после чего менялись коэффициенты в оценочной функции.
Продолжение следует.
Кристофер, christopher@tut.by
Компьютерная газета. Статья была опубликована в номере 21 за 2008 год в рубрике технологии
