AI and robotics was researched since decades. In contrast to other disciplines like computer science or mathematics there was no success available. Even if AI researchers have analyzed the subject from a scientific perspective and discussed the situation at conferences there were not able to identify major problems or offer possible answers. What was happen instead was a long disappointing journey.
Even if AI in the past suffered, lots of subjects were analyzed. Notable examples are: autonomous robotics, model predictive control, genetic algorithms, reinforcement learning, Turing maschines. All these subjects were seen as promising candidates towards the pathway to intelligent machinery. They can be called advanced subjects in computer science and many papers were written. The general idea was to describe intelligence as an optimization problem which can be measured with a score. For example, trajectory optimization tries to reduce the costs, while genetic algorithms are maximing the fitness of candidates. In both cases the computer is a device for solving a mathematical problem.
On the first look, it makes sense to describe robotics movement with model predictve control algorithms. It helps to translate a problem from the reality towards an abstract mathematical equation. The idea is, that artificial intelligence can be realized as a combination of computer science, mathematics and game theory. Most researchers in the past would agree, that such kind of interdisplinary approach is a sign of excellence and allows to discover future robotics algorithms. What the researchers in the 1990s and 2000s didn't know was that the describe workflow is a dead end. None of mentioned techniques lead to artificial intelligence.
Model predictive control is a good example for a dead end in robotics resarch. The subject was researched by multiple researchers independend from each other with a great effort. There is no obvious mistake in the equation nor in a certain paper about the subject. At the same time, the entire model predictive control research has to be called a dead end because it fails to control simple robots.
In the history of artificial intelligence such kind of dead end is not an exception but its default situation. All the other attempts to realize robotics like expert system, neural networks and 5th generation programming languages like Prolog have failed too. It seems that there was a need to explore all the non working principles to get a better understanding what sort of approach won't result into a working robot.
Ai research in the past was realized as an intersection of physics models, mathematical theories and computer science. The hope was that the combination of these powerful disciplines allows to create intelligent machinery. For example trajectory optimiziation has a background in theoretical physics, and can be implemented as an algorithm on a computer. This would allow to plan the movement of a robot.
What was unknown in the past or perhaps it was ignored was, that the state space in robotics is too large to use mathematical optimization problems. Predicting future states of a system is only possible if the system consists of a few variables e.g. in a predator-prey scenario modelled with Lotka–Volterra equations. Such a system can be calculated on a computer and future states can be processed in advanced. The concept fails on robotics domains like dexterous grasping or biped walking. The equations are not known or they are too complicated the calculate. Even if there are realistic physics simulators available like Box2D, its not possible to determine future states of these engines into the future.
Despite this pessimistic situation it makes sense to explore model predtctive control and other mathematical optimization techniques because it allows a better understanding of np hard problems. If its known, that the state space in robotics is too large, its possible to rethink about the situation and explore strategies how to reduce the state space. A state space reduction is the pathway to advanced robotics.
Showing posts with label MPC. Show all posts
Showing posts with label MPC. Show all posts
July 09, 2026
The slow emergence of Artificial Intelligence
December 16, 2019
Some details about Model predictive control
Jacques Richalet has published in 1978 the first paper about model predictive control. In that time only trivial examples were solved with the technique. Controlling biped robots with the same approach is discussed in the literature since around 2010. It's a very powerful control technique and it make sense to explain what the idea is.
The main problem for a robot control system is to determine the next action. A robot consists of joints and the question is in which direction the joints has to be moved so that the robot is doing something useful. Answering this question with software is possible but very complicated. The reason is the absence of a model. A model is a sandbox in which an action make sense. The best example for a model is a chess engine. A chess engine accepts a move and it puts the system into the follow up state. So what is a chess engine? Somebody may argue, that it's equal to an Artificial Intelligence, but this answer is not accurate enough. A chess game can be played by two human users without any AI. The game engine provides only the sandbox in which the users can take actions. So the more elaborated answer is, that a chess engine is a model of the game of chess.
Another kind of technology goes into the similar direction which is called a physics engine. Some physics engines like bullet are available. They are the basis of modern games. The typical interaction with a physics engine api is, that the programmer is doing the following steps:
1. initialize the world with some objects: box1, box2, joint1, joint2
2. send a command to the physics engine, e.g. “joint1=-1”
3. update of the engine, e.g. “engine.step(10 milliseconds)
4. print out the values of the objects to the graphics display
A physics engine is a model. It accepts commands from the outside and is able to predict future states. The prediction gets initiated with the update-method. The programmer can decide to move the physics engine for 10 milliseconds forward in time. The principle of a physics engine can be transferred into the domain of model predictive control. The result is a new kind of problem: who should the model look like to solve a certain problem?
For example, there is a robotarm which contains of 3 joints and has a gripper. The task to is program for this robot a model which accepts some actions. The model needs to be fast and accurate at the same time. If such a model is available, it's possible to search in the game tree for a desired state. It's the same principle used for realizing chess AI and TicTacToe AI players.
The advantage of model predictive control over direct control is, the ability to figure out action sequences. Complex systems need more than a single action, but around 3-10 are needed to reach the goal state.
The main problem for a robot control system is to determine the next action. A robot consists of joints and the question is in which direction the joints has to be moved so that the robot is doing something useful. Answering this question with software is possible but very complicated. The reason is the absence of a model. A model is a sandbox in which an action make sense. The best example for a model is a chess engine. A chess engine accepts a move and it puts the system into the follow up state. So what is a chess engine? Somebody may argue, that it's equal to an Artificial Intelligence, but this answer is not accurate enough. A chess game can be played by two human users without any AI. The game engine provides only the sandbox in which the users can take actions. So the more elaborated answer is, that a chess engine is a model of the game of chess.
Another kind of technology goes into the similar direction which is called a physics engine. Some physics engines like bullet are available. They are the basis of modern games. The typical interaction with a physics engine api is, that the programmer is doing the following steps:
1. initialize the world with some objects: box1, box2, joint1, joint2
2. send a command to the physics engine, e.g. “joint1=-1”
3. update of the engine, e.g. “engine.step(10 milliseconds)
4. print out the values of the objects to the graphics display
A physics engine is a model. It accepts commands from the outside and is able to predict future states. The prediction gets initiated with the update-method. The programmer can decide to move the physics engine for 10 milliseconds forward in time. The principle of a physics engine can be transferred into the domain of model predictive control. The result is a new kind of problem: who should the model look like to solve a certain problem?
For example, there is a robotarm which contains of 3 joints and has a gripper. The task to is program for this robot a model which accepts some actions. The model needs to be fast and accurate at the same time. If such a model is available, it's possible to search in the game tree for a desired state. It's the same principle used for realizing chess AI and TicTacToe AI players.
The advantage of model predictive control over direct control is, the ability to figure out action sequences. Complex systems need more than a single action, but around 3-10 are needed to reach the goal state.
December 13, 2019
Building advanced robotics with model predictive control
In the late 1980s, Rodney Brooks has argued, that reactive architectures are able to control simple robots. So called scripted AI and behavior trees are used for direct control of a robot. The idea is, that the programmer defines motion primitives like moveto, grasp, ungrasp and then more complex behaviors can be built. But there is a problem with this approach because in reality it's hard to scale up the idea and most of these reactive controlled robots are only able to follow a line.
The problem is, that it's unclear which motion primitives are needed in the concrete example to solve a task. The good news is, that there is more powerful technique available which is called model predictive control (MPC). The idea is to divide the programming task into two steps: system identification and controller design. In the first step it is defined what the concrete domain is. The step of model building is ignored in direct control but for MPC it's important.
So the question is: what is a model? A model is a short term for “forward model”, and this is equal to a game engine. For example, in the TicTacToe game, the model is the part of the software which formalizes the game rules. It's equal to an API, the programmer can send the next action to the game engine and this brings the engine into a follow up state. A forward model is able to predict future states. That means, it's possible to send a sequence of actions to the engine.
In case of model predictive control, the games which are played have to do with control games in physical environments. A typical example is a two wheeled robot which can move the left wheel or the right wheel. If the robot is doing so, he changes the direction. The amount of change is encoded in the forward model of the robot.
The reason why model predictive control is misinterpreted sometimes is because such a forward model is complicated to build and it's hard to imagine why it's useful. Suppose, an elaborated model was created for the two wheel robot, what's next? Right the model itself can't control the robot, this task has to be done by the controller which is located in the second step of the MPC-framework. The motivation is high to ignore the forward model and start with the AI controller. This principle is called direct control, or reactive control, because no model is available.
The disadvantage is, that without a model it's not possible to plan over longer horizons. And this results into low complexity systems. The better idea is to focus on model building first. Let me give an example. Suppose, there is a robotarm who should do a task. Instead of figure out who to program the robot the starting point is to analyze the domain. That means, the robot arm has to be converted into a game engine. The question is not, what is the next action but it's a “what-if” problem. What happens, if the robot moves the joint0 for 10 seconds to the left? What happens if the gripper is open?
Solving computer games is usually done with Artificial Intelligence. The idea is, that there is a game and then an advanced AI Solver is used to play the game autonomously. The bottleneck is not to program the solver for the game, but the challenge is to formalize the game. The rules of some easy games like pong are known. For example, if the ball collides with the border he will move it's direction. For robotics control problems, the game rules are not known. That means, each robot is playing a game, but the inner working of this game are not available.
What human operators can do is not only to control a robot, but they know also what will happen in a certain situation. In the literature this is sometimes called “qualitative reasoning”. It means, that for the human operator it's obvious that the after the gripper was opened, the object will fall down.
From remote control to fully autonomous robots
The first step in realizing a robotics system is a remote controlled system. That means, the human operator has to press the joystick and this will move the robotarm. Such a control technique is remarkable robust, because the human operator is using his own skills to produce the next control actions. Most cranes on real construction sites are working with this principle.
The more challenging problem is to remove the human operator from the loop and control the robot only with software. Such a system is needed for reducing the costs. Realizing such goal is possible with so called model predictive control (MPC). MPC means, that the human operator only provides higher goals and the motion controller is figuring out the detailed actions. A typical example for a robot crane would be, that the human operator places doesn't operates the crane directly but he drags and drops the container to the target location. It's up to the robot to figure out how to do so.
From a computational perspective a high level goal is equal to a constraint. What the human operator provides is a goal within the game tree. The solver has to explore the game tree for finding an action sequence which brings the system into the desired state. Browsing through the game tree is only possible if the game rules are known. This step is known as system identification. System identification describes the possible action of a robot and the result. It's the same like building a physics engine or a forward model.
The reason why MPC is a powerful technique for controlling a robot system is because it divides the overall task into two subproblems. First, system identification and second, fulfill the constraints by searching for an action sequence. The part with finding out the concrete actions can be ignored, because the problem can be solved easily with brute force search, similar how a chess engine is working. The gametree is explored, and if the computer hardware is fast enough, it will produce the next action in realtime. The more interesting problem is creating the forward model. The interesting fact is, that for nearly all robotics problem, no forward model is available. The only thin which goes into that direction are physics engines used in computer games, but there is a difference between a physics engine and an MPC controller.
What robotics programmer have to implement is a dedicated forward model which works much faster than a classical physics engine. It's equal to program a simulator which can answer “what-if” questions. For example, “What will happen if the crane is moving to the left?” On the first look, it's obvious what will happen, but the problem is, that the information isn't available for the computer. Creating a software module which can answer “what-if” question very fast is the fundamental step in realizing model predictive control.
The problem is, that it's unclear which motion primitives are needed in the concrete example to solve a task. The good news is, that there is more powerful technique available which is called model predictive control (MPC). The idea is to divide the programming task into two steps: system identification and controller design. In the first step it is defined what the concrete domain is. The step of model building is ignored in direct control but for MPC it's important.
So the question is: what is a model? A model is a short term for “forward model”, and this is equal to a game engine. For example, in the TicTacToe game, the model is the part of the software which formalizes the game rules. It's equal to an API, the programmer can send the next action to the game engine and this brings the engine into a follow up state. A forward model is able to predict future states. That means, it's possible to send a sequence of actions to the engine.
In case of model predictive control, the games which are played have to do with control games in physical environments. A typical example is a two wheeled robot which can move the left wheel or the right wheel. If the robot is doing so, he changes the direction. The amount of change is encoded in the forward model of the robot.
The reason why model predictive control is misinterpreted sometimes is because such a forward model is complicated to build and it's hard to imagine why it's useful. Suppose, an elaborated model was created for the two wheel robot, what's next? Right the model itself can't control the robot, this task has to be done by the controller which is located in the second step of the MPC-framework. The motivation is high to ignore the forward model and start with the AI controller. This principle is called direct control, or reactive control, because no model is available.
The disadvantage is, that without a model it's not possible to plan over longer horizons. And this results into low complexity systems. The better idea is to focus on model building first. Let me give an example. Suppose, there is a robotarm who should do a task. Instead of figure out who to program the robot the starting point is to analyze the domain. That means, the robot arm has to be converted into a game engine. The question is not, what is the next action but it's a “what-if” problem. What happens, if the robot moves the joint0 for 10 seconds to the left? What happens if the gripper is open?
Solving computer games is usually done with Artificial Intelligence. The idea is, that there is a game and then an advanced AI Solver is used to play the game autonomously. The bottleneck is not to program the solver for the game, but the challenge is to formalize the game. The rules of some easy games like pong are known. For example, if the ball collides with the border he will move it's direction. For robotics control problems, the game rules are not known. That means, each robot is playing a game, but the inner working of this game are not available.
What human operators can do is not only to control a robot, but they know also what will happen in a certain situation. In the literature this is sometimes called “qualitative reasoning”. It means, that for the human operator it's obvious that the after the gripper was opened, the object will fall down.
From remote control to fully autonomous robots
The first step in realizing a robotics system is a remote controlled system. That means, the human operator has to press the joystick and this will move the robotarm. Such a control technique is remarkable robust, because the human operator is using his own skills to produce the next control actions. Most cranes on real construction sites are working with this principle.
The more challenging problem is to remove the human operator from the loop and control the robot only with software. Such a system is needed for reducing the costs. Realizing such goal is possible with so called model predictive control (MPC). MPC means, that the human operator only provides higher goals and the motion controller is figuring out the detailed actions. A typical example for a robot crane would be, that the human operator places doesn't operates the crane directly but he drags and drops the container to the target location. It's up to the robot to figure out how to do so.
From a computational perspective a high level goal is equal to a constraint. What the human operator provides is a goal within the game tree. The solver has to explore the game tree for finding an action sequence which brings the system into the desired state. Browsing through the game tree is only possible if the game rules are known. This step is known as system identification. System identification describes the possible action of a robot and the result. It's the same like building a physics engine or a forward model.
The reason why MPC is a powerful technique for controlling a robot system is because it divides the overall task into two subproblems. First, system identification and second, fulfill the constraints by searching for an action sequence. The part with finding out the concrete actions can be ignored, because the problem can be solved easily with brute force search, similar how a chess engine is working. The gametree is explored, and if the computer hardware is fast enough, it will produce the next action in realtime. The more interesting problem is creating the forward model. The interesting fact is, that for nearly all robotics problem, no forward model is available. The only thin which goes into that direction are physics engines used in computer games, but there is a difference between a physics engine and an MPC controller.
What robotics programmer have to implement is a dedicated forward model which works much faster than a classical physics engine. It's equal to program a simulator which can answer “what-if” questions. For example, “What will happen if the crane is moving to the left?” On the first look, it's obvious what will happen, but the problem is, that the information isn't available for the computer. Creating a software module which can answer “what-if” question very fast is the fundamental step in realizing model predictive control.
December 10, 2019
System identification and automatic game playing
Most examples of Narrow Artificial Intelligence is about game playing. The domain is given in advance, and the AI software has to bring the model into the goal state. Typical examples are the TicTacToe game, the micromouse challenge or a line following robot. All these problems have in common, that the domain was defined precisely and the AI has to solve the game.
In case of the micromouse challenge the problem is provided by the maze, the robot hardware and the rule that the robot has to travel through the maze. What the engineers are doing is to solve this challenge. They are using pathplanner, motion planner and vision algorithm which will allow the robot to drive autonomously through the maze.
The surprising fact is, that all of these robots are useless for practical applications. It's not possible to utilize the micromouse robot for a different kind of task. This is a tragedy in case of very complex robots. The paradox situation is, that on the one hand the robotic system is highly developed but from a practical point of view, the robot can do nothing.
To overcome this bottleneck there is need to introduce a prestep before the robotic software is programmed. This prestep is called system identification. System identification tries to describe the domain. That means, the rules of the micromouse challenge are not given in advance, but the engineers has to describe first what the task for the robot is.
Or let me give a more easier example. A normal AI project is about programming a software which can solve TicTacToe. The more elaborated AI project is, if it's unclear which kind of game should be played by the software. The rules are not provided in advance. This is the case for real robotic applications. Especially if the aim is to replace human work with robots. The problem is, that it's unclear what exactly a human worker is doing. He is trying to solve a problem, but the domain is not described in advance.
System identification is equal to a forward model which is equal to a simulation and this is equal to a physics engine. A physics engine is not the AI itself, but it's the environment in which an AI Controller gets activated. A physics engine is sometimes introduced in the Artificial Intelligence community as a reward structure, or inverse reinforcement learning. The idea is, that before a game can be solved there is need to figure out what the game is about. This prestep before a solver can bring the system into a goal step is more complicated to solve than normal AI tasks. In most AI domains there is no need for this step because it's trivial to do the model checking. A TicTacToe simulator provides the accurate simulation for the real tic tac toe game, all the rules are known in advance.
This kind of situation is missing for robotics application. The typical robot project works with a missing domain model. That means, it's unclear if the action of the robot produced a positive or a negative reward.
Model predictive control
The rules of TicTacToe are well known: two players have to place pieces on the board and the problem is which is the best move. But is this really the problem? No it's not because the optimal move can be determined by a game-tree-search. The more interesting question is what is the TicTacToe game about. If a player puts a piece on the board, he brings the game into a new state. The action has an effect and the amout of possible actions for the next player is smaller. The game engine formalizes the rules. It determines under which condition somebody has won and what allowed actions are.
The interesting problem in TicTacToe is not solving the game itself, but it's how to transfer the game rules into the game engine. If this topic is unanswered it's not possible to automate the game. In case of the TicTacToe game the game engine is trivial to program. In most cases it can be programmed with less than 100 lines of code. In other domains like micromouse, or robotic grasping domains the game rules are more complicated. In most projects, the AI programmer ignore the task for formalizing the game rules. They assume that programming an AI is equal to solve a domain.
An often cited example for model predictive control is steering of a vehicle. The project contains of two parts: system identification and solving the model. In the system identification task, it is defined what will happen if the car steers to the left. This allows to predict future game states. It's equal to invent a game. The game rules are about a car which is able to steer to the left and to the right. Solving this game is done in the second task called “solver”. Here is the question which action is needed to next to win the game. Solving a game makes only sense, if the game rules are available. That means, a random action can be send to the forward simulation and the model provides the What-if-feedback back to the controller.
It's important to know, that a forward model can be controlled by a human operator. A forward model means only that the game rules are formalized in a simulation and it's possible to play with this simulation. Playing means, that the human operator can try out different actions and observe the reaction of the system. Because of this reason, the system identification step is often ignored by the AI community. It has nothing to do with automatic game playing itself, but it's the prestep towards this goal.
In case of the micromouse challenge the problem is provided by the maze, the robot hardware and the rule that the robot has to travel through the maze. What the engineers are doing is to solve this challenge. They are using pathplanner, motion planner and vision algorithm which will allow the robot to drive autonomously through the maze.
The surprising fact is, that all of these robots are useless for practical applications. It's not possible to utilize the micromouse robot for a different kind of task. This is a tragedy in case of very complex robots. The paradox situation is, that on the one hand the robotic system is highly developed but from a practical point of view, the robot can do nothing.
To overcome this bottleneck there is need to introduce a prestep before the robotic software is programmed. This prestep is called system identification. System identification tries to describe the domain. That means, the rules of the micromouse challenge are not given in advance, but the engineers has to describe first what the task for the robot is.
Or let me give a more easier example. A normal AI project is about programming a software which can solve TicTacToe. The more elaborated AI project is, if it's unclear which kind of game should be played by the software. The rules are not provided in advance. This is the case for real robotic applications. Especially if the aim is to replace human work with robots. The problem is, that it's unclear what exactly a human worker is doing. He is trying to solve a problem, but the domain is not described in advance.
System identification is equal to a forward model which is equal to a simulation and this is equal to a physics engine. A physics engine is not the AI itself, but it's the environment in which an AI Controller gets activated. A physics engine is sometimes introduced in the Artificial Intelligence community as a reward structure, or inverse reinforcement learning. The idea is, that before a game can be solved there is need to figure out what the game is about. This prestep before a solver can bring the system into a goal step is more complicated to solve than normal AI tasks. In most AI domains there is no need for this step because it's trivial to do the model checking. A TicTacToe simulator provides the accurate simulation for the real tic tac toe game, all the rules are known in advance.
This kind of situation is missing for robotics application. The typical robot project works with a missing domain model. That means, it's unclear if the action of the robot produced a positive or a negative reward.
Model predictive control
The rules of TicTacToe are well known: two players have to place pieces on the board and the problem is which is the best move. But is this really the problem? No it's not because the optimal move can be determined by a game-tree-search. The more interesting question is what is the TicTacToe game about. If a player puts a piece on the board, he brings the game into a new state. The action has an effect and the amout of possible actions for the next player is smaller. The game engine formalizes the rules. It determines under which condition somebody has won and what allowed actions are.
The interesting problem in TicTacToe is not solving the game itself, but it's how to transfer the game rules into the game engine. If this topic is unanswered it's not possible to automate the game. In case of the TicTacToe game the game engine is trivial to program. In most cases it can be programmed with less than 100 lines of code. In other domains like micromouse, or robotic grasping domains the game rules are more complicated. In most projects, the AI programmer ignore the task for formalizing the game rules. They assume that programming an AI is equal to solve a domain.
An often cited example for model predictive control is steering of a vehicle. The project contains of two parts: system identification and solving the model. In the system identification task, it is defined what will happen if the car steers to the left. This allows to predict future game states. It's equal to invent a game. The game rules are about a car which is able to steer to the left and to the right. Solving this game is done in the second task called “solver”. Here is the question which action is needed to next to win the game. Solving a game makes only sense, if the game rules are available. That means, a random action can be send to the forward simulation and the model provides the What-if-feedback back to the controller.
It's important to know, that a forward model can be controlled by a human operator. A forward model means only that the game rules are formalized in a simulation and it's possible to play with this simulation. Playing means, that the human operator can try out different actions and observe the reaction of the system. Because of this reason, the system identification step is often ignored by the AI community. It has nothing to do with automatic game playing itself, but it's the prestep towards this goal.
Subscribe to:
Posts (Atom)