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

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

Типы агентов по целям

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

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

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

В этом посте (и далее) в качестве примера для объяснения различных алгоритмов мы рассматриваем проблему перемещения из одного места в другое (путь с одним источником и одним пунктом назначения). На Рисунке 1 представлена ​​дорожная карта части Румынии.

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

Постановка и постановка проблемы

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

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

Формально проблему можно определить с помощью 5 компонентов:

  1. Начальное состояние агента. В этом случае начальное состояние можно описать как In: Arad
  2. Возможные действия, доступные агенту, соответствующие каждому состоянию, в котором находится агент. Например, ACTIONS (In: Arad) = {Go: Sibiu , Вперед: Тимишоара, Вперед: Зеринд}
  3. Модель перехода, описывающая, что делает каждое действие. Представим его как РЕЗУЛЬТАТ (s, a), где s - это состояние, в котором в данный момент находится действие, а a - действие, выполняемое агентом. В этом примере РЕЗУЛЬТАТ (In: Arad, Go: Zerind) = In: Zerind.
  4. Тест цели, определяющий, является ли текущее состояние целевым. Здесь состояние цели - {In: Bucharest}.
  5. Функция стоимость пути, которая определяет стоимость каждого пути, которая отражается в показателе производительности. Для агента, пытающегося добраться до Бухареста, важно время, поэтому мы можем установить функцию стоимости как расстояние между местами. (Здесь мы игнорируем другие факторы, влияющие на время в пути). По соглашению мы определяем функцию стоимости как c (s, a, s ’), где s - текущее состояние, а a - действие, выполняемое агентом для достижения состояния s’.

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

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

Поиск решений

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

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

Мы должны заметить одну особенность в дереве поиска на рисунке 2. Есть путь из Арада в Сибиу и снова обратно в Арад. Мы говорим, что In (Arad) - это повторяющееся состояние, генерируемое циклическим путем. Это означает, что дерево поиска для Румынии бесконечное, хотя пространство поиска ограничено. Эти зацикленные пути приводят к сбою некоторых алгоритмов, из-за чего проблема кажется неразрешимой. Фактически, замкнутый путь - это частный случай избыточных путей, где существует более одного пути из одного состояния в другое (например, Арад - Сибиу и Арад - Зеринд - Орадя - Сибиу).

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

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

Показатель эффективности алгоритмов решения проблем

Мы можем оценить производительность алгоритма с помощью следующих показателей:

  1. Полнота: гарантированно ли алгоритм найдет решение, если оно существует?
  2. Оптимальность: находит ли алгоритм оптимальное решение?
  3. Сложность по времени. Сколько времени требуется алгоритму, чтобы найти решение?
  4. Сложность места. Сколько памяти уходит на поиск решения?

В теории графов временная и пространственная сложность измеряется с помощью | V | и | E |, где V и E - количество вершин и количество ребер в графе соответственно. Но в AI мы исследуем пространство состояний (которое является графом) проблемы, используя эквивалентное ему дерево поиска. Поэтому имеет смысл использовать b и d для измерения сложности, где b - фактор ветвления дерево (максимальное количество преемников любого узла), а d - глубина самого мелкого целевого узла.

Резюме

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

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