How the AMR Dispatching System works

This article mainly introduces the related content of the distribution and execution of intelligent robot tasks in the warehouse. Task distribution, as the name implies, for a batch of tasks currently to be executed (common tasks in the warehouse scene include handling tasks and parking tasks), they are allocated available AMR (Autonomous Mobile Robots) resources, that is, the task requirements in different scenes in the warehouse Match with the available handling robot resources. AMR resources are capacity resources for performing tasks, so task distribution is also called capacity allocation.

A simple example is as follows:

A good task distribution system can fully mobilize robot resources and achieve global or local optimization in terms of running time and distance, so as to achieve the highest efficiency. This article discusses the two common tasks common to existing robots, namely handling tasks and parking tasks, and discusses the task allocation model and execution strategy in handling tasks and the selection of parking points in parking tasks.

Background introduction

With the continuous development of robot technology and the continuous improvement of enterprise digitization and automation, more and more robots have gradually entered the operation scenes of various links in the storage and production-related fields.

Although the robot has various forms and different operating links or operating modes, the basic operations performed or the basic functions achieved have the same thing, that is, complete the handling function and choose a suitable place to park after the task is completed and wait for the follow-up task. Robot handling tasks can be abstracted as moving objects to be transported (such as pallets, shelves, bins, and commodities) from the starting point (such as storage locations, elevator connection points, packing stations, rack picking points, etc.) to the destination point ( For example, the picking workstation, the sorting Chute port, and the review packing workstation, etc.), the parking task is that the robot selects a suitable parking spot to wait after completing the task so that it can quickly respond to subsequent tasks and improve work efficiency.

Below we will discuss these two basic tasks of the robot separately.

Handling task distribution

Handling task distribution-handling task

Currently, in the fields of warehousing and manufacturing, one of the core functions of ground robots is the handling of objects or containers. The elements of a handling task mainly include: robot, handling target, starting point, transfer point, destination point, and driving route, among which:

1. Robot: the concrete execution carrier of the handling task
2. Transport target: the entity that the robot will transport, and its specific manifestation is not unique in different scenarios. For example, in the goods-to-person system, the transportation target is mainly multi-layer shelves or pallets; in the sorting scenario, it is mainly the packages to be distributed; and in the picking support system, it is the goods that are manually picked.
3. Starting point: the point where the robot starts to perform the task, such as a parking point or a workstation, etc.
4. Transfer point: a key node that must be passed under the handling task, rather than a general node on the driving path. The transit points here are often business-related nodes. For example, the shelf storage point under the goods-to-human robot system is the storage point. The robot starts from the initial point and goes to the storage point to pick up the shelf and then send it to the workstation; in the picking support robot system, it is a series of picking points. Need to stop and pick or move goods picked manually
5. Destination point: the place where the transport target needs to be reached, such as a workstation or a sorting bay, etc.
6. Driving path: the robot walking path planned based on factors such as road network connectivity and road congestion

Here we believe that each task includes a robot and a corresponding transportation target. Starting from a starting point, the robot can pass through one or more transit points to reach one or more destination points. For warehousing, putting on shelves, and returning to warehouse tasks, shelves and storage positions are selected in the inventory system. After processing by the inventory system and the order batch processing system, the handling target, transfer point, and destination point in the handling task have been determined.

System level

The task distribution system for handling tasks is divided into two layers, namely the upper-layer business constraint definition and the lower-layer core matching algorithm.

Handling task distribution-business constraints

Business constraints involve a large number of different scenarios and need to meet different business requirements, which is relatively complex.

For example, when performing task distribution, the tasks to be done may be of different types. Some tasks are more urgent and have higher priority and need to be done first; some tasks have higher waiting costs, so they need to reserve a certain share for their time. The capacity of this type of task is guaranteed to be immediately allocated for transportation when such tasks are issued; there may be different types of idle AMRs, and some types of AMRs can only perform specific types of tasks.

Due to the complexity of business requirements, hierarchical and detailed combing of business is the focus of improving the efficiency of warehouse handling tasks.

