Кинодинамическое планирование

В робототехнике и движения планировании кинодинамическое планирование — это класс задач, для которых должны быть соблюдены границы скорости , ускорения и силы/крутящего момента, а также кинематические ограничения, такие как обход препятствий. Этот термин был придуман Брюсом Дональдом , Пэтом Ксавьером, Джоном Кэнни и Джоном Рейфом. Дональд и др. разработал первые схемы аппроксимации с полиномиальным временем (PTAS) для этой проблемы. Предложив с доказуемо полиномиальным временем алгоритм ε-аппроксимации , они решили давнюю открытую проблему оптимального управления. В их первой статье рассматривалось оптимальное по времени управление («самый быстрый путь») точечной массой в условиях ньютоновской динамики среди многоугольных (2D) или многогранных (3D) препятствий с учетом государственных ограничений на положение, скорость и ускорение. Позже они распространили эту технику на многие другие случаи, например, на 3D-кинематические роботы с открытой цепью при полной лагранжевой динамике . Совсем недавно множество практических эвристических алгоритмов, многие авторы разработали основанных на стохастической оптимизации и итеративной выборке, для решения проблемы кинодинамического планирования. Было показано, что эти методы кинодинамического планирования хорошо работают на практике. Однако ни один из этих эвристических методов не может гарантировать оптимальность вычисленного решения (т. е. у них нет гарантий производительности), и ни один из этих эвристических методов не может быть математически доказан быстрее, чем исходные алгоритмы PTAS (т. е. ни один из них не имеет доказуемо более низкой вычислительной сложности). .