Интеллектуальные агенты и алгоритмы поиска

1.

НЕДЕЛИ 2–3 · CSE8802
Интеллектуальные агенты и
алгоритмы поиска
Основы искусственного интеллекта · CSE8802 · Недели 2–3
6В06110 Computer Science & AI Engineering
Айдарова Танжулдыз Нуралиевна, старший преподаватель
Кафедра «Программная инженерия» · Satbayev University

2.

План занятия
Неделя 2
Неделя 3
Интеллектуальные агенты
Алгоритмы поиска
▸ Понятие агента и цикл «восприятие – действие»
▸ Задача поиска в пространстве состояний
▸ Модель PEAS
▸ Дерево поиска и стратегии
▸ Свойства среды
▸ BFS и DFS
▸ Пять типов агентов
▸ Эвристический поиск A*
Основы ИИ · Недели 2–3
2 / 25

3.

Что такое интеллектуальный агент?
▸ Агент — всё, что воспринимает свою среду с помощью датчиков (sensors)
и воздействует на неё с помощью исполнительных механизмов
(actuators)
СРЕДА
Sensors
▸ Восприятие (percept) — информация, полученная агентом в конкретный
момент времени
Actuators
▸ История восприятий (percept sequence) — вся последовательность
восприятий агента за время его работы
▸ Поведение агента математически описывается функцией агента: история
восприятий → действие
АГЕНТ
Основы ИИ · Недели 2–3
3 / 25

4.

Функция агента и программа агента
Функция агента
Программа агента
▸
Абстрактное, математическое описание поведения
▸
Конкретная реализация, работающая на архитектуре
▸
Задаёт действие для КАЖДОЙ возможной истории
восприятий
▸
Архитектура — компьютер, датчики, исполнительные
механизмы
▸
Удобна для анализа и сравнения агентов
▸
Программа + архитектура = агент
▸
На практике нереализуема напрямую — таблица
бесконечно велика
▸
Именно программу агента мы проектируем и пишем на
практике
Основы ИИ · Недели 2–3
4 / 25

5.

Модель PEAS
P
E
A
S
Performance measure
Environment
Actuators
Sensors
Критерий эффективности
Среда
Исполнительные механизмы
Датчики
Показатель, по которому
оценивается успешность работы
агента
Пространство, в котором
действует агент
С помощью чего агент
воздействует на среду
С помощью чего агент получает
информацию о среде
Основы ИИ · Недели 2–3
5 / 25

6.

PEAS: пример — автономный автомобиль
Performance
Безопасность, соблюдение правил, скорость движения, комфорт пассажиров, расход топлива
Environment
Дороги, другие автомобили, пешеходы, светофоры, дорожные знаки, погодные условия
Actuators
Руль, педали газа и тормоза, указатели поворота, звуковой сигнал, дисплей
Sensors
Камеры, радар и лидар, GPS, датчики скорости и одометр, датчики положения двигателя
Основы ИИ · Недели 2–3
6 / 25

7.

PEAS: пример — робот-пылесос
Performance
Чистота пола, экономия времени и энергии, отсутствие повреждений мебели
Environment
Комната, ковры, мебель, лестницы и перепады высоты пола
Actuators
Колёса привода, вращающиеся щётки, всасывающий насос
Sensors
Датчики удара (бампер), инфракрасные датчики, датчики обрыва пола (лестниц)
Основы ИИ · Недели 2–3
7 / 25

8.

Свойства среды (1)
Наблюдаемость
Детерминированность
Полностью наблюдаемая
Детерминированная
датчики дают полную информацию о состоянии среды (шахматы на
экране)
следующее состояние однозначно определяется текущим
состоянием и действием
Частично наблюдаемая
Стохастическая
часть информации скрыта или зашумлена (покер, вождение в
тумане)
присутствует элемент случайности или неопределённости (прогноз
погоды)
Основы ИИ · Недели 2–3
8 / 25

9.

Свойства среды (2)
Эпизодичность
Динамичность
Эпизодическая
Статическая
каждое решение не зависит от предыдущих (контроль качества
деталей на конвейере)
среда не меняется, пока агент обдумывает решение (кроссворд)
Последовательная
Динамическая
текущее решение влияет на будущие решения (игра в шахматы)
среда меняется в реальном времени, независимо от агента
(вождение автомобиля)
Основы ИИ · Недели 2–3
9 / 25

10.

