What Is Autonomous Navigation? | Autonomous Navigation, Part 1

The goal of this whole video series is to give you a basic understanding of the autonomous navigation problem, what some of the terms are, some of the needed algorithms, and what makes this problem difficult in certain environments. So, that’s what we’ll cover over a few videos, but in this first one, I want to set the stage a bit and just introduce the idea of autonomous navigation. I think it’s pretty interesting, so I hope you stick around for it. I’m Brian, and welcome to a MATLAB Tech Talk.

Navigation is the ability to determine your location within an environment and to be able to figure out a path that will take you from your current location to some goal. Navigating in the wilderness might require say GPS to determine where you are, and a map to plan the best path to get around mountains and lakes to reach your camp site or whatever your goal is.

Now, autonomous navigation, is doing exactly this, but without a human in the loop. Broadly speaking, it’s how we get a vehicle to determine its location using a set of sensors and to move on its own through an environment to reach a desired goal. When I say vehicle, I mean any kind of mobile machine. It could be a car traveling down a road, or a UAV making its way back to the airport, or a spacecraft journeying across the solar system, or a submersible exploring the depths of the ocean, or some other mobile robot. In this way, we’ve given the vehicle autonomy. The ability to make decisions and act on its own.

But, there are different levels of autonomy and they range from a vehicle that is simply operated by a human from a remote location but it has some simple algorithms on board that will take over and autonomously keep it from running off a cliff or something, up to a fully autonomous vehicle with no human interaction at all.

For this series, we’re mostly going to focus on what it takes to make a fully autonomous vehicle. This is because there’s a lot more involved in it, and we can apply that knowledge to other vehicles that fall elsewhere on this autonomy spectrum.

But even with fully autonomous navigation, we can further divide this into two different approaches; a heuristic approach where autonomy is accomplished through a set of practical rules or behaviors. It doesn’t guarantee an optimal result, but is good enough to achieve some immediate goal. The benefit of heuristics is that you don’t need complete information about the environment to accomplish autonomy. And then on the other side there is an optimal approach, which typically requires more knowledge of the environment and the plan and the resulting actions come from a maximization or minimization of an objective function. Let’s go a little bit more into each of these.

An example of a heuristic approach is a maze solving vehicle where the simple rules might be to drive forward and keep the wall on the left. So it turns left when the wall turns left, makes a u-turn at the end of a wall, and it turns right at a corner. This type of autonomous vehicle will proceed to wander up and down the hallways until it happens to reach the goal.  In this way, the vehicle doesn’t have to maintain a map of the maze, or even know that it’s in a maze, in order to find the end. It doesn’t follow an optimal path, but it works. At least, as long as it doesn’t get itself stuck in a loop.

Other types of heuristic-based autonomy include things like the simplest of robotic vacuums, where when it approaches an obstacle like a wall, it rotates to a new random angle and just keeps going.

As time increases, the chance that the entire floor is covered approaches 100 percent and so in the end, the goal of having a clean floor is met, even if the vehicle doesn’t take the optimal path to achieve it.

So, this brings us to the second type of fully autonomous vehicles; ones that are solving an optimization problem. In these systems, the vehicle builds a model of the environment, or updates a model that is was given to it, and then figures out an optimal path to reach the goal.

There are a lot of great practical examples of autonomous vehicles where optimal-based strategies produce a much better result than their heuristic-based counterparts. Possibly most famously at the moment is autonomous driving where a vehicle has to navigate to a destination through dynamic and chaotic streets. And relying on simple behaviors like drive forward and keep the curb to your right is probably not the best approach to safely and quickly get to where you want to go. It makes more sense to give the vehicle the ability to model the dynamic environment, even if that model is imperfect, and then use it to determine an optimal solution.

Now it’s not usually the case where a solution is either 100% heuristic or 100% optimal. Often, we can use both approaches to achieve a larger goal. For example, with an autonomous car, at a high level it can plan an optimal route through a city taking into account the current traffic. However, at a local level when it approaches a slower car, it has to make a decision to either slow down or to change lanes and pass. If it was going to make this decision optimally, it would have to have knowledge beyond the front car to determine if changing lanes is the best solution which could be difficult to obtain, So possibly a better solution is to have a heuristic behavior that says something like, if it is safe to do so, always attempt to pass slower cars. Once that decision is made, an optimal path into the adjacent lane can be created. In this way, these two approaches can complement each other depending on the situation.

