Experimental Evaluation of AGV Dispatching Methods in an Agent-Based Simulation Environment and a Digital Twin
A critical part of Automated Material Handling Systems (AMHS) is the task allocation and dispatching strategy employed. In order to better understand and investigate this component, we here present an extensive experimental evaluation of three different approaches with randomly generated, as well as...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-05-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/13/10/6171 |
| _version_ | 1797601209864945664 |
|---|---|
| author | Fabian Maas genannt Bermpohl Andreas Bresser Malte Langosz |
| author_facet | Fabian Maas genannt Bermpohl Andreas Bresser Malte Langosz |
| author_sort | Fabian Maas genannt Bermpohl |
| collection | DOAJ |
| description | A critical part of Automated Material Handling Systems (AMHS) is the task allocation and dispatching strategy employed. In order to better understand and investigate this component, we here present an extensive experimental evaluation of three different approaches with randomly generated, as well as custom designed, environment configurations. While previous studies typically focused on use cases based on highly constrained navigation capabilities (e.g., overhead hoist transport systems), our evaluation is built around highly mobile, free-ranging vehicles, i.e., Autonomous Mobile Robots (AMR) that are gaining popularity in a broad range of applications. Consequently, our experiments are conducted using a microscopic agent-based simulation, instead of the more common discrete-event simulation model. Dispatching methods often are built around the assumption of the asynchronous evaluation of an event-based model, i.e., vehicles trigger a cascade of individual dispatching decisions, e.g., when reaching intersections. We find that this does not translate very well to a fleet of highly mobile systems that can change direction at any time. With this in mind, we present formulations of well known dispatching approaches that are better suited for a synchronous evaluation of the dispatching decisions. The formulations are based on the Stable Marriage Problem (SMP) and the Linear Sum Assignment Problem (LSAP). We use matching and assignment algorithms to compute the actual dispatching decisions. The selected algorithms are evaluated in a multi-agent simulation environment. To integrate a centralised fleet management, a digital twin concept is proposed and implemented. By this approach, the fleet management is independent of the implementation of the specific agents, allowing to quickly adapt to other simulation-based or real application scenarios. For the experimental evaluation, two new performance measures related to the efficiency of a material handling system are proposed, <i>Travel Efficiency</i> and <i>Throughput Effort</i>. The experimental evaluation indicates that reassignment mechanisms in the dispatching method can help to increase the overall efficiency of the fleet. We did not find significant differences in absolute performance in terms of throughput rate. Additionally, the difference in performance between SMP- and LSAP-based dispatching with reassignment seems negligible. We conclude with a discussion, where we consider potential confounding factors and relate the findings to previously reported results found in the literature. |
| first_indexed | 2024-03-11T03:58:57Z |
| format | Article |
| id | doaj.art-b5fc13a42d0848c39c58ad6368fc9963 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-11T03:58:57Z |
| publishDate | 2023-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-b5fc13a42d0848c39c58ad6368fc99632023-11-18T00:21:38ZengMDPI AGApplied Sciences2076-34172023-05-011310617110.3390/app13106171Experimental Evaluation of AGV Dispatching Methods in an Agent-Based Simulation Environment and a Digital TwinFabian Maas genannt Bermpohl0Andreas Bresser1Malte Langosz2German Research Center for Articial Intelligence—Robotics Innovation Center, 28359 Bremen, GermanyGerman Research Center for Articial Intelligence—Robotics Innovation Center, 28359 Bremen, GermanyGerman Research Center for Articial Intelligence—Robotics Innovation Center, 28359 Bremen, GermanyA critical part of Automated Material Handling Systems (AMHS) is the task allocation and dispatching strategy employed. In order to better understand and investigate this component, we here present an extensive experimental evaluation of three different approaches with randomly generated, as well as custom designed, environment configurations. While previous studies typically focused on use cases based on highly constrained navigation capabilities (e.g., overhead hoist transport systems), our evaluation is built around highly mobile, free-ranging vehicles, i.e., Autonomous Mobile Robots (AMR) that are gaining popularity in a broad range of applications. Consequently, our experiments are conducted using a microscopic agent-based simulation, instead of the more common discrete-event simulation model. Dispatching methods often are built around the assumption of the asynchronous evaluation of an event-based model, i.e., vehicles trigger a cascade of individual dispatching decisions, e.g., when reaching intersections. We find that this does not translate very well to a fleet of highly mobile systems that can change direction at any time. With this in mind, we present formulations of well known dispatching approaches that are better suited for a synchronous evaluation of the dispatching decisions. The formulations are based on the Stable Marriage Problem (SMP) and the Linear Sum Assignment Problem (LSAP). We use matching and assignment algorithms to compute the actual dispatching decisions. The selected algorithms are evaluated in a multi-agent simulation environment. To integrate a centralised fleet management, a digital twin concept is proposed and implemented. By this approach, the fleet management is independent of the implementation of the specific agents, allowing to quickly adapt to other simulation-based or real application scenarios. For the experimental evaluation, two new performance measures related to the efficiency of a material handling system are proposed, <i>Travel Efficiency</i> and <i>Throughput Effort</i>. The experimental evaluation indicates that reassignment mechanisms in the dispatching method can help to increase the overall efficiency of the fleet. We did not find significant differences in absolute performance in terms of throughput rate. Additionally, the difference in performance between SMP- and LSAP-based dispatching with reassignment seems negligible. We conclude with a discussion, where we consider potential confounding factors and relate the findings to previously reported results found in the literature.https://www.mdpi.com/2076-3417/13/10/6171vehicle dispatchingagent-based simulationdigital twinindustry 4.0 |
| spellingShingle | Fabian Maas genannt Bermpohl Andreas Bresser Malte Langosz Experimental Evaluation of AGV Dispatching Methods in an Agent-Based Simulation Environment and a Digital Twin Applied Sciences vehicle dispatching agent-based simulation digital twin industry 4.0 |
| title | Experimental Evaluation of AGV Dispatching Methods in an Agent-Based Simulation Environment and a Digital Twin |
| title_full | Experimental Evaluation of AGV Dispatching Methods in an Agent-Based Simulation Environment and a Digital Twin |
| title_fullStr | Experimental Evaluation of AGV Dispatching Methods in an Agent-Based Simulation Environment and a Digital Twin |
| title_full_unstemmed | Experimental Evaluation of AGV Dispatching Methods in an Agent-Based Simulation Environment and a Digital Twin |
| title_short | Experimental Evaluation of AGV Dispatching Methods in an Agent-Based Simulation Environment and a Digital Twin |
| title_sort | experimental evaluation of agv dispatching methods in an agent based simulation environment and a digital twin |
| topic | vehicle dispatching agent-based simulation digital twin industry 4.0 |
| url | https://www.mdpi.com/2076-3417/13/10/6171 |
| work_keys_str_mv | AT fabianmaasgenanntbermpohl experimentalevaluationofagvdispatchingmethodsinanagentbasedsimulationenvironmentandadigitaltwin AT andreasbresser experimentalevaluationofagvdispatchingmethodsinanagentbasedsimulationenvironmentandadigitaltwin AT maltelangosz experimentalevaluationofagvdispatchingmethodsinanagentbasedsimulationenvironmentandadigitaltwin |