Linear-quadratic regulator rapidly exploring random tree
Linear-quadratic regulator rapidly exploring random tree 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. The method is an extension of the rapidly exploring random tree, a widely used approach to motion planning.
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. 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. Finding a feasible trajectory in the complex state space is a demanding problem for mathematics.
Description
LQR tracking
Linear-quadratic regulator 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. 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. 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.