Game-theoretic Distributed Learning Approach for Heterogeneous-cost Task Allocation with Budget Constraints
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913301268529152 |
|---|---|
| author | Yang, Weiyi Liu, Xiaolu He, Lei Du, Yonghao Chen, Yingwu |
| author_facet | Yang, Weiyi Liu, Xiaolu He, Lei Du, Yonghao Chen, Yingwu |
| contents | This paper investigates heterogeneous-cost task allocation with budget constraints (HCTAB), wherein heterogeneity is manifested through the varying capabilities and costs associated with different agents for task execution. Different from the centralized optimization-based method, the HCTAB problem is solved using a fully distributed framework, and a coalition formation game is introduced to provide a theoretical guarantee for this distributed framework. To solve the coalition formation game, a convergence-guaranteed log-linear learning algorithm based on heterogeneous cost is proposed. This algorithm incorporates two improvement strategies, namely, a cooperative exchange strategy and a heterogeneous-cost log-linear learning strategy. These strategies are specifically designed to be compatible with the heterogeneous cost and budget constraints characteristic of the HCTAB problem. Through ablation experiments, we demonstrate the effectiveness of these two improvements. Finally, numerical results show that the proposed algorithm outperforms existing task allocation algorithms and learning algorithms in terms of solving the HCTAB problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03974 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Game-theoretic Distributed Learning Approach for Heterogeneous-cost Task Allocation with Budget Constraints Yang, Weiyi Liu, Xiaolu He, Lei Du, Yonghao Chen, Yingwu Computer Science and Game Theory This paper investigates heterogeneous-cost task allocation with budget constraints (HCTAB), wherein heterogeneity is manifested through the varying capabilities and costs associated with different agents for task execution. Different from the centralized optimization-based method, the HCTAB problem is solved using a fully distributed framework, and a coalition formation game is introduced to provide a theoretical guarantee for this distributed framework. To solve the coalition formation game, a convergence-guaranteed log-linear learning algorithm based on heterogeneous cost is proposed. This algorithm incorporates two improvement strategies, namely, a cooperative exchange strategy and a heterogeneous-cost log-linear learning strategy. These strategies are specifically designed to be compatible with the heterogeneous cost and budget constraints characteristic of the HCTAB problem. Through ablation experiments, we demonstrate the effectiveness of these two improvements. Finally, numerical results show that the proposed algorithm outperforms existing task allocation algorithms and learning algorithms in terms of solving the HCTAB problem. |
| title | Game-theoretic Distributed Learning Approach for Heterogeneous-cost Task Allocation with Budget Constraints |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2404.03974 |