Linear-quadratic regulator rapidly exploring random tree (LQR-RRT) is a sampling based algorithm for

kinodynamic planning In robotics and motion planning, kinodynamic planning is a class of problems for which velocity, acceleration, and force/torque bounds must be satisfied, together with kinematic constraints such as avoiding obstacles. The term was coined by Bruce ...

. 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 equation In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, an ...

s, is available to simulate a physical system.

Motivation

The

control theory Control theory is a field of mathematics that deals with the control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive the system to a ...

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 Newton's laws of motion are three basic laws of classical mechanics that describe the relationship between the motion of an object and the forces acting on it. These laws can be paraphrased as follows: # A body remains at rest, or in moti ...

. A solver, for example PID controllers and

model predictive control Model predictive control (MPC) is an advanced method of process control that is used to control a process while satisfying a set of constraints. It has been in use in the process industries in chemical plants and oil refineries since the 1980s. In ...

, 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 A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory. For instance, the toy ...

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 (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 A trajectory or flight path is the path that an object with mass in motion follows through space as a function of time. In classical mechanics, a trajectory is defined by Hamiltonian mechanics via canonical coordinates; hence, a complete traj ...

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 A proportional–integral–derivative controller (PID controller or three-term controller) is a control loop mechanism employing feedback that is widely used in industrial control systems and a variety of other applications requiring continuou ...

, 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 Time is the continued sequence of existence and events that occurs in an apparently irreversible succession from the past, through the present, into the future. It is a component quantity of various measurements used to sequence events, to co ...

in mind. An action taken in the now will affect the system indirectly in the future with a delayed feedback.

History

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. In 2016 the algorithm was listed in a survey of control techniques for autonomous vehicles 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. 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. 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. 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.

References

External Links

MIT ARCLab Microgavity Research

A Python Code Collection of Robotics Algorithms

LQR-RRT* code and visualization

PythonRobotics LQR-RRT* code

LQR-RRT* presentation
{{Control theory Optimal control Search algorithms