Handling task distribution-task constraints

Task priority

Different tasks have different priorities, which can be measured by the following indicators:

1. Task issuance / deadline: In the current non-empty task pool, different tasks have different issuance times or deadlines. Generally speaking, the deadline is given priority, and the earlier the priority, the higher the priority; when the deadline is unknown, consider Issue time.
2. Task types: Tasks are divided according to types, including pallet storage, pallet removal, empty pallet return, stack pallet shift, obstructed pallet shift, bin storage, and bin removal, etc.

Generally speaking, the priority of different task types meets the requirements of outbound task>inbound task>tally task. Of course, the order is not absolute, mainly based on business efficiency requirements.

3. Queuing status: Taking CTU inbound tasks as an example, a workstation may have a large backlog of tasks that need to be carried by CTU, so the priority of the tasks of this workstation is higher than that of other workstations.

Priority scoring mechanism

For each task, a comprehensive score can be given according to its index attributes to evaluate its priority; the lower the score, the higher the priority.

For a single indicator, the score corresponding to each task is limited to between 0 and 1, and it is configurable. For example, for the task type indicator, the scores of actual outbound tasks and cut inbound tasks are 0.5 and 0.8, respectively, which means that outbound tasks precede inbound tasks.

Task types belong to category indicators. For indicators of quantity (tasks corresponding to the number of workstations inline) or time (task deadline) type indicators, one way is to sort them by value, and then fit a score by order. For example, suppose that the task set for this time is 5 tasks A, B, C, D, E, and the deadlines are B, C, A, E, D in ascending order, then A, B, C, D, E correspond to the serial numbers It is 3/(3+1+2+5+4) or 3²/(3²+1²+2²+5²+4²).

Different indicators also have a priority order. A simple method is to multiply the scores of different indicators by weight with significant discrimination to obtain the weighted comprehensive score of each task.

Task dependency

Different tasks may have task dependencies. For example, the PS manual area is out of the warehouse. The current workstation needs to complete the previous task and remove the pallet before it can perform the next out of warehouse handling task. Therefore, the outbound transportation task depends on the pallet return or empty pallet recovery task of the corresponding workstation. Therefore, for the task queue that has been generated according to the priority, for each dependent task, the corresponding dependent task needs to be inserted before the task.

Generally speaking, different task types have priority or interdependence. For example, after the outbound pallet in the PS area is emptied, the empty pallet needs to be removed first, otherwise, the next inbound task bound to the site cannot be executed. However, the task of stacking and transferring needs to be executed before the empty stacking back to the library, otherwise, the stacking machine will occupy the stacking machine and the empty stacking back to the library task cannot be executed.

Capacity ratio

Take the PS area as an example. Although the outbound task has a higher priority, if there are more outbound tasks, it may cause all AMRs to perform all outbound handling tasks, resulting in a backlog of inbound pallets at the connection point, so a certain amount of equipment needs to be reserved. Than’s AMR capacity only serves or prioritizes warehousing tasks.

Capacity limit

Due to the physical capacity limitations of the starting point, destination, or driving area, it is necessary to implement capacity restrictions on AMRs or transport containers that arrive at the corresponding location at the same time, such as the number of containers that can be accommodated at the destination site in a short time, and the number of AMRs that can be driven into the lane. The restriction conditions can be flexibly configured according to specific business scenarios.

Handling task distribution-AMR constraints

Executable task type restrictions

After dividing the capacity group, each AMR can only perform specific types of tasks.

AMR priority

AMR priority classification is common in CTU scenarios. For example, tasks in the same lane are given priority to AMRs that have been assigned tasks in the lane, and inbound and outbound tasks are given priority to AMRs that are going to the corresponding workstation.

Handling task distribution-core matching algorithm

For the core matching algorithm, there is already a set of proven practices. All the matching problems involved in this article are subject to two parts: task and AMR.

