Linear-quadratic regulator rapidly-exploring random tree

From HandWiki
LQR-RRT
ClassKinodynamic motion planning
Worst-case performanceO(n log n)
Worst-case space complexityO(n)

Linear-quadratic regulator rapidly-exploring random tree (LQR-RRT) is a sampling based algorithm for kinodynamic planning. A solver is producing random actions which are forming a funnel in the state space. The generated tree is the action sequence which fulfills the cost function. The restriction is, that a prediction model, based on differential equations, is available to simulate a physical system.

Motivation

Cart-pendulum

The control theory is using differential equations to describe complex physical systems like an inverted pendulum.[1] A set of differential equations forms a physics engine which maps the control input to the state space of the system. The forward model is able to simulate the given domain. For example, if the user pushes a cart to the left, a pendulum mounted on the cart will react with a motion. The exact force is determined by newton's laws of motion.

A solver, for example PID controllers and model predictive control, are able to bring the simulated system into a goal state. From an abstract point of view, the problem of controlling a complex physical system is a kinodynamic motion planning problem.[2] In contrast to a normal path planning problem, the state space isn't only a 2d map which contains x and y coordinates. But a physical underactuated system has much more dimension, e.g. the applied forces, rotating angles and friction to the ground.[3] Finding a feasible trajectory in the complex state space is a demanding problem for mathematics.

Description

LQR tracking

MPC scheme basic

Linear-quadratic regulator (LQR) is a goal formulation for a system of differential equations.[4] It defines a cost function but doesn't answer the question of how to bring the system into the desired state. In contrast to linear problems, for example a line following robot, kinodynamic problems can be solved not with a single action but with a trajectory of many control signals. These signals are determined and constantly updated with the receding horizon strategy, also known as model predictive control (MPC). LQR tracking means to find and evaluate trajectories for solving a system of differential equations.

In contrast to a PID controller, which is only able to find the next control action, a LQR tree is able to store a sequence of actions in advance.[5] This is equal to a multistage solver which keeps the time horizon in mind. An action taken in the now will affect the system indirectly in the future with a delayed feedback.

History

Astronaut and Expedition 66 Flight Engineer Matthias Maurer is pictured inside the Kibo laboratory module setting up an Astrobee robotic free-flyer for the ReSWARM experiment.

The algorithm is a university-driven research project. The first version was developed by Perez et al. at the Massachusetts Institute of Technology in 2012 in the AI laboratory.[3] In 2016 the algorithm was listed in a survey of control techniques for autonomous vehicles[6] and was adapted by other academic robotics teams like University of Florida for building experimental path planners. In 2018, the algorithm was included in the Pythonrobotics library.[7] The algorithm is currently being tested on the Astrobee, a six degree of freedom (DOF) free-flyer with a 3 DOF robotic arm in the International Space Station.[8][9][10][11] It is currently part of the Relative Satellite Swarming and Robotic Maneuvering (ReSWARM) experiments taking place at the International Space Station since April 2021 starting with expeditions 65 and 66.[12][13][14][15] Future experiments will entail physical manipulation of objects to further validate the on-orbit assembly demonstration, consideration of physical objects for real-time mapping and collision avoidance, and bringing the information-theoretic framework to a greater set of uncertain robots.[16]

References

  1. ↑ "How Long Does It Take for a Pencil to Tip Over?". WIRED. 2014-09-03. https://www.wired.com/2014/09/how-long-does-it-take-for-a-pencil-to-tip-over/. Retrieved 2020-08-19. 
  2. ↑ Jean-Paul Laumond; Mark Overmars (11 February 1997). Algorithms for Robotic Motion and Manipulation: WAFR 1996. CRC Press. pp. 109–. ISBN 978-1-4398-6452-4. https://books.google.com/books?id=pxK2DwAAQBAJ&pg=PT109. 
  3. ↑ 3.0 3.1 Alejandro Perez and Robert Platt and George Konidaris and Leslie Kaelbling and Tomas Lozano-Perez (2012). "2012 IEEE International Conference on Robotics and Automation". 2012 IEEE International Conference on Robotics and Automation. IEEE. pp. 2537–2542. doi:10.1109/icra.2012.6225177. ISBN 978-1-4673-1405-3. 
  4. ↑ "Watch An Inverted Pendulum - Arduino-Driven". 2018-06-02. https://www.i-programmer.info/news/91-hardware/11857-watch-an-inverted-pendulum-arduino-driven.html. 
  5. ↑ Philipp Reist and Pascal Preiswerk and Russ Tedrake (2016). "Feedback-motion-planning with simulation-based LQR-trees". The International Journal of Robotics Research (SAGE Publications) 35 (11): 1393–1416. doi:10.1177/0278364916647192. 
  6. ↑ Paden, Brian; Čáp, Michal; Yong, Sze Zheng; Yershov, Dmitry; Frazzoli, Emilio (March 2016). "A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles". IEEE Transactions on Intelligent Vehicles 1 (1): 33–55. doi:10.1109/TIV.2016.2578706. ISSN 2379-8904. https://ieeexplore.ieee.org/document/7490340. 
  7. ↑ Sakai, Atsushi and Ingram, Daniel and Dinius, Joseph and Chawla, Karan and Raffin, Antonin and Paques, Alexis (2018). "PythonRobotics: a Python code collection of robotics algorithms". arXiv:1808.10703 [cs.RO].CS1 maint: multiple names: authors list (link)
  8. ↑ Doerr, Bryce; Linares, Richard (2020-08-06). "Motion Planning and Control for On-Orbit Assembly using LQR-RRT* and Nonlinear MPC". arXiv:2008.02846 [cs.RO].
  9. ↑ "Research – ARCLab" (in en-US). http://arclab.mit.edu/research/. 
  10. ↑ "CSE alumnus researches the use of robotics in space" (in en). https://cse.umn.edu/college/feature-stories/cse-alumnus-researches-use-robotics-space. 
  11. ↑ Doerr, Bryce; Albee, Keenan; Ekal, Monica; Linares, Richard; Ventura, Rodrigo (2021-02-20). "Safe and Uncertainty-Aware Robotic Motion Planning Techniques for Agile On-Orbit Assembly". arXiv:2102.10348 [cs.RO].
  12. ↑ "Experiment Details". https://www.nasa.gov/mission_pages/station/research/experiments/explorer/Investigation.html?#id=8425. 
  13. ↑ "How to reach a tumbling target in space" (in en). https://news.mit.edu/2022/how-reach-tumbling-target-space-0225. 
  14. ↑ "December 6, 2021 – ISS On-Orbit Status Report" (in en-US). https://blogs.nasa.gov/stationreport/2021/12/06/. 
  15. ↑ Garcia, Mark (2021-12-10). "Astronaut Matthias Maurer is pictured inside the Kibo laboratory modul". http://www.nasa.gov/image-feature/astronaut-matthias-maurer-is-pictured-inside-the-kibo-laboratory-module. 
  16. ↑ Doerr, Bryce; Albee, Keenan; Ekal, Monica; Ventura, Rodrigo; Linares, Richard (2023-01-03). "The ReSWARM Microgravity Flight Experiments: Planning, Control, and Model Estimation for On-Orbit Close Proximity Operations". arXiv:2301.01319 [cs.RO].

External Links




Retrieved from "https://handwiki.org/wiki/index.php?title=Linear-quadratic_regulator_rapidly-exploring_random_tree&oldid=3670899"