Термин интеллект (intelligence) происходит от латинского intellectus что означает ум, рассудок, разум; мыслительные способности человека

Вид материала

Документы

Содержание Рациональный агент. Проблемные среды. Cоздание автоматизированного водителя такси. Тип агента Простые рефлексивные агенты. Стратегии неинформированного поиска. Поиск в ширину Поиск в глубину с ограничением глубины Двунапрвленный поиск Поиск по критерию стоимости Понятие эвристики. Жадный поиск Поиск в оперативном режиме Поиск с удовлетворением ограничений Поиск в условиях противодействия игр Характеристика языка Пролог. Краткий обзор языка.

Подобный материал:

• 1. Основы теории коррозии Термин коррозия происходит от латинского "corrosio", что, 205.52kb.
• Слово "мебель" происходит от латинского "мобилис", что означает "подвижный", 457.09kb.
• Лекция Понятие об интеллекте и интеллектуальных нарушениях. Интеллект, 1197.01kb.
• Теоретический курс: Что означает термин «логика» Каковы объект и предмет логики, 632.78kb.
• Понятие информации, виды информации. Ее свойства, 220.05kb.
• Культура античности древнегреческая цивилизация, 120.53kb.
• М. Ю. Лермонтова 7-10 стр, 331.07kb.
• Проституция одна из форм социально отклоняющегося полового поведения, проявляющегося, 325.9kb.
• Концепция, 230.42kb.
• Роль спекуляции (легальной и нелегальной) в рыночном хозяйстве. Хеджеры и спекулянты, 244.01kb.

Рациональный агент.

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

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

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

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


Типы рациональных агентов.

1. Простые рефлексивные агенты – очень просты, очень надёжны, но ограниченный интеллект.
   
2. Агенты основанные на модели – предыдущие акты восприятия.
   
3. Агенты основанные на цели.
   
4. Агенты основанные на полезности.
   
5. Обучающиеся агенты.
   

Показатели производительности рациональных агентов.

Показатели производительности

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

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

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

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

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

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

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

Проблемные среды.

Определение проблемной среды

PEAS (Performance, Environment, Actuators, Sensors— производительность, среда, исполнительные механизмы, датчики).

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

Cоздание автоматизированного водителя такси.

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

Тип агента - Водитель такси

Показатели производительности - Безопасная, быстрая, комфортная езда в рамках ПДД, максимизация прибыли

Среда - Дороги, другие транспортные средства, пешеходы, клиенты

Исполнительные механизмы - Рулевое управление, акселератор, тормоз, световые сигналы, клаксон, дисплей

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

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

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

Таксисту может выпасть участь работать в Южной Калифорнии, где редко возникает такая проблема, как снег, или на Аляске, где снега на дорогах не бывает очень редко. Может оказаться, что водителю всю жизнь придется ездить по правой стороне или от него может потребоваться, чтобы он сумел достаточно успешно приспособиться к езде по левой стороне во время пребывания в Британии или в Японии. Безусловно, чем более ограниченной является среда, тем проще задача проектирования.

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

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

Автоматизированный водитель может также иметь приборы, недоступные для среднего водителя-человека: спутниковую глобальную систему навигации и определения положения (Global Positioning System— GPS) для получения точной информации о местонахождении по отношению к электронной карте, а также инфракрасные или ультразвуковые датчики для измерения расстояний до других автомобилей и препятствий. Наконец, ему потребуется клавиатура или микрофон для пассажиров, чтобы они могли указать место своего назначения.


Простые рефлексивные агенты.

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

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

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

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

Поэтому рандомизированный простой рефлексный агент может превзойти по своей производительности детерминированного простого рефлексного агента.


Стратегии неинформированного поиска.

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

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

b + b2 + b3 + . bd + (bd+1 - b) = O(bd+1) b – узлов, на глубине d

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

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


Поиск в глубину с ограничением глубины - проблему неограниченных деревьев можно решить, предусматривая применение во время поиска в глубину заранее определенного предела глубины L. Это означает, что узлы на глубине L рассматриваются таким образом, как если бы они не имели преемников. Такой подход называется поиском с ограничением глубины.
Применение предела глубины позволяет решить проблему бесконечного пути. К сожалению, в этом подходе также вводится дополнительный источник неполноты, если будет выбрано значение L Двунапрвленный поиск - В основе двунаправленного поиска лежит такая идея, что можно одновременно проводить два поиска (в прямом направлении, от начального состояния, и в обратном направлении, от цели), останавливаясь после того, как два процесса поиска встретятся на середине.
Дело в том, что значение b^d/2 гораздо меньше, чем b^d, или, как показано на этом рисунке, площадь двух небольших кругов меньше площади одного большого круга с центром в начале поиска, который охватывает цель поиска.


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

Поиск по критерию стоимости направляется с учетом стоимостей путей, а не значений глубины в дереве поиска, поэтому его сложность не может быть легко охарактеризована в терминах b и d. Вместо этого предположим, что C — стоимость оптимального решения, и допустим, что стоимость каждого действия составляет, по меньшей мере, ε.
Это означает, что временная и пространственная сложность этого алгоритма в наихудшем случае составляет O(b^1+[c/8]), т.е. может быть намного больше, чем b⁴. Это связано с тем, что процедуры поиска по критерию стоимости могут и часто выполняют проверку больших деревьев, состоящих из мелких этапов, прежде чем перейти к исследованию путей, в которые входят крупные, но, возможно, более полезные этапы. Безусловно, если все стоимости этапов равны, то выражение b^1+[c/8] равняется bd.

