Кинодинамическое планирование - Kinodynamic planning
В робототехника и планирование движения, кинодинамическое планирование класс задач, для которых скорость, ускорение, и границы силы / крутящего момента должны быть выполнены вместе с кинематическими ограничениями, такими как избегание препятствий. Термин был придуман Брюс Дональд, Пэт Ксавьер, Джон Кэнни и Джон Рейф.[1] Дональд и др. разработал первый схемы полиномиальной аппроксимации (PTAS) за проблему. Предоставляя доказуемо полиномиальное время алгоритм ε-аппроксимации, они решили давнюю открытую проблему оптимального управления. Их первая статья рассматривала оптимальное по быстродействию управление («самый быстрый путь») точечной массы при Ньютоновская динамика, среди многоугольных (2D) или многогранных (3D) препятствий с учетом ограничений по положению, скорости и ускорению. Позже они распространили эту технику на многие другие случаи, например, на трехмерных кинематических роботов с открытой цепью при полном Лагранжева динамика. В последнее время многие практичные эвристические алгоритмы основанные на стохастической оптимизации и итеративной выборке были разработаны широким кругом авторов для решения проблемы кинодинамического планирования. Эти методы кинодинамического планирования показали свою эффективность на практике. Однако ни один из этих эвристических методов не может гарантировать оптимальность вычисленного решения (т. Е. У них нет гарантий производительности), и ни один из них не может быть математически доказан как быстрее, чем исходные алгоритмы PTAS (т. Е. Ни один из них не имеет доказуемо более низкой вычислительной сложности). .
использованная литература
- ^ Дональд, Б.; Xavier, P .; Кэнни, Дж.; Рейф, Дж. (1993), «Кинодинамическое планирование движения» (PDF), Журнал ACM, 40 (5): 1048–1066, CiteSeerX 10.1.1.51.1443, Дои:10.1145/174147.174150