Blog | 16-09-2020

Mobile robot fleet planning and control possibilities

written by: Tim de Jager - Robotics Engineer

When deploying a fleet of mobile robots, there are choices to be made on how to implement the planning and control of the fleet. While centralized planning offers the highest level of predictability and control, there can be a drawback in flexibility and reactivity. On the other hand, employing decentralized planning that runs on the robots themselves is highly flexible and the planning for the individual robot is possibly less complex. The robots can quickly react on changes in the environment. However, the behavior of the fleet is less predictable, and it can lead to emerging behavior. This can be problematic due to safety regulations. In the following blog, we will discuss the robot fleet planning and control possibilities in more detail.

In recent years, more and more robots are deployed in the industry. Previously, robots have mainly been used in a static manner, i.e. performing a singular repetitive task over and over again with high precision and speed. When multiple robots are employed in such a setup, each robot performs a dedicated task with no direct interaction with the other robots. Therefore, no or little additional planning is necessary.

Mobile robots in a team

While this approach is suitable for many large-scale production environments, it cannot be applied in all environments. For instance, in a logistics fulfillment process, it is often required that the robots are mobile as the tasks are spatially distributed. An example of such a spatially distributed task is retrieving ordered items from different locations in a warehouse. To be able to retrieve these orders efficiently, many robots need to work together in a team.

This creates the challenge of control, planning and cooperation within such a robot fleet. All ordered items need to be picked from a specific location in the warehouse and transported to a different location. To reach the highest efficiency, the robots should not interfere with each other while navigation through the tight corridors in the warehouse and they should pick items that are located close to each other.

Different robot planning approaches

What is described above is a very difficult planning problem for which different approaches exist. These can generally be categorized in centralized and decentralized planning systems. :

1. In a centralized system, planning is calculated for the complete fleet beforehand and then communicated to the robots. The fleet is not able to adapt the plan. If the plan changes during the execution, the fleet must be able to communicate to the central system to ensure that it is updated accordingly.
2. In a decentralized planning system, each robot makes its own decisions. In these systems, the plan can be adapted more easily during execution. The robot can decide on its own without the need to communicate everything.

Centralized robot planning

In more detail, in centralized planning there is a single entity which knows about all tasks and robots in the team. The centralized planner assigns tasks to the robots and decides which routes the robots must navigate. As all information is available, an optimal plan can be calculated beforehand.

While in the case of a handful robots, a good assignment can usually be calculated in a straightforward manner, a problem with a centralized system arises when more and more robots are added to the system. The number of possibilities rises exponentially with every additional robot. Consequently, planning time increases and it might become infeasible to provide an optimal plan in time or to quickly response to changes.

A solution to simplify the problem is partitioning. Usually there is a physical limit of how many robots are sensible in a certain area of a warehouse. Therefore, a partition of regions can be defined, and, in each region, a separate independent fleet is deployed. Another advantage of the centralized approach is the high predictability and the high level of control. However, in complex environments execution will not always be as planned, for instance due to errors or changes in the environment during the execution of the plans, such as humans or even other robot fleets performing unrelated tasks.

Decentralized robot planning

On the other hand, there is decentralized planning where each robot makes its own decisions. It needs to accumulate all necessary information and calculate a plan based on this information. One possibility is that there is a ‘broker’ that has the tasks available, and the robots ‘bid’ on the tasks they want to perform and choose the navigation routes themselves. However, the design of such ‘bidding’ systems can be very difficult [3]. Other solutions are that the robots broadcast their current plan and all robots plan accordingly [1].

While the robots may not have all information available, this is in many cases not necessary. The robots are mainly interested in their own actions. This results in a much less complex planning problem. Additionally, it allows the robots to plan online as soon as the environment changes. This results in less predictable ‘emerging’ behavior, but if a robot in the fleet fails or another robot is added to the system, the rest of the fleet will automatically adjust for it.

Hybrid solutions and examples

Of course, hybrid solutions are a possibility as well. For instance, some parts of the planning could be centralized while others are performed decentralized. As an example, the task each robot must perform could be calculated by a centralized planning entity. However, the robot has to figure out itself in which order to perform the tasks and how to navigate through the warehouse.

One of the first examples of a large-scale of multiple robotics deployments was done by KIVA [2] (which is now Amazon Robotics). They employ a centralized approach which is then merely executed on the robots. This is possible as the whole warehouse was built according to this specification. Furthermore, Fetch [4] employs a more hybrid solution with more intelligence on the robots. The robots find the paths themselves and communicate their status to the fleet manager.

Understand the environment and tasks

To summarize, there is no ‘one-size fits all’ solution, as the decision depends on the environment and the nature of the tasks. For instance, if the tasks do no change rapidly over time, a centralized planning entity can be employed to ensure there is predictability in the execution. In many cases, the deployed number of robots is not yet a problem for a centralized solution to work. Likewise, as mentioned before, there is usually a limit of how many robots can be deployed in a warehouse. In other cases, partitioning can be applied to ensure to keep the planning problem tractable.

However, when the environment is very unpredictable and the robots need to react quickly, more control needs to be implemented on the robots. These systems are more difficult to design, because the interaction between the robots will lead to (often not wished) unpredictable behavior. Thus, only by understanding the environment and by using models and simulations, an educated decision can be made to decide which of the solutions should be employed.