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