Главная arrow Робототехника arrow Планирование движений
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Планирование движений Печать

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

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

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

В этой области робототехники нашел свое применение целый ряд методов организации работы в условиях неопределенности. Некоторые из этих методов основаны на алгоритмах принятия решений в условиях неопределенности. Если робот сталкивается с неопределенностью только при переходах из одного состояния в другое, но само состояние является полностью наблюдаемым, то эту задачу лучше всего можно промоделировать в виде марковского процесса принятия решения, или MDP (Markov Decision Process). Решением задачи MDP является оптимальная политика, с помощью которой робот может определить, что делать в каждом возможном состоянии. Таким образом, он получает возможность исправить погрешности движения всех видов, тогда как решение, полученное от детерминированного планировщика, с указанием единственного пути, может быть гораздо менее надежным. В робототехнике вместо термина политика обычно используют термин функция навигации. Функцию стоимости, можно преобразовать в такую функцию навигации, обеспечив отслеживание градиента.

Возникающая в результате задача управления роботом представляет собой частично наблюдаемую задачу MDP, или POMDP (partially observable MDP). В таких ситуациях робот обычно поддерживает внутреннее доверительное состояние, наподобие описанного в разделе 25.3. Решением задачи POMDP является политика, определенная на доверительных состояниях робота. Иными словами, входными данными для рассматриваемой политики является все распределение вероятностей. Это позволяет роботу основывать свое решение не только на том, что ему известно, но и на том, что неизвестно. Например, если робот действует в условиях неопределенности в отношении какой-то важной переменной состояния, он может принять рациональное в этих условиях решение и вызвать на выполнение  действие по сбору информации. Такой подход в инфраструктуре MDP невозможен, поскольку в задачах MDP подразумевается наличие полной наблюдаемости. К сожалению, методы точного решения задач POMDP не применимы к робототехнике, поскольку не существует известных методов для непрерывных пространств. А в результате дискретизации обычно создаются такие задачи POMDP, которые слишком велики, чтобы их можно было решить с помощью известных методов. Все, что можно сделать в настоящее время, — это пытаться свести неопределенность в отношении позы к минимуму; например, в эвристике  плавания вдоль берегов требуется, чтобы робот оставался неподалеку от известных отметок в целях уменьшения неопределенности в отношении его позы. Такая ситуация, в свою очередь, приводит к постепенному уменьшению неопределенности при нанесении на карту обнаруженных поблизости новых отметок, а это в дальнейшем позволяет роботу исследовать новые территории.