Исследования в области планирования начались с попытки сконструировать роботов, которые бы выполняли свои задачи с некоторой степенью гибкости и способностью реагировать на окружающий мир. Планирование предполагает, что робот должен уметь выполнять некоторые элементарные действия. Он пытается найти последовательность таких действий, с помощью которой можно выполнить более сложную задачу, например, двигаться по комнате, заполненной препятствиями.
Планирование по ряду причин является сложной проблемой, не малую роль в этом играет размер пространства возможных последовательностей шагов. Даже очень простой робот способен породить огромное число различных комбинации элементарных движений. Представьте себе, к примеру, робота, который может передвигаться вперед, назад, влево и вправо, и вообразите, сколькими различными путями он может двигаться по комнате. Представьте также, что в комнате есть препятствия, и что робот должен выбирать путь вокруг них некоторым оптимальным образом. Для написания программы, которая могла бы разумно определить лучший путь из всех вариантов, и не была бы при этом перегружена огромным их числом, потребуются сложные методы для представления пространственного знания и управления перебором в пространстве альтернатив.
Одним из методов, применяемых человеческими существами при планировании, является иерархическая декомпозиция задачи. Планируя путешествие в Лондон, Вы, скорее всего, займетесь отдельно проблемами организации перелета, поездки до аэропорта, самого полета и поиска подходящего вида транспорта в Лондоне, хотя все они являются частью большого общего плана. Каждая из этих задач может сама быть разбита на такие подзадачи, как, например, покупка карты города, преодоление лабиринта линий метро и поиск подходящего ресторана. Такой подход не только эффективно ограничивает размер пространства поиска, но и позволяет сохранять часто используемые маршруты для дальнейшего применения.
В то время как люди разрабатывают планы безо всяких усилий, создание компьютерной программы, которая бы занималась тем же – сложная проблема. Казалось бы, такая простая вещь, как разбиение задачи на независимые подзадачи, на самом деле требует изощренных эвристик и обширного знания об области планирования. Не менее сложная проблема – определить, какие планы следует сохранить, и как их обобщить для использования в будущем.
Робот, слепо выполняющий последовательности действий, не реагируя на изменения в своем окружении, или неспособный обнаруживать и исправлять ошибки в своем собственном плане, едва ли может считаться разумным. Зачастую от робота требуют сформировать план, основанный на недостаточной информации, и откорректировать свое поведение по мере его выполнения. Робот может не располагать адекватными сенсорами для того, чтобы обнаружить все препятствия на проектируемом пути. Такой робот должен начать двигаться по комнате, основываясь на «воспринимаемых» им данных, и корректировать свой путь по мере того, как выявляются другие препятствия. Организация планов, позволяющая реагировать на изменение условий окружающей среды – основная проблема планирования.
Наконец, робототехника была одной из областей исследований искусственного интеллекта, породившей множество концепций, лежащих в основе агентно-ориентированного принятия решений. Исследователи, потерпевшие неудачу при решении проблем, связанных с большими пространствами представлений и разработкой алгоритмов поиска для традиционного планирования, переформулировали задачу в терминах взаимодействия полуавтономных агентов. Каждый агент отвечает за свою часть задания, и общее решение возникает в результате их скоординированных действий.
Исследования в области планирования сегодня вышли за пределы робототехники, теперь они включают также координацию сложных систем задач и целей. Современные планировщики применяются как в агентских средах, так и для управления ускорителями частиц.
