What is state estimation?
In robotics, state refers to the condition of the robot. The most common conditions we are concerned with are location, velocity, and orientation, but there are many other conditions that could be included in the description of a robot’s state -- temperature, remaining battery life and component faults, to name a few. State estimation refers to the process of inferring these quantities algorithmically from mathematical models based on how the robot evolves over time and information gained from the robot's sensors.
At its core, state estimation seeks to answer the following: Where is the robot? How is it moving? And how is it oriented?
Why does state estimation matter?
At Shield AI, we design artificially intelligent systems to help protect service members and civilians by providing critically important situational awareness. Our robots achieve this mission by autonomously exploring inside structures collecting, processing, and transmitting data to users in real-time.
State estimation derives its importance from the autonomous nature of our robots. Reliable state estimation is a fundamental building block of autonomy. In order to operate autonomously, the robot’s exploration algorithm must be able to decide where it wants to go next. The robot’s planner must be able to plan a path to that location from its current location and the robot’s controller must be able to reliably follow that path. Exploration, path planning and controls all depend on the robot’s ability to reliably establish where it is, how it is moving, and how it is oriented.
How does a robot know where it is and how does it apply that information?
To understand how this works, we first need to review the concept of reference frames. A reference frame consists of a fixed location and fixed directions, similar to the x-y-z coordinates on a graph. When we specify a location, we specify its displacement from the fixed location in each of the fixed directions. For example, we might say the robot is 10 meters East and 5 meters North [10E, 5N] of its starting location and that it wants to go to a location 10 meters East and 10 meters North [10E,10N] of its starting location. In this case, the reference frame’s fixed location is the robot’s starting location and the fixed directions are East and North.
The first block that builds upon state estimation is the controller. When our quadcopter is given a direction to travel and a flight speed, the controller must translate this information into the rotational speed for each of its four motors. Rotating the four motors at different rates results in the robot spinning, tilting, and accelerating differently. In order to do this, the robot must be able to estimate its orientation. If a robot happened to be facing North and has planned to travel North at a speed of 2 meters/second, the robot must decide upon a rotational speed for each of its motors which would result in the robot tilting forward and accelerating until it reaches 2 meters/second.
Next, we consider path planning, which is how the robot determines what trajectory it should follow in order to reach a desired location. In the above example, the robot travelled North at 2 meters/second. Given the example of [10E, 5N] as a current location and [10E, 10N] as the next desired location, traveling North seems like an appropriate action. However, traveling North at 2 meters/second would be the wrong action to travel from [10E,15N] to [10E,10N]. It follows that if the robot doesn't know which of these locations it currently occupies, it cannot know the correct direction to go. Therefore, the robot’s ability to plan paths depends critically on state estimation.
State estimation also plays a second critical role in path planning. An important part of path planning is for the robot to choose a path which does not collide with anything in the environment. In order to achieve this unobstructed travel, the robot requires a map to tell it where the objects are in its environment. At Shield AI, our robots fly into previously unseen structures. This means the robot has to build a map of its environment while it is exploring. In order to do this, we have equipped our robots with sensors and intelligence to detect objects. State estimation allows the robot to establish the object’s location relative to the robot’s own location. With this information, the robot can start building a map. In order to build a coherent map, the robot must always know where it is located and how it is oriented with respect to a fixed reference frame. Continuing our earlier example, imagine the robot’s sensors detect an object two meters away, directly in front of it. If we know that the robot’s location is [10E,5N] and it is facing North, then we know the object is at the location [10E,7N] on the map. When the path planner considers the problem of getting from [10E, 5N] to [10E, 10N] it knows that it must choose a trajectory which avoids the object located at [10E,7N]. The map is particularly important when the path planner is given a destination outside of the current view of the sensors; in this case, the map is the only way the planner can be sure its chosen trajectory has no collisions.
Another task that the autonomous robot must complete is to decide where to go next after it reaches its destination. This task also inherits its dependency on state estimation through the map. Because Shield AI’s robots thoroughly explore the entirety of the interior of a structure, our robot determines where to travel next by choosing some part of the map that it has not previously visited.
Read the second part of our series on state estimation: The Challenges of State Estimation.