Linear-quadratic regulator rapidly exploring random tree
 | This article, Linear-quadratic regulator rapidly exploring random tree, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
Comment: This appears to be original research and as such cannot be accepted as an article. To be notable as a Wikipedia topic, it needs multiple reliably published secondary sources (such as survey articles or books) that cover this specific topic in-depth and are independent of the topic (that is, by people other than its creators). Without such sources we cannot have an article. —David Eppstein (talk) 20:27, 7 July 2020 (UTC)
| Class | Kinodynamic motion planning |
|---|---|
| Worst-case performance | O(n log n) |
| Worst-case space complexity | O(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
The control theory is using differential equations to describe complex physical systems like an inverted pendulum. 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.[1] In contrast to a normal path planning problem, the state space isn't only a 2d map which contains of 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.[2] Finding a feasible trajectory in the complex state space is a demanding problem for mathematics.
Description
LQR tracking
Linear-quadratic regulator (LQR) is a goal formulation for a system of differential equations. 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.[3] 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.
Tree search in a forward model
Describing a physical system with differential equations is only the first step towards an advanced controller design. If the inner dynamics of a system were formalized, it is possible to simulate the system in a computer graphically. Non-linear systems described with differential equations are chaotic, which means, they behave unpredictable on the long run. The variables in the system are interacting with each other and additional control signals from the outside are sent to the system. This prevents a simple direct torque control in the sense, that control signal A will lead into a certain system state B.
To address the complexity, the forward model is simulated over the time axis in a graph structure.[4] In the game theory the principle is known as monte Carlo tree search. In the domain of physical simulation, the game rules are defined as mathematical functions like sinus and fractions which are describing the next step of the system in reaction to the previous step. A numerical solver is creating random inputs, then the outcome of the system is stored in a tree, and the procedure is repeated until a goal state is reached.[5][6]
A path in the system's game tree is called a trajectory, because it contains of more than a single action. The action sequence is applied to the dynamic system and produces a step response. The LQR-RRT algorithm makes sure that the optimal action is determined.
Difference to classical control theory
Classical control theory is focused on converting physical problems into a mathematical model. The goal is to invent differential equations which are simulating the real systems. The aim is to formalize existing systems as accurate as possible.
In contrast, the LQR-RRT algorithm assumes that a predictive model is already available and the problem is to bring the system into a goal state.[7] The challenge is to develop an automatic controller which calculates the action sequence for the system. Motion planning and especially kinodynamic motion planning is working on top of a physics engine.
Criticism
The algorithm wasn't able to stabilize the slipping bicycle model at certain configurations in the Matlab environment.[8] The reason is, that dynamical systems are too complex for the LQR-Tree searching algorithm. Another concern is, that the algorithm can't update the predictive model during runtime. Only learning based model predictive control is able to do so.[9]
References
- ^ Adnan Tahirovic and Faris Janjos (2018). A Class of SDRE-RRT Based Kinodynamic Motion Planners. 2018 Annual American Control Conference (ACC). IEEE. doi:10.23919/acc.2018.8431412.
- ^ Alejandro Perez and Robert Platt and George Konidaris and Leslie Kaelbling and Tomas Lozano-Perez (2012). LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics. 2012 IEEE International Conference on Robotics and Automation. IEEE. doi:10.1109/icra.2012.6225177.
- ^ Philipp Reist and Pascal Preiswerk and Russ Tedrake (2016). "Feedback-motion-planning with simulation-based LQR-trees". The International Journal of Robotics Research. 35 (11). SAGE Publications: 1393--1416. doi:10.1177/0278364916647192.
- ^ Reist, Philipp S (2015). Sensorless Juggling Machines and Chaos for Control (PhD). ETH Zurich.
- ^ Rust, Ian Charles (2010). Control of a nonlinear underactuated system with adaptation, numerical stability verification, and the use of the lqr trees algorithm (PhD). Massachusetts Institute of Technology.
- ^ Moore, Joseph Lawrence (2014). Robust post-stall perching with a fixed-wing UAV (PhD). Massachusetts Institute of Technology.
- ^ Albee, Keenan Eugene Sumner (2019). Toward optimal motion planning for dynamic robots: applications on-orbit (PhD). Massachusetts Institute of Technology.
- ^ Steve M Levine (2012). Sampling-based Planning Algorithms Applied to Bicycles.
- ^ Patrick Bouffard and Anil Aswani and Claire Tomlin (2012). Learning-based model predictive control on a quadrotor: Onboard implementation and experimental results. 2012 IEEE International Conference on Robotics and Automation. IEEE. doi:10.1109/icra.2012.6225035.
- Category:Optimal control
- Category:Search algorithms
| This article, Linear-quadratic regulator rapidly exploring random tree, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |