Simultaneous Optimization of Task Allocation and Path Planning Using Mixed-Integer Programming for Time and Capacity Constrained Multi-Agent Pickup and Delivery

Takuma Okubo, Masaki Takahashi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

Lately, there has been a need to improve the efficiency of material movements within factories and multi-agents are required to perform these tasks. In this study, graphical representation and mixed-integer programming have been adopted for simultaneous optimization of task allocation and path planning for each agent to achieve the following three goals. First, this study realizes time and capacity constrained multi-agent pickup and delivery (TCMAPD) that simultaneously considers time constraints, capacity constraints, and collision avoidance. Previous studies have not considered these constraints simultaneously. Thus, we can solve the problems associated with using multi-agents in actual factories. Second, we achieved TCMAPD that optimizes the collision avoidance between multi-agents. In conventional research, only a single collision avoidance method can be used. However, an appropriate route was selected from a variety of avoidance methods in this study. Hence, we could achieve a more efficient task allocation and path planning with collision avoidance. Third, the proposed method simultaneously optimizes task allocation and path planning for each agent. Previous studies have separately considered the approach of optimizing task allocation and path planning or used the cost of path planning after task allocation to again perform task allocation and path planning. To simultaneously optimize them in a single plan, we have developed a solution-derivable formulation using mixed-integer programming to derive a globally optimal solution. This enables efficient planning with a reduced total time traveled by the agents.

Original languageEnglish
Title of host publication2022 22nd International Conference on Control, Automation and Systems, ICCAS 2022
PublisherIEEE Computer Society
Pages1088-1093
Number of pages6
ISBN (Electronic)9788993215243
DOIs
Publication statusPublished - 2022
Event22nd International Conference on Control, Automation and Systems, ICCAS 2022 - Busan, Korea, Republic of
Duration: 2022 Nov 272022 Dec 1

Publication series

NameInternational Conference on Control, Automation and Systems
Volume2022-November
ISSN (Print)1598-7833

Conference

Conference22nd International Conference on Control, Automation and Systems, ICCAS 2022
Country/TerritoryKorea, Republic of
CityBusan
Period22/11/2722/12/1

Keywords

  • mixed-integer programming
  • multi-agent
  • path conflict
  • path planning
  • task allocation

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Simultaneous Optimization of Task Allocation and Path Planning Using Mixed-Integer Programming for Time and Capacity Constrained Multi-Agent Pickup and Delivery'. Together they form a unique fingerprint.

Cite this