Generally speaking, according to whether the maximum number of tasks that the robot can mount at a certain time is one, it can be divided into two modes: single-task mode and task queue mode. Among them, in the single-task mode, the robot can only receive one task at a time, and can only receive and execute the next task after completing the current task; for the task queue mode, the robot can allocate multiple tasks at once, according to different scenarios, according to a certain order or Simultaneous execution.

According to the number of the two parties in the single-round assignment problem (ie AMR and handling tasks), it can be divided into one-to-many and many-to-many modes.

One-to-many: polling strategy

Many-to-many: MCMF; integer programming

One-to-many mode

One-to-many mode is mainly divided into the following two situations:

1. workcentre initiated: When a new task is generated, select the most suitable one from multiple alternative robots
2. Vehicle initiated: When a robot is idle, select one of the waiting tasks for the robot to execute

workcentre initiated task assignment problem

In this mode, how to choose the most suitable one from the available robots is the core of the entire strategy. Generally speaking, there are the following principles:

Nearest Vehicle rule

Select the Jth AMR that meets the following conditions:

AMRj = min{ Dj } for all idle vehicles

Where Dj is the distance from AMRj to the current task point

Farthest Vehicle rule

Select the Jth AMR that meets the following conditions:

Dj/8j = { Dj/Vj } for all idle vehicles j

Where Vj is the driving speed of the AMRj

Longest Idle Vehicle rule

Select the Jth AMR that meets the following conditions:

Tj = max{ Ti }

Among them Ti=Tc-Ti, Tc represents the current time, Ti represents the free time of the AMRi up to the current time

For the current task pool to be executed (no priority between tasks), perform the above selection principles for each task in turn, match an optimal AMR for each task, and then select the number of AMRs and tasks from low to high according to the cost. The pair with the largest number is the result of the allocation.

Vehicle initiated task assignment problem

In this mode, each time you choose the most suitable task for the currently idle car to execute

Shortest Travel Time/Distance rule

Select the task with the shortest empty driving time or the shortest distance for the current AMR. Other principles include the principle of the maximum outbound queue, FCFS principle, etc.

For the currently available AMR resource pool, perform the above selection principles for each AMR in turn, match an optimal task for each AMR, and then select the number of pairs that do not exceed the number of available AMRs and the largest number of tasks according to the cost from low to high. As a result of the distribution.

There are two different ways to choose a car based on a task or to choose a task based on a car. Generally speaking, the long-term failure of a certain task is more serious than the long-term idleness of a certain AMR, so selecting a car based on the task is a more appropriate way.

Many-to-many mode

Minimum cost and maximum flow (MCMF)

Create a map based on the current task set to be assigned and the AMR set:

Consider a typical scenario, each AMR can only perform one task at the same time, then the capacity of each AMR to the source point is 1. The capacity of each edge from the task to the sink point is obviously 1. If an AMR executes, there is a directed edge from the AMR to the task, and its capacity is 1. The cost of each edge can be obtained by combining the following points: (1) task priority score (2) AMR priority score (3) handling cost.

Handling task distribution-handling cost

Generally speaking, the starting and ending points of a handling task are determined when the task is issued. Therefore, the cost of a certain specified capacity to perform a certain specified handling task can be clearly defined. Common definition methods include handling distance and handling time.

Taking into account that the driving direction of the AMR in the warehouse is generally two orthogonal directions, horizontal and vertical in a two-dimensional plane, common distance definition methods include Euclidean distance or Manhattan distance, which is relatively simple.

Another more accurate method is to call the path planning algorithm (A* etc.) to calculate the complete distance of the shortest path from AMR→task start→task end.

This method is especially suitable for the situation where there is a one-way road in the road network. Considering the high cost of real-time calculation, the distances of all complete paths in the map can be stored and directly searched. In the case of route congestion, different costs can be defined for each edge according to map hotspot information. The handling distance and the handling time can be transformed into each other. For example, for each straight path in the complete path, the travel time based on the speed planning can be obtained according to the acceleration information of the AMR, and the turning time is added to each turning behavior.

