Multi-Agent Systems for Warehouse Applications | Robotics for Smart Factory, Part 3
From the series: Robotics for Smart Factory
Current trends show a rise in the use of automated robots in manufacturing industries such as aerospace, automotive, biomedical, and clean energy. Multi-agent systems are a key concept in the larger megatrend of robotics in warehouse automation. In this talk, we will explore how to design, simulate, and scale multi-agent systems by evaluating objectives such as sizing a workspace, optimizing available resources, and maximizing work.
Published: 14 Feb 2022
Hey, everyone. Thank you for choosing this session. I'm Sarah Nambi, one of the development leads from MathWorks in the controlled streaming. Today I'm here to talk about designing and scaling multi-agent systems for warehouse automation. So the overview of the topic is going to be that we would discuss some trends in the warehouse automation and supply chain domain, talk about the merits of autonomous systems and the current challenges, the role of multi agents in our warehouse robotics, walk you through an example, and then finally, discuss the key takeaways.
So first off, let's talk about supply chain and warehouse automation. Logistics has evolved a lot in the past. Back then, there used to be the instance where the raw materials would be procured by the manufacturer, would develop the product, hand it off to the distributor, would then hand it off to the retailer, and then the consumer would go buy it from a retail store. In today's world, the ways of e-commerce, as well as how we've minimized the time that it takes to manufacture a product to customer delivery, has completely changed the market.
Manufacturing companies are trying to meet high customer demands where retail stores are not able to satisfy. A traditional industrial automation system cannot offer the flexibility to meet these changes and demands at full scale, as well as efficiency. So therefore, we've seen the rise of optimizing logistics, as well as the last mile delivery, which have become the key differentiators for organizations who are competing in the space. So given that scenario, this has led to businesses model their e-commerce and adopt a lot of automation in their warehouse logistics.
So let's talk about the different adoption. So the first piece I want to talk about is motion coordination between assembly line robots. These are stationary robots. All they get to do is few jobs of moving objects or trying to complete a particular task. The second piece is inventory management in warehouse centers. We're automating the entire warehouse system, as well as using automated guided vehicles, to deliver goods from one place to another.
Finally, the biggest piece of the puzzle, last mile delivery of the goods, is now being researched on, or even practical applications have come out, for UAVs as well as other rovers. All of these examples are what essentially we call multi-agent systems, because they're multiple players in the game, they could be homogeneous or heterogeneous. Today for our discussion, we are going to focus on inventory management and warehouse centers where they would use AGVs or Automated Guided Vehicles, to optimize their problem.
All right. What are the great merits of using multi-agent systems in warehouse applications? The first piece is having the autonomous piece or the complete flexibility of letting the agents choose the right job for a given agent. This is done while achieving a optimal condition, or an optimal cost. Similarly, they assist in utilizing all of the resources to its full potential. And finally, this is all being driven by meeting the customer demands at full scale, as well as speed. So our focus today would be on high-level control design needed for these multi-agent systems.
Challenges of these multi-agent systems, which I would like to talk about, is standardization of architecture. No matter how the research has grown in the past few decades, we haven't come up with the standardization process. Communication protocol is also something that is still being researched upon, as well as tried upon from peer to peer model, as well as a peer to server model, and this has not been standardized either.
A simulation platform, a generic simulation platform that is required to size the system before we implement it, or build it, to scale. And finally, generalization of metrics, we do have different metrics for a specific task or a specific application, but there is no generalized way of cohesively bringing all of this together.
So before we jump into multi-agent system, let's just take a look at what a autonomous robot means in warehouse applications. So a single agent, or a single robot, is one entity which contains sensors, as well as the smarts to understand its environment, or have a self-awareness of the environment, able to plan its path or its task from one location to another, as well as finally control its electronic components such as the drives, as well as sensors, and drive autonomously in a given 2D space, or 3D space.
All of this is being done while avoiding obstacles, as well as humans in the loop. This is what we would like to call a single agent. In the past decade or so, deployment of these advanced algorithms from perception to control have been so successful that people have been able to deploy these agents in the industry. These actually formed the basic backbone of multi-agent systems. These are the building blocks, and we're going to call them as a single unit agent.
So now we've defined a robot, or a single agent, how do they actually come into a warehouse application? All of these robots are automated guided vehicles, are expected to coordinate or interact with each other, as well as its environment, overcome the obstacles, as well as humans, and complete all the complex tasks that they have been assigned to in an optimal fashion.
So let's actually split this huge sentences into smaller goals in a modular fashion. The first piece is interacting with the environment, or even defining the environment. This piece of the puzzle we would like to call it a scenario creation. The second piece is communication. Communication with each other, of the robot or even with the environment, and we would want to call this particular modulus communication protocol, or the simple communication block.
And once you're able to communicate, you would want to avoid each other, or avoid bumping into each other, and resolve conflicts. So finding optimal path in a heavy traffic environment is the other piece, where we want to term this as the routing engine. And the final piece of the puzzle is to do all of this, as will complete the actual task that was given to these robots, with utmost efficiency, wherein comes to the tasking engine.
So now we have smaller goals for this bigger problem. How do we structure this and come up with the nice architecture? The first piece is building the environment, as well as defining these robots. And then, setting up the communication protocols, one is now that we set the robots up, as well as the environment. Now set the communication protocols. Once the communication protocol is set up, then we would use the algorithms to manage all of these robots, as well as do your jobs efficiently. So we have the tasking engine, and then the routing engine.
All of the environment and the robots communicate with each other, either via talking to a single server or from a peer to peer communication. Once you have the communication set up, it also talks to the tasking and the routing engine, which would help you resolve, as well as complete, these tasks in an optimal fashion.
So how do you build the environment and the robots? You could easily build the environment and these robots using the Simulink platform. That's our communication. There's a product called SimEvents where we would use entities, as well as event-based discrete systems, to build a communication protocol. Finally, we could use custom algorithms, as well as Stateflow, to manage the state of these agents or robots, as well as the jobs that they've been assigned to do.
Now let's talk about other details inside these high level building blocks. So what is the next step that we need to do? So scenario creation, defining the environment, coming up with a map, coming up with a traffic graph for these robots could actually navigate. Secondly, when we define the robots, we also need to define their jobs. So since we are talking about a simulation environment, we want to create these entities.
Once you've created the entity of an agent, this particular agent or robot has its own flavor of dynamics. So we want to find that. And now that we have the definition of an environment and a robot, the communication is going to be event-based. This could be a discrete event, as well as it could be a broadcast event while being discreet.
Now that these messages are flowing in, it would help us then allocate all of these jobs to particular agents, depending upon how complex they are, as well as how expensive they are for each of these agents. And once they've been assigned without coordination, all of these agents would end up bumping each other. So we have the routing engine, where it would resolve all of the conflicts between these agents.
So now let's take a quick look as to how we've come up with the workflow. The first step is to create the scenario, which is the environment. The second step is to create the entities, which are going to be the jobs as well as the agents for a specific warehouse problem. The agents have another flavor to them where we need to define their dynamics. And finally, these agents need to talk to each other, as well as talk to the tasking and routing engine. So they need to broadcast messages, as well as receive messages, so this would be an event-based communication.
And then finally, the tasking allocation algorithms, you could allocate all of these jobs to particular agents depending upon their cost. And how do we get these costs? These costs are actually Manhattan distance from point A to point B, energy levels of the particular robot, or even add a penalty to robots which are constantly in conflict. So all of this cost calculation would be done by the conflict management piece, or the routing engine. Finally, we have all of this. Then we would start simulating them.
So the first step, scenario creation. So let's take a look at this particular diagram where we've come up with a binary occupancy grid for a 3D robot environment. You can also see the traffic graph, which has nodes and edges, such that it makes the conflict management much more efficient, such that each of these agents could potentially reserve an area or come up with multiple paths for a particular job.
The second piece is entity creation. This entity creation is now being done by SimEvents. I'm using a entity creator, highlighted over there, which is specifically for a agent or a robot. So you could generate an entity as soon as the simulation gets started. You could have exit conditions, as well as entry conditions.
So over here, we are creating an agent or a robot with a particular ID, current position, type, and footprint. You don't have to provide these details every single time, but just give the number of agents that you would like to simulate, and this would get automatically generated. So that's how modular this design is. Once you have created your agent, it's being stored as agent data, which needs to be passed on to your initialization engine where you're creating all of these events, or the broadcast messages. So you have the entity folder.
So now that your jobs have been created, your agents have been created, the next piece is defining the dynamics for these agents. So one of the examples is using the Differential-Drive Robot block from the Robotics Toolbox. And you can specify the real radius of the robot, as well as the track width of the robot, speed as well up to the neutral state. So this is a kinematic model, and you have multiple other models that, if you choose to do so, you can use Simulink to explore.
Now that dynamics have been defined, the next piece is communication. So event-based communication is where you would use essential cues with first in, first out, or last in, first out, or broadcast until the downstream block accepts it. In our case, the downstream block is going to be a server, and the example that we are looking at is a communication protocol where all of the agents talk to a particular server. There is no peer to peer communication, but a peer to server communication. These entities are all created for agents, as well as tasks, and they're all queued up for the traffic network as well.
Now that communication has been set up, the next piece is to define the tasking engine. How would you define a task or a job? It's defined as moving a package from point A to point B. What is associated with the task? A cost to complete the task. In our case, we would take into account the Manhattan distance of the route from A to B, as well as the current position of the agent.
Availability of an agent is also something that we need to take into consideration. So depending on the availability, as well as the cost, we can allocate a particular job to the least expensive agent. In doing so, we could take into account multiple algorithms that are already in the game theory domains, such as Hungarian, Auction, or Greedy.
Now that we've assigned these jobs to specific agents, we want to keep track of how these jobs are doing. So you can potentially use a state machine, Stateflow, from Simulink actually helps you build these state machines to manage tasks.
Now that we set up the tasking engine, we want to build the routing engine. The tasking engine mainly depends on the routing engine to calculate the cost and update the cost every single time stamp of the simulation.
So now we have the cost, as well as the task, we need to ensure that there is no conflict, or there's no chaos between the agents when they're trying to move about in a given 3D, 2D space. Conflict management can be carried out in multiple ways, using barrier functions, using reservation principle, using a dynamic A* algorithm between multiple agents.
Similarly that we are planning multiple routes using the router, you can also use a state machine to manage these bots within the particular route they choose to travel on. This would be carried out using Stateflow from Simulink, so feel free to explore that particular piece.
And finally, we would like to simulate this entire system, plot the relevant results to understand tasking efficiency, assignment metrics, or which agent is being assigned to each task, progression of how these tasks are doing, as well as the health of the agents. Whether the agent is available, busy, or is it broken down to some situation.
All right. So now that we've come up with the workflow, and we've set up this entire scenario, let's try to look at an example. So the premise of the problem is to use x number of agents to complete y number of tasks in a distribution center. So what you're seeing on the top left is the initialization engine, or the entity pool where we would create the bus signals for agents and tasks.
So now we have to find the bus, then we would create these entities using the entity generator, where we would name it and it would get mapped to the entity pool. So as we explained earlier, each entity has an ID current position type, as well as a footprint. So once you've defined that, it applies to task, as well as your traffic graph. And then, your entire entity engine is set up.
So the next piece is updating the tasks and agents. So this is where you're tasking engine comes into play, as well as your state machine for managing your agents or robots. So each of these Stateflow managers manage the transition of the tasks, as well as the agents. And then you have the dynamics block for the agents. You have the metrics block to visualize metrics. And then finally, the end simulation block where we end the simulation, depending on reaching a particular criteria.
We are using five agents over here to complete 11 tasks. So let's take a look at the simulation. So you can see five agents on your right trying to move. We've set up the problem, such that there is only one loading dock. And you can see that the assignment has happened immediately, where each agent is assigned to a particular task. And you can observe that in the bottom right.
And then to understand their status, you can see all of these tasks are in progress, versus the other six are yet to be completed. And all of these five agents are busy. So we've created a conflict scenario over here, just by having one loading station, so that the agents would actually slow down and you can see them re-planning and recalculating their cost and then taking off again.
So the efficiency improves incredibly as you start scaling the system. You could increase the number of agents from 5 to 100, as well as increase the number of tasks from 11 to 100, or 1,000. And then see how your efficiency dips, or how the conflict doesn't get resolved, or the number of tasks always in the progress state. So this would help you size the system, design a system, and scale them responsibly and optimally. I hope you enjoyed that simulation.
So the key takeaways for this particular problem is the modularization of the problem statement. As I said earlier, if you pull out the affected pieces, then you could use only a few parameters, such as number of agents, number of tasks, choice of algorithm for you to use for your tasking in your routing engine, then you'd be well on your way to scale a system. Scaling a system right now with our example is only possible because the right architecture, so choosing the right architecture is very important.
Once we've made the right architecture, next piece is choosing the right algorithms. Tasking and guarding algorithms are very important, depending upon how you end up using it for your application. It could be for a bunch of AGVs or it could be for a fleet of stationary robots which just pick and place.
All of this is only possible using SimEvents and Stateflow in Simulink, where we've used them to architect scalable multiple agent solutions. So I would highly recommend checking out some events in Stateflow for you to design a scalable multi-agent system.
I hope you enjoyed the presentation. Thank you for your time. I would appreciate any feedback that you've got, so please do reach out to me. Here's my contact information. And I will watch out the space for any further questions that you have. Thank you.