Свойства среды (3)
Дискретность
Число агентов
Дискретная
Одноагентная
конечное число чётко различимых состояний и действий (шахматы)
в среде действует только один агент (разгадывание кроссворда)
Непрерывная
Многоагентная
бесконечное множество состояний, значения меняются плавно
(скорость и положение автомобиля)
несколько агентов, конкурирующих или сотрудничающих (шахматы,
команда роботов-курьеров)
Основы ИИ · Недели 2–3
10 / 25

11.

Типы агентов: пять уровней сложности
1
Простой рефлекторный агент
Реагирует по правилу «если…то…», без памяти
2
Агент на основе модели
Хранит внутреннюю модель состояния среды
3
Агент на основе цели
Действует, ориентируясь на достижение цели
4
Агент на основе полезности
Оценивает и сравнивает качество разных состояний
5
Обучающийся агент
Улучшает своё поведение на основе опыта
Основы ИИ · Недели 2–3
11 / 25

12.

Тип 1
Простой рефлекторный агент
Восприятие → Правило «если…то…» → Действие
▸ Реагирует только на текущее восприятие, без учёта истории
▸ Использует условно-действенные правила (condition-action rules)
▸ Не хранит внутреннего состояния и не строит модель мира
▸ Прост и быстр, но эффективен только в полностью наблюдаемых средах
▸ Пример: термостат — «если температура ниже нормы, то включить отопление»
Основы ИИ · Недели 2–3
12 / 25

13.

Тип 2
Агент, основанный на модели
Восприятие + Внутренняя модель среды → Правило → Действие
▸ Хранит внутреннее состояние — модель того, как устроен мир
▸ Учитывает, как среда меняется независимо от агента
▸ Учитывает, как собственные действия агента влияют на среду
▸ Может успешно работать в частично наблюдаемых средах
▸ Пример: робот-пылесос, помнящий, какие комнаты уже убраны
Основы ИИ · Недели 2–3
13 / 25

14.

Тип 3
Агент, основанный на цели
Восприятие + Модель + Цель → Поиск подходящего действия → Действие
▸ Помимо модели среды имеет чёткое представление о цели (goal)
▸ Оценивает, какое действие приближает его к достижению цели
▸ Способен «заглядывать вперёд», рассматривая последствия действий
▸ Требует механизмов поиска и планирования — отсюда связь с темой алгоритмов поиска
▸ Пример: GPS-навигатор, выбирающий маршрут к заданному пункту назначения
Основы ИИ · Недели 2–3
14 / 25

15.

Тип 4
Агент, основанный на полезности
Восприятие + Модель + Функция полезности → Максимизация полезности → Действие
▸ Одной цели часто недостаточно — к ней ведёт несколько разных путей
▸ Функция полезности (utility function) оценивает, насколько «хорошо» состояние
▸ Агент выбирает действие, максимизирующее ожидаемую полезность
▸ Позволяет сравнивать и уравновешивать конфликтующие критерии (скорость и безопасность)
▸ Пример: маршрутизатор, выбирающий не просто короткий, а быстрый, безопасный и экономичный путь
Основы ИИ · Недели 2–3
15 / 25

16.

Обучающийся агент
Тип 5
1
2
3
4
Исполняющий элемент
Критик
Обучающий элемент
Генератор задач
Performance element
Critic
Learning element
Problem generator
выбирает внешние действия — то,
что раньше выполнял агент
целиком
оценивает поведение агента по
внешним стандартам качества
вносит улучшения в работу
исполняющего элемента
предлагает новые,
исследовательские действия для
получения полезного опыта
Основы ИИ · Недели 2–3
16 / 25

17.

Итоги: пять типов агентов
Тип агента
Память / модель
Учитывает цель
Пример
Нет
Нет
Термостат
На основе модели
Да (состояние среды)
Нет
Пылесос с картой комнат
На основе цели
Да
Да
GPS-навигатор
На основе полезности
Да
Да + оценка качества
Умный маршрутизатор
Да, постоянно улучшается
Да
Рекомендательная система
Простой рефлекторный
Обучающийся
Основы ИИ · Недели 2–3
17 / 25

18.

Как агент находит путь к своей цели?
От интеллектуальных агентов — к алгоритмам поиска в пространстве состояний
▸ Агент, основанный на цели, должен уметь находить последовательность действий, ведущую к
цели
▸ Эта задача формализуется как поиск в пространстве состояний
▸ Результат поиска — план: последовательность действий от начального состояния к целевому
Основы ИИ · Недели 2–3
18 / 25