Handling task distribution-task execution

In the case of mounting task queues or multi-transfer point tasks, in order for the robot to perform tasks, it is also necessary to determine the sequence of tasks involved, specifically including:

1. If there are multiple transit points or destination points, it is necessary to determine the order of service between them;
2. If you use the task queue mode, you need to determine the execution order between multiple tasks. The way to determine the execution order is different in different scenarios. The main considerations include distance and the current load situation of the workstation.

Each machine needs to be assigned one or more handling tasks, and it is necessary to determine the racks and the handling sequence that each robot needs to handle so that the total handling distance of all robots is the shortest or the completion time of all tasks is the shortest.

In this scenario, task assignment and sequence determination are simultaneously determined by solving a variant vehicle routing problem (VRP). For the picking support robot system introduced in the previous section, determining the robot’s travel order to picking points (that is, multiple transit points) can be abstracted as a classic Traveling Salesman Problem (TSP) under the structure of the storage road network. Or it’s a variant problem, by minimizing the length of the travel path to determine the order of arrival of each picking point.

In the handling robot scenario, multiple workstations may require items on the same shelf, that is, a handling task has multiple destinations. Although the order of arrival of each workstation can be determined by the TSP method to minimize the overall handling distance, it also needs to be adjusted according to the task load situation of the workstation at the time, and priority can be given to the workstations with relatively urgent needs or the currently idle workstations to reduce the wait, Although it will increase a part of the handling cost, it can improve the overall system operation efficiency

Handling task distribution-evaluation and sensitivity analysis

Task allocation and execution strategies will vary according to the different needs of different scenarios, and for the same business needs in the same scenario, there are usually a variety of different scheduling strategies to choose from, even the same strategy will be due to Different built-in parameter choices produce different performances. In reality, it is usually difficult to completely determine how a single link affects the overall system production efficiency.

Nevertheless, through the analysis of some specific statistics, we can also roughly understand the impact of strategy on system performance. For the distribution and execution of the handling tasks introduced in this section, in order picking scenarios such as picking and picking support robot systems, several statistics can be used to evaluate the performance of scheduling strategies, including:

1. Order production efficiency: the ratio of the number of completed orders to the number of accepted orders within a certain period of time
2. Response time: the sum of the time the task waits for the robot to execute and the idle time of the robot
3. Production time: the time when the order is produced in the system
4. Average robot utilization: the time the robot performs the task (including the ratio of the idling and full load time to the total time)

In the actual production system, more statistics will be calculated and monitored for subsequent performance analysis, including the waiting time of workstation picking, the average handling distance of robots, and the average time consumption of handling tasks. For the sorting scene, the efficiency of parcel delivery will be calculated.

In addition to the system performance mentioned above, on the other hand, we also need to pay attention to the properties of the algorithm strategy itself. Specifically, with the continuous popularization of robot technology and the continuous expansion of business scenarios, the number of robots in the system and the number of tasks to be processed will further increase, which will make the scale of the scheduling problem become very large, and at the same time the business response to the system It may be very demanding. In this scenario, the algorithm strategy is required to have good computing performance.

The robot system will inevitably have abnormal failures, and the algorithm strategy also needs to be robust enough to be quickly adjusted. In addition, for the possible different scheduling targets in different time periods, the scheduling strategy also needs to be flexible enough to meet different requirements. In general, it is necessary to comprehensively evaluate the task scheduling strategy under consideration through aspects such as operational efficiency, computing performance, robustness, and flexibility.

Parking task scheduling

After the robot completes the previous task, if there is no subsequent task and no need to charge, it usually needs to perform the parking task.

The parking task means that the idle robot goes to the selected stop and waits until the next task is assigned. The selection of the stop needs to consider factors such as distance and other robot positions, and choose the appropriate parking without affecting the operation of other working robots. The point can improve the response speed of the robot system to new tasks and thus improve the overall work efficiency.

Considering the stacker erection system, the parking points include the entry and exit workstations, the shelf mid-point, and the completion point of the previous task.