Понятие эвристики.

Эвристика - Функция узла f(n) характеризующее расстояние до цели. Эвристические методы применяют для моделирования математических и игровых задач и для совершенствования работы компьютеров. Главное в эвристической про грамме - стратегия поиска решений.

Жадный поиск - При жадном поиске по первому наилучшему совпадению предпринимаются попытки развертывания узла, который рассматривается как ближайший к цели на том основании, что он со всей вероятностью должен быстро привести к решению. Таким образом, при этом поиске оценка узлов производится с использованием только эвристической функции: f(n) = h(n).

Поиск A* - Наиболее широко известная разновидность поиска по первому наилучшему совпадению называется поиском А* (читается как «А звездочка»). В нем применяется оценка узлов, объединяющая в себе g(n), стоимость достижения данного узла, и h(n), стоимость прохождения от данного узла до цели: f(n)=g(n)+h(n). Поскольку функция g(n) позволяет определить стоимость пути от начального узла до узла n, а функция h(n) определяет оценку стоимости наименее дорогостоящего пути от узла п до цели, то справедлива следующая формула: f(n) = оценка стоимости наименее дорогостоящего пути решения, проходящего через узел n Таким образом, при осуществлении попытки найти наименее дорогостоящее решение, по-видимому, разумнее всего вначале попытаться проверить узел с наименьшим значением g(n) + h(n). Как оказалось, данная стратегия является больше чем просто разумной: если эвристическая функция h(n) удовлетворяет некоторым условиям, то поиск А* становится и полным, и оптимальным.

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

Поиск с удовлетворением ограничений - Формально говоря, любая задача удовлетворения ограничений (Constraint Satisfaction Problem— CSP) определена множеством переменных, X₁, X₂,…, X_n, и множеством ограничений, C₁, C₂,…, C_m. Каждая переменная X_i имеет непустую область определения D_i возможных значений. Каждое ограничение C_i включает некоторое подмножество переменных и задает допустимые комбинации значений для этого подмножества. Состояние задачи определяется путем присваивания значений некоторым или всем этим переменным, {X_i = v_i, X_j = v_j,...}. Присваивание, которое не нарушает никаких ограничений, называется совместимым, или допустимым присваиванием. Полным называется такое присваивание, в котором участвует аждая переменная, а решением задачи CSP является полное присваивание, которое довлетворяет всем ограничениям. Кроме того, для некоторых задач CSP требуется найти решение, которое максимизирует целевую функцию.

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

Например: “Альфа-бета-отсечение” – Лучшее враг хорошего. Общий случай: Если для Игрока узел m лучше чем п, то узел п никогда не встретится в игре.


Характеристика языка Пролог.

Пролог (англ. Prolog) — язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.

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

История

Разработка языка Prolog началась в 1970 г. Аланом Кулмероэ и Филиппом Русселом. Они хотели создать язык, который мог бы делать логические заключения на основе заданного текста. Название Prolog является сокращением от "PROgramming in LOGic". Этот язык был разработан в Марселе в 1972 г. Принцип резолюции Ковальского, сотрудника Эдинбургского университета, казался подходящей моделью, на основе которой можно было разработать механизм логических выводов. С ограничением резолюции на дизъюнкты Хорна унификация привела к эффективной системе, где неустранимый недетерминизм обрабатывался с помощью процесса отката, который мог быть легко реализован. Алгоритм резолюции позволял создать выполняемую последовательность, необходимую для реализации спецификаций, подобных приведенному выше отношению flight.

Первая реализация языка Prolog с использованием компилятора Вирта ALGOL-W была закончена в 1972 г., а основы современного языка были заложены в 1973 г. Использование языка Prolog постепенно распространялось среди тех, кто занимался логическим программированием, в основном благодаря личным контактам, а не через коммерциализацию продукта. В настоящее время существует несколько различных, но довольно похожих между собой версий. Хотя стандарта языка Prolog не существует, однако версия, разработанная в Эдинбургском университете, стала наиболее широко используемым вариантом. Недостаток разработок эффективных приложений Prolog сдерживал его распространение вплоть до 1980 г.

Краткий обзор языка.

Программа на языке Prolog состоит из набора фактов, определенных отношений между объектами данных (фактами) и набором правил (образцами отношений между объектами базы данных). Эти факты и правила вводятся в базу данных через операцию consult. Для работы программы пользователь должен ввести запрос - набор термов, которые все должны быть истинны. Факты и правила из базы данных используются для определения того, какие подстановки для переменных в запросе (называемые унификацией) согласуются с информацией в базе данных.

Язык Prolog, как интерпретатор, приглашает пользователя вводить информацию. Пользователь набирает запрос или имя функции. Выводится значение (истина - yes, или ложь - по) этого запроса, а также возможные значения переменных запроса, присвоение которых делает запрос истинным (то есть унифицирует запрос). Если ввести символ ";", тогда отображается следующий набор значений переменных, унифицирующий запрос, и так до тех пор, пока не исчерпается весь набор возможных подстановок, после чего Prolog печатает no и ждет следующего запроса. Возврат каретки воспринимается как прекращение поиска дополнительных решений.

Хотя выполнение программы на языке Prolog основывается на спецификации предикатов, оно напоминает выполнение программ на аппликативных языках LISP или ML Разработка правил языка Prolog требует того же рекурсивного мышления, что и разработка программ на этих аппликативных языках.

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