PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917030871957504 |
|---|---|
| author | Berto, Federico Hua, Chuanbo Luttmann, Laurin Son, Jiwoo Park, Junyoung Ahn, Kyuree Kwon, Changhyun Xie, Lin Park, Jinkyoo |
| author_facet | Berto, Federico Hua, Chuanbo Luttmann, Laurin Son, Jiwoo Park, Junyoung Ahn, Kyuree Kwon, Changhyun Xie, Lin Park, Jinkyoo |
| contents | Combinatorial optimization problems involving multiple agents are notoriously challenging due to their NP-hard nature and the necessity for effective agent coordination. Despite advancements in learning-based methods, existing approaches often face critical limitations, including suboptimal agent coordination, poor generalization, and high computational latency. To address these issues, we propose PARCO (Parallel AutoRegressive Combinatorial Optimization), a general reinforcement learning framework designed to construct high-quality solutions for multi-agent combinatorial tasks efficiently. To this end, PARCO integrates three key novel components: (1) transformer-based communication layers to enable effective agent collaboration during parallel solution construction, (2) a multiple pointer mechanism for low-latency, parallel agent decision-making, and (3) priority-based conflict handlers to resolve decision conflicts via learned priorities. We evaluate PARCO in multi-agent vehicle routing and scheduling problems, where our approach outperforms state-of-the-art learning methods, demonstrating strong generalization ability and remarkable computational efficiency. We make our source code publicly available to foster future research: https://github.com/ai4co/parco. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03811 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization Berto, Federico Hua, Chuanbo Luttmann, Laurin Son, Jiwoo Park, Junyoung Ahn, Kyuree Kwon, Changhyun Xie, Lin Park, Jinkyoo Multiagent Systems Artificial Intelligence Combinatorial optimization problems involving multiple agents are notoriously challenging due to their NP-hard nature and the necessity for effective agent coordination. Despite advancements in learning-based methods, existing approaches often face critical limitations, including suboptimal agent coordination, poor generalization, and high computational latency. To address these issues, we propose PARCO (Parallel AutoRegressive Combinatorial Optimization), a general reinforcement learning framework designed to construct high-quality solutions for multi-agent combinatorial tasks efficiently. To this end, PARCO integrates three key novel components: (1) transformer-based communication layers to enable effective agent collaboration during parallel solution construction, (2) a multiple pointer mechanism for low-latency, parallel agent decision-making, and (3) priority-based conflict handlers to resolve decision conflicts via learned priorities. We evaluate PARCO in multi-agent vehicle routing and scheduling problems, where our approach outperforms state-of-the-art learning methods, demonstrating strong generalization ability and remarkable computational efficiency. We make our source code publicly available to foster future research: https://github.com/ai4co/parco. |
| title | PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization |
| topic | Multiagent Systems Artificial Intelligence |
| url | https://arxiv.org/abs/2409.03811 |