When deploying robots in an industrial setting, one of the primary goals is performance. In an industrial robot workcell, performance is often measured as cycle time: the time required to complete a set of tasks. Typical tasks include painting, welding, and inspecting. Regardless of the tasks, the goal is to complete them as fast as possible, so that the workcell can begin work on the next set of tasks. A long cycle time for a given cell can cause that cell to become the bottleneck on an assembly line.
One way to try to improve performance is to use multiple robots in the same workcell. In a multi-robot workcell, the tasks can be divvied up among the robots, with the expectation that the robots can perform their work concurrently and thus shorten the cycle time. In theory, more robots means more performance but, as is also true of adding cooks to a kitchen, results in practice do not always meet expectations.
The Challenge of Multi-Robot Workcell Performance
Recently, a customer approached us after adding a second robot to a workcell, saying that they achieved only a meager 10 percent reduction in cycle time. While one might not expect to get perfect parallelism (going from 1 robot to N robots and achieving a cycle time that is 1/N of what it was before), we want to maximize the benefit of adding robots to a workcell.
Why is it difficult to achieve better performance in multi-robot workcells? Imagine you are designing a workcell with four robots and 50 tasks that need to be completed per cycle. If we consider a design to be both an allocation of tasks to robots and the sequencing of tasks for each robot, there are a vast number of possible designs to consider.
First, there are a huge number of possible assignments of tasks to robots. Perhaps the possibilities are limited a bit because some robots cannot perform some tasks, either because they cannot reach them or because the robots are heterogeneous and certain types can perform only a subset of the tasks. Nevertheless, the number of possible assignments is typically extremely large, in this example 450 (which is a bit more than 1030). Then, once those assignments have been made, there is a huge number of different orders in which the robots can perform their tasks. For our example, there are at least another 1034 possible combinations (12!4 assuming tasks are distributed equally — it gets worse if they are not-evenly distributed), so we end up with over 1064 possible designs to consider. Even if we could test one design per nanosecond, that would still take longer than the age of the universe. The number of designs is clearly far larger than can be exhaustively searched.
What distinguishes the many possible designs? In a good design, every robot spends approximately the same amount of time per cycle; we want to avoid having some robots idle while others are still working. Similarly, in a good design, every robot is able to move without spending much time either waiting for other robots to move out of its way or taking a non-optimal path so as to avoid other robots. The goal of a design is to enable high-performance choreography of the robots.
In such a vast design space, there can be large differences in performance between good designs and poor designs. Even ignoring obviously bad designs, for example, allocating almost all tasks to one robot or sequencing tasks such that the total robot motion is greatest — there is still a significant performance discrepancy between seemingly reasonable designs.
Our team has developed Optimization-as-a-Service (OaaS), which uses a proprietary algorithm to find high-performing design options that would otherwise take months to be discovered by a team of engineers. We have obtained speedups of 5-20 percent using our OaaS (discussed later), compared to designs that were laboriously developed by experienced engineers. This result highlights that design is both very difficult and very important.
How Multi-Robot Workcell Design is Done Today
How can engineers possibly choose a design from such a large design space? Fundamentally, the only way to search a huge space of any kind is to take a sample from it (pick a design), evaluate that design (assess its performance), and, based on the evaluation of that sample and any previously taken samples, decide where to sample next. This design loop continues until a sufficiently performant design is obtained, or until it is determined that more effort is unlikely to result in a substantially better design.
Choosing Initial Design Sample: Choosing the initial design is challenging, given the enormous number of possible options. Where to start? Experienced robotic engineers may have some intuition for what heuristics to use to narrow the space a bit. For example, we might expect every robot to be allocated approximately the same number of tasks. However, even this intuitive heuristic fails to account for the fact that each task — as well as moving to that task — can take a different amount of time. Other heuristics might involve assigning tasks to robots that are closer to them, as well as sequencing tasks to minimize total robot motion.
Evaluating Design Samples: To evaluate a design, one must determine its performance. And, to determine its performance, one must create a motion plan for the robots. Motion planning is the process of computing how to get the robots from task to task without hitting any obstacles or other robots. Motion planning is a historically difficult computational problem, even for a single robot, and choreographing multiple robots is extremely difficult. In fact, motion planning takes so much effort that it is the primary reason why multi-robot workcell designs tend not to achieve their performance potentials.
Because the choreography is so difficult, engineers frequently use “interference zones” to simplify the task. If two or more robots can potentially occupy a part of the workcell, that volume is considered an interference zone and requires a robot to obtain a lock before entering it, such that only one robot can be in a given interference zone at a time. While interference zones make motion planning easier, they sacrifice considerable performance, because it is frequently possible that multiple robots could have operated in an interference zone without collision.
In addition, because finding a good motion plan takes so long, it limits how many samples can be evaluated in a practical amount of time. With slow motion planning, engineers can typically only consider a handful of designs. Evaluating fewer designs means that there is less chance of finding an excellent design.
Choosing Subsequent Design Samples: Based on the evaluation of the most recent sample, as well as the evaluation of any previous samples, engineers must choose the next sample. Many algorithms are possible here. Typically, these algorithms trade off the desire to sample near to a previous sample that is considered good, versus the desire to sample far away so as to avoid getting trapped in a local optimum.
Optimizing Multi-Robot Workcell Productivity
OaaS works to improve overall productivity by first analyzing a manufacturer’s existing digital twin, identifying bottleneck areas. Our engineers use the OaaS software to recommend improvements based on desired parameters like cycle time, but could also consider issues like floor space and power consumption. These recommendations are fundamentally based on fast and efficient searching of the huge space of possible designs.
Because motion planning has historically been the primary limiter in the search for high-performing multi-robot workcell designs, our approach has leveraged new technology for high-speed motion planning. Realtime Robotics launched its RapidPlan motion planning software, which uses a combination of more efficient algorithms and data structures to achieve motion planning latencies on the order of a millisecond for single robot and multiple robots. This orders-of-magnitude speedup in motion planning latency is transformative in that it enables a far more effective multi-robot workcell design process.
Similar to any scheme for searching a huge space, the idea is to follow the same design loop: sample a design, evaluate the design, choose the next design, etc. However, because evaluation can now be done so quickly, hundreds of thousands, or even millions of possible samples can be evaluated in a reasonable amount of time (e.g., less than a day).
Regardless of the sampling methodology, the ability to consider many more designs greatly increases the chance of finding the higher performing designs in the design space. The optimization algorithm can take more samples near good designs, while also taking more samples that are far enough away to avoid local optima. It can also start from multiple initial samples and run the searches in parallel.
OaaS can deliver better results than the traditional alternative of adding more robots to solve the problem. Adding robots, which is akin to adding another lane to a highway to improve traffic, incurs additional costs beyond even the costs of the extra robots, including greater programming complexity.
The potential for squeezing out additional cycle time from already optimized or new cells is driving an increasing number of automotive manufacturers to OaaS. A leading automotive manufacturer recently utilized OaaS in a proof-of-concept project for electric vehicle manufacturing. The company’s simulation file was analyzed without stopping or interfering with ongoing production, and the resulting recommendations helped improve cycle time by 15 percent. Improvements were ultimately incorporated without pausing production.
Multi-robot workcell design is not a completely solved problem. We find higher performing designs with high-speed motion planning, but opportunity remains. Even faster motion planning would enable more thorough exploration of the design space, and more clever sampling algorithms would enable the sampled designs to better cover the space. With better searching of the design space, we can find designs with even greater performance as well as less power consumption and smaller footprints. We expect further innovation in this space given how important this problem is to users of industrial robots.
This article was written by Dan Sorin, Founder and Chief Architect at Realtime Robotics (Boston, MA). He is also a Professor of Electrical and Computer Engineering and of Computer Science at Duke University. For more information, visit here .