En robótica y planificación del movimiento , la planificación cinodinámica es una clase de problemas para los que se deben cumplir los límites de velocidad , aceleración y fuerza / par, junto con restricciones cinemáticas como evitar obstáculos. El término fue acuñado por Bruce Donald , Pat Xavier, John Canny y John Reif. [1] Donald y col. desarrolló los primeros esquemas de aproximación de tiempo polinómico (PTAS) para el problema. Al proporcionar un algoritmo de aproximación ε de tiempo polinomial comprobable, resolvieron un problema abierto de larga data con un control óptimo. Su primer artículo consideró el control óptimo en el tiempo ("camino más rápido") de una masa puntual bajo la dinámica newtoniana , en medio de obstáculos poligonales (2D) o poliédricos (3D), sujetos a límites estatales de posición, velocidad y aceleración. Más tarde, ampliaron la técnica a muchos otros casos, por ejemplo, a robots cinemáticos de cadena abierta 3D bajo dinámica lagrangiana completa . Más recientemente, muchos algoritmos heurísticos prácticosbasados en la optimización estocástica y el muestreo iterativo, fueron desarrollados por una amplia gama de autores para abordar el problema de la planificación cinodinámica. Se ha demostrado que estas técnicas de planificación cinodinámica funcionan bien en la práctica. Sin embargo, ninguna de estas técnicas heurísticas puede garantizar la optimización de la solución calculada (es decir, no tienen garantías de rendimiento), y ninguna puede demostrarse matemáticamente que sea más rápida que los algoritmos PTAS originales (es decir, ninguna tiene una complejidad computacional demostrablemente menor) .
Referencias
- ^ Donald, B .; Xavier, P .; Canny, J .; Reif, J. (1993), "Planificación del movimiento cinodinámico" (PDF) , Journal of the ACM , 40 (5): 1048–1066, CiteSeerX 10.1.1.51.1443 , doi : 10.1145 / 174147.174150