For AMR systems, common parking situations include:

1. Go to the pre-planned designated parking place to park;
2. Cruise on the planned path until a new task is assigned;
3. Wait at the place where the previous task was completed.

In addition, the ring-distributed parking space selection strategy of ring workstations is based on the probability of each workstation task, and parking spaces are selected to reduce the average response time as much as possible. The circular parking strategy is divided into static and dynamic. In the static strategy, the parking space is selected and fixed until recalculated, while the dynamic strategy is extended on the basis of the static strategy. The selection of parking spaces needs to be based on all current free parking spaces. The parking position of the trolley will change dynamically.

In the real scenario, the idle robot parking task scheduling mainly includes first selecting a suitable parking space and can terminate the parking task at any time to perform a new handling task during the process of going to the parking spot and waiting at the parking spot.

Among them, the overall selection process of generating parking spaces is roughly divided into two parts: first, the range of optional parking spaces needs to be determined. In some scenarios, a number of fixed parking positions have been designed at the beginning of planning, and idle robots can only be used in these In the parking space, select a location that is not currently occupied by other robots for parking; while in other scenarios, there is no fixed parking location, and the robot can select any optional location (non-selectable locations include points that cause route blockage, etc.). Parking.

After determining the range of optional parking spaces, the second step needs to select this specific parking space based on the distance and the parking position of other idle robots. Among them, the distance factor considers the location of the area where the next task may occur as much as possible to reduce the moving distance and improve the response speed. At the same time, it is also necessary to consider the parking position of other idle robots, balance the distribution density of robots in each area, and avoid waste of resources caused by too many idle robots in a specific area, And the lack of robots in other areas causes untimely response after accepting tasks. Specific to the parking task scheduling of different types of robots in different scenarios, it is necessary to improve the overall response speed as the goal, consider the aforementioned influencing factors, and select according to the characteristics and requirements of specific scenarios.

The following is a brief discussion on the parking scheduling of the goods-to-human robot and the sorting robot to elaborate on the overall process of parking scheduling proposed earlier.

For goods-to-human robot systems, fixed parking spaces are usually not planned but dynamically selected each time. The parking space selection strategy will vary according to different task types. For example, the last executed task was an inventory or warehousing task. When the robot transports the rack to the corresponding inventory or warehousing workstation, the inventory and storage are completed. It also needs to be transported back to the warehouse, so you can choose to park on-site to reduce the subsequent empty driving distance of the robot, but because the inventory and shelf tasks usually take a long time to execute, during this period, if there are other more urgent tasks, the robot can be called.

On the other hand, the parking selection after the task of returning to the library is executed will be different. After the robot moves the rack back to the storage space, it usually chooses a suitable parking spot for parking. In the first step, you must first confirm the optional parking point. Parking on the road will cause congestion. Generally, it is not selected, and the empty storage space may be conflicted due to the subsequent return of shelves to the warehouse. Generally, it is generally not selected. Choose storage locations under the shelves that are not occupied by robots. After that, in the second step, choose a storage space under the shelf that is far away from other parking robots but closer to the workstation to park, so as to ensure that the idle robots are distributed evenly and are as close as possible to subsequent possible tasks, thereby improving the overall response of the system speed.

For the sorting robot system, each packing station is generally planned with a fixed queuing position, and the queuing position is also graded, and the sorting robot needs to select a fixed queuing position of the packing station after completing the last parcel allocation. Carry out parking and wait.

When selecting the queuing position, first consider selecting the queuing position corresponding to the package table with the least number of waiting for cars as the optional range, so that the resource capacity of each package table is balanced. If the task amount of each package table is different, it can be based on The number of tasks is weighted and selected, and then the highest priority idle queuing space at the booking station is selected as the parking spot.

Through the above introduction, idle robots can choose parking points based on distance and other robot parking information by determining optional parking spaces, so as to ensure suitable parking distribution, and suitable robot parking distribution can effectively improve the system’s task. The response speed improves the overall operating efficiency.