Planowanie kinodynamiczne - Kinodynamic planning
W robotyce i planowaniu ruchu , kinodynamic planowanie jest klasa problemów, dla których prędkość , przyspieszenie granice, a siła / moment obrotowy musi być spełniony, wraz z kinematycznych ograniczeń, takich jak unikanie przeszkód. Termin został wymyślony przez Bruce'a Donalda , Pata Xaviera, Johna Canny'ego i Johna Reifa. Donalda i in. opracowali pierwsze wielomianowe schematy aproksymacji czasu (PTAS) dla tego problemu. Zapewniając możliwy do udowodnienia algorytm aproksymacji ε w czasie wielomianowym , rozwiązali od dawna otwarty problem w zakresie optymalnej kontroli. Ich pierwszy artykuł dotyczył optymalnej w czasie kontroli („najszybszej ścieżki”) masy punktowej w dynamice newtonowskiej , pośród wielokątnych (2D) lub wielościennych (3D) przeszkód, z zastrzeżeniem ograniczeń stanów dotyczących położenia, prędkości i przyspieszenia. Później rozszerzyli tę technikę na wiele innych przypadków, na przykład na roboty kinematyczne 3D z otwartym łańcuchem w pełnej dynamice Lagrange'a . Ostatnio wielu autorów opracowało wiele praktycznych algorytmów heurystycznych opartych na optymalizacji stochastycznej i iteracyjnym próbkowaniu w celu rozwiązania problemu planowania kinodynamicznego. Wykazano, że te techniki planowania kinodynamicznego dobrze sprawdzają się w praktyce. Jednak żadna z tych technik heurystycznych 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. żaden nie ma prawdopodobnie niższej złożoności obliczeniowej) .