Planowanie kinodynamiczne

W robotyce i planowaniu ruchu planowanie kinodynamiczne jest klasą problemów, dla których muszą być spełnione ograniczenia prędkości , przyspieszenia i siły/momentu obrotowego , wraz z ograniczeniami kinematycznymi, takimi jak unikanie przeszkód. Termin ten został ukuty przez Bruce'a Donalda , Pata Xaviera, Johna Canny'ego i Johna Reifa. Donalda i in. opracował pierwsze schematy aproksymacji czasu wielomianowego (PTAS) dla tego problemu. Zapewniając możliwy do udowodnienia czas wielomianu Algorytm aproksymacji ε rozwiązali długotrwały otwarty problem optymalnej kontroli. Ich pierwszy artykuł dotyczył optymalnej czasowo kontroli („najszybszej ścieżki”) masy punktowej w warunkach dynamiki Newtona , pośród wielokątnych (2D) lub wielościennych (3D) przeszkód, z zastrzeżeniem ograniczeń stanu dotyczących położenia, prędkości i przyspieszenia. Później rozszerzyli tę technikę na wiele innych przypadków, na przykład na trójwymiarowe roboty kinematyczne z otwartym łańcuchem przy pełnej dynamice Lagrange'a . Ostatnio wiele praktycznych algorytmów heurystycznych oparte na optymalizacji stochastycznej i iteracyjnym próbkowaniu zostały opracowane przez wielu autorów w celu rozwiązania problemu planowania kinodynamicznego. Wykazano, że te techniki planowania kinodynamicznego działają dobrze w praktyce. Jednak żadna z tych heurystycznych technik nie może zagwarantować optymalności obliczonego rozwiązania (tj. nie ma gwarancji wydajności) i żadna nie może być matematycznie udowodniona, że ​​jest szybsza niż oryginalne algorytmy PTAS (tj. żadna nie ma udowodnionej niższej złożoności obliczeniowej) .