And autonomous cars aren’t the only examples of systems that make use of these two approaches. There are other ground vehicles, like they have in Amazon warehouses that have to quickly maneuver to a given storage area to move packages around while not running into other mobile vehicles and stationary shelves. Or vehicles that search within disaster areas that have to navigate unknown and hazardous terrain. There are space missions like OSIRIS-REX which has to navigate around the previously unvisited asteroid Bennu and prepare for a precisely located touch and go to collect a sample to return to Earth. There are robotic arms and manipulators that navigate within their local space to pick things up and move them to new locations. There are UAV’s and drones that survey areas, and many, many more applications.

But autonomous navigation isn’t necessarily easy despite how common it’s becoming in the world, and most of what makes it difficult is that the vehicle has to navigate through an environment that isn’t perfectly known. And so in order to create a plan it has to build up a model of the environment over time. And the environment is constantly changing and so the model has to be constantly updated, and there are obstacles that move around and aren’t necessarily obvious, so sensing and recognizing them is difficult as well. The more uncertainty there is in the environment and the environment model, the harder the navigation problem becomes.

For example, building an autonomous spacecraft that is orbiting the Earth is typically a simpler navigation problem than an autonomous aircraft. Space is a more predictable environment than air because we have less uncertainty with the forces that act on the vehicle and we have more certainty in the tracks that other nearby objects are on. Therefore, we can have more confidence in a plan and have a better expectation that the spacecraft will autonomously be able to follow that plan. With aircraft, we have to deal with unknown turbulence, flocks of birds flying around, and other human controlled planes, and landing, and taxiing around an airport.

But an autonomous aircraft is itself typically a simpler problem than an autonomous car for the same reasons. There is much more uncertainty driving around in a city than there is flying around in relatively open air.

So, the thing I want to stress here is that what makes these vehicles impressive is not the fact that they can move on their own. I mean, it’s pretty trivial to get a car to drive forward by itself. You just need an actuator that compresses the gas pedal. The car will take off and drive forward. The difficult part is getting it to navigate autonomously within an uncertain and changing environment. For the car, it’s to get to the destination efficiently, and follow local traffic laws, to avoid potholes, and balls rolling into the street, and to reroute around construction, and to avoid other cars driven by unpredictable humans, and to do all of this in the snow and the rain and so on. Not an easy feat.

So, to understand how we get vehicles to do that and other incredible autonomous tasks, we need to revisit the capabilities of autonomous systems that we covered in the first video of the sensor fusion and tracking series. If you haven’t seen it and want a longer description, I’ve left a link below, but here’s a quick recap.

Autonomous systems need to interact with the physical world and part of interaction is to collect data about the environment using sensors. This sensor data has to be interpreted into something that is more useful than just measured quantities. These are things like understanding where other objects or obstacles are, building a model, or a map of the environment, and understanding the state of the autonomous vehicle itself, what its location is and orientation.

With this information, the vehicle has everything it needs to plan a path from the current location to the goal. Avoiding obstacles and other objects along the way. The last step is to act on that plan. To drive the motors and actuators in such a way that the vehicle follows the path. The actuators impact the physical world and the whole loop continues.

We sense the environment. We understand where we are in relation to landmarks in the environment. We perceive and track dynamics objects. We replan given this new set of information. We control the vehicle to follow that plan. And so on until we get to the goal.

In the sensor fusion video, we talked about how sensor fusion and tracking straddled the sense and perceive steps, and while sensor fusion and tracking are absolutely necessary parts of autonomous navigation, in this series we’re going to focus our attention on other algorithms within the perceive step and on the plan step. And we’re going to answer questions like what does it mean to generate a model of the environment? How does a vehicle know where it is within that model? How does a vehicle track other large objects and obstacles? What are some of the ways path planning is accomplished? And how do you know the system is going to work in the end?

So, that’s what you have to look forward to. In the next video, we’re going to explore the SLAM problem. That is, how we approach simultaneously determining the location of the vehicle and building a map of the environment. So if you don’t want to miss that or any other future Tech Talk videos don’t forget to subscribe to this channel. And you want to check out my channel, control system lectures, I cover more control theory topics there as well. Thanks watching, and I’ll see you next time.