19.

Компоненты задачи поиска
1
Начальное состояние
точка, из которой агент начинает поиск
2
Действия / операторы
множество допустимых действий в каждом состоянии
3
Модель перехода
результат применения действия к состоянию — новое состояние
4
Целевой тест
проверка, является ли состояние целевым
5
Стоимость пути
числовая цена последовательности действий (шагов, времени, расстояния)
Основы ИИ · Недели 2–3
19 / 25

20.

Дерево поиска и стратегии поиска
Дерево поиска: корень = начальное состояние, ветви =
действия
Слепой
(неинформированный)
поиск
Эвристический
(информированный) поиск
▸
Не использует дополнительную
информацию о близости к цели
▸
▸
Опирается только на структуру
задачи
Использует эвристическую функцию
— оценку «перспективности»
состояния
▸
Позволяет находить решение
быстрее и эффективнее
▸
Пример: A*
▸
Основы ИИ · Недели 2–3
Примеры: BFS, DFS
20 / 25

21.

Breadth-First Search
BFS — поиск в ширину
Исследование дерева уровень за уровнем
Структура данных: очередь FIFO (первым пришёл — первым вышел)
▸ Исследует состояния уровень за уровнем, начиная с ближайших к старту
▸ Прежде чем перейти на следующий уровень, полностью раскрывает текущий
▸ Гарантированно находит кратчайший путь по числу шагов (при равной цене шагов)
▸ Требует значительного объёма памяти — хранит все узлы текущего уровня
▸ Полнота: да · Оптимальность: да (при единичной стоимости шагов)
Основы ИИ · Недели 2–3
21 / 25

22.

Depth-First Search
DFS — поиск в глубину
Погружение по одной ветке до конца, затем возврат (backtracking)
Структура данных: стек LIFO (последним пришёл — первым вышел) или рекурсия
▸ Идёт по одной ветке дерева максимально глубоко, прежде чем вернуться назад
▸ При достижении тупика выполняет откат (backtracking) к предыдущему узлу
▸ Экономичен по памяти по сравнению с BFS
▸ Не гарантирует нахождение кратчайшего пути
▸ Без ограничения глубины может «зависнуть» в бесконечной или очень длинной ветке
Основы ИИ · Недели 2–3
22 / 25

23.

A* — эвристический поиск
f(n) = g(n) + h(n)
g(n)
h(n)
f(n)
фактическая стоимость пути от начального состояния
до узла n
эвристическая оценка стоимости пути от узла n до
цели
оценка полной стоимости пути через узел n
▸
На каждом шаге раскрывает узел с наименьшим значением f(n)
▸
Сочетает точные знания о пройденном пути (g) с оценкой оставшегося пути (h)
▸
При допустимой эвристике (h никогда не завышает реальную стоимость) находит оптимальный путь
▸
Значительно эффективнее слепого поиска за счёт «направленного» движения к цели
▸
Широко применяется в навигации, компьютерных играх и робототехнике
Основы ИИ · Недели 2–3
23 / 25

24.

Сравнение BFS, DFS и A*
Критерий
BFS
DFS
A*
Очередь (FIFO)
Стек (LIFO)
Приоритетная очередь
Да
Не всегда
Да (с допустимой эвристикой)
Оптимальность
Да (равные шаги)
Нет
Да (с допустимой эвристикой)
Затраты памяти
Высокие
Низкие
Средние – высокие
Нет
Нет
Да
Структура данных
Полнота
Использует эвристику
Основы ИИ · Недели 2–3
24 / 25

25.

Заключение
Ключевые выводы
✓
✓
✓
Агент = восприятие + действие; полностью описывается через
модель PEAS
Свойства среды определяют, насколько сложным должен быть
агент
Пять типов агентов — путь от простой реакции к
самостоятельному обучению
✓
Поиск в пространстве состояний — инструмент
целенаправленных агентов
✓
BFS, DFS и A* — три базовые стратегии поиска решения задачи
Основы ИИ · Недели 2–3
Вопросы для закрепления
1. Приведите собственный пример PEAS для любого выбранного
вами агента.
2. Чем статическая среда отличается от динамической? Приведите
пример.
3. Почему алгоритм A* на практике обычно эффективнее BFS?
4. В каких случаях DFS предпочтительнее BFS, а в каких — наоборот?
25 / 25