{"body":"

Developing a path planner for mobile robots in complex indoor environments is a challenging project. In Ocado’s 10X team we have been working to design a path planner that could be deployed on any robot navigating in an indoor environment, such as an autonomous trolley on a warehouse floor. Something like this could obviously have major implications for any company that wants to automate its machine handling equipment in its warehouses, for example, or even potentially in the autonomous vehicle industry. This makes this a really important area of research.

A path planner does exactly what it says on the tin: it plans paths from some start position to a goal through a given environment. The way this environment is represented can vary from robot to robot and task to task, but fundamentally the robot must be able to query whether a given point is free (it is not in an obstacle) and whether a line is free (it does not intersect an obstacle).

As such, a fundamental part of autonomous robotics, motion planning is a well-trodden path (sorry!) and so it was important not to simply reinvent the wheel. After researching the field, we found two main classes of planners that were relevant to what we wanted to do: sampling planners and a newer technique using diffusion maps.

Sampling planners find paths by incrementally growing a graph of the environment, where each node represents a free state in the environment and each edge is a free path between two states.

The following algorithm is used to grow the graph:

Randomly sample a free state (xrand, red) in the environment.
Find the state’s nearest neighbour (xnear, green).
If the path between the new state and the nearest neighbour is free, add the new state to the graph.

Whilst different sampling planners may differ in how they initialise the graph and can do different things to grow the graph towards xrand, they all rely heavily on euclidean nearest-neighbour queries. These types of planners work very well in open spaces but struggle in narrow passageways because euclidean distance is a poor barometer for cost-to-go between points. Take two points on opposite sides of a wall: while close in euclidean distance, actual cost-to-go is much larger as you must go around the wall. As indoor spaces are littered with narrow passageways, these planners were unsuitable for what was needed.

Diffusion maps can be used for a better approximation of cost-to-go than euclidean distance. Diffusion maps are a non-linear dimensionality reduction technique, borrowed from machine learning. A grid map of the environment is created and matrix operations are then used to map each point in the grid space into a new k-dimensional diffusion space, for some small integer k (k=10 is sufficient to capture the underlying structure of the environment). In the diffusion space, the distance between each pair of points is a much better approximation of cost-to-go than distance in the original space.

Once you have the diffusion map, it can be used to find paths in several ways. A simple gradient descent can be used, starting at the robot’s current position and at each stage choosing the neighbouring node that minimises the diffusion distance to the goal. Alternatively, diffusion distance can be used as a heuristic to guide an A* grid search. However, in practice both of these methods fail in complex environments: the first relies too heavily on the approximate diffusion map and finds sub-optimal paths, whereas the second is simply too slow.

To combat this, we devised an algorithm that combined both planners in the hope this would alleviate the issues found in each. When growing the tree, xnear can be chosen as the point closest to xrand in diffusion space instead of the point closest in euclidean space. As diffusion distance is a good approximation of cost-to-go, this ensures that xnear is easily reachable from xrand, instead of being separated by a wall. This change allows trees to be grown rapidly through narrow environments - shown clearly in the image below. Without the diffusion-based nearest neighbours, the tree fails to explore the environment fully. After the same number of iterations, the diffusion-based planner has explored the entire environment.

This is some really exciting work which lends itself well to mobile robots operating in one fixed, complicated space, such as the warehouse, or food-delivery bot on a campus. Keep your eyes peeled for an academic paper on this topic coming soon!

","presentation":{"classes":"","theme":"theme-default","columns":""}}

Going Mobile: Path Planning for Robots