The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
게임이론에서는 도로망의 교통혼잡을 혼잡게임으로 연구해 왔다. 기존 작업에서는 각 에이전트의 도로 사용량이 고전 혼잡 게임과 마찬가지로 에이전트 이동의 전체 시간 범위 동안 정적이라고 가정했습니다. 그러나 각 에이전트는 경로를 구성하는 도로를 순차적으로 사용하기 때문에 이러한 가정은 재고되어야 합니다. 본 논문에서는 차량 네트워크에서 에이전트의 도로 이용 간의 시간 의존성을 고려한 경사하강법 기반의 다중 에이전트 분산 경로 선택 기법을 제안한다. 제안된 방식은 먼저 FIFO(First In First Out) 정책에 따라 에이전트의 확률적 점유를 고려하여 각 도로의 시간에 따른 흐름을 추정합니다. 그런 다음 경사하강법과 추정된 시간 의존 흐름을 이용하여 각 경로 후보의 최적 경로 선택 확률을 계산한다. 각 에이전트는 최종적으로 최적 경로 선택 확률에 따라 하나의 경로를 선택합니다. 우리는 먼저 제안된 방식이 에이전트 수와 개별 경로 후보 수의 곱에 반비례하는 수렴 속도로 기하급수적으로 정상 상태로 수렴할 수 있음을 증명합니다. 그리드형 네트워크와 실제 도로 네트워크에서의 시뮬레이션을 통해 제안하는 방식이 기존 정적 흐름 기반 접근 방식에 비해 실제 이동 시간을 각각 5.1%, 2.5% 향상시킬 수 있음을 보여줍니다. 또한, 우리는 제안된 기법이 무선 통신의 낮은 보급률이나 제한된 전송 범위로 인해 발생할 수 있는 에이전트 간의 불완전한 정보 공유에 대해 강력함을 입증합니다.
Takanori HARA
Nara Institute of Science and Technology
Masahiro SASABE
Nara Institute of Science and Technology
Shoji KASAHARA
Nara Institute of Science and Technology
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Takanori HARA, Masahiro SASABE, Shoji KASAHARA, "Multi-Agent Distributed Route Selection under Consideration of Time Dependency among Agents' Road Usage for Vehicular Networks" in IEICE TRANSACTIONS on Communications,
vol. E105-B, no. 2, pp. 140-150, February 2022, doi: 10.1587/transcom.2021CET0001.
Abstract: Traffic congestion in road networks has been studied as the congestion game in game theory. In the existing work, the road usage by each agent was assumed to be static during the whole time horizon of the agent's travel, as in the classical congestion game. This assumption, however, should be reconsidered because each agent sequentially uses roads composing the route. In this paper, we propose a multi-agent distributed route selection scheme based on a gradient descent method considering the time-dependency among agents' road usage for vehicular networks. The proposed scheme first estimates the time-dependent flow on each road by considering the agents' probabilistic occupation under the first-in-first-out (FIFO) policy. Then, it calculates the optimal route choice probability of each route candidate using the gradient descent method and the estimated time-dependent flow. Each agent finally selects one route according to the optimal route choice probabilities. We first prove that the proposed scheme can exponentially converge to the steady-state at the convergence rate inversely proportional to the product of the number of agents and that of individual route candidates. Through simulations under a grid-like network and a real road network, we show that the proposed scheme can improve the actual travel time by 5.1% and 2.5% compared with the conventional static-flow based approach, respectively. In addition, we demonstrate that the proposed scheme is robust against incomplete information sharing among agents, which would be caused by its low penetration ratio or limited transmission range of wireless communications.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2021CET0001/_p
부
@ARTICLE{e105-b_2_140,
author={Takanori HARA, Masahiro SASABE, Shoji KASAHARA, },
journal={IEICE TRANSACTIONS on Communications},
title={Multi-Agent Distributed Route Selection under Consideration of Time Dependency among Agents' Road Usage for Vehicular Networks},
year={2022},
volume={E105-B},
number={2},
pages={140-150},
abstract={Traffic congestion in road networks has been studied as the congestion game in game theory. In the existing work, the road usage by each agent was assumed to be static during the whole time horizon of the agent's travel, as in the classical congestion game. This assumption, however, should be reconsidered because each agent sequentially uses roads composing the route. In this paper, we propose a multi-agent distributed route selection scheme based on a gradient descent method considering the time-dependency among agents' road usage for vehicular networks. The proposed scheme first estimates the time-dependent flow on each road by considering the agents' probabilistic occupation under the first-in-first-out (FIFO) policy. Then, it calculates the optimal route choice probability of each route candidate using the gradient descent method and the estimated time-dependent flow. Each agent finally selects one route according to the optimal route choice probabilities. We first prove that the proposed scheme can exponentially converge to the steady-state at the convergence rate inversely proportional to the product of the number of agents and that of individual route candidates. Through simulations under a grid-like network and a real road network, we show that the proposed scheme can improve the actual travel time by 5.1% and 2.5% compared with the conventional static-flow based approach, respectively. In addition, we demonstrate that the proposed scheme is robust against incomplete information sharing among agents, which would be caused by its low penetration ratio or limited transmission range of wireless communications.},
keywords={},
doi={10.1587/transcom.2021CET0001},
ISSN={1745-1345},
month={February},}
부
TY - JOUR
TI - Multi-Agent Distributed Route Selection under Consideration of Time Dependency among Agents' Road Usage for Vehicular Networks
T2 - IEICE TRANSACTIONS on Communications
SP - 140
EP - 150
AU - Takanori HARA
AU - Masahiro SASABE
AU - Shoji KASAHARA
PY - 2022
DO - 10.1587/transcom.2021CET0001
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E105-B
IS - 2
JA - IEICE TRANSACTIONS on Communications
Y1 - February 2022
AB - Traffic congestion in road networks has been studied as the congestion game in game theory. In the existing work, the road usage by each agent was assumed to be static during the whole time horizon of the agent's travel, as in the classical congestion game. This assumption, however, should be reconsidered because each agent sequentially uses roads composing the route. In this paper, we propose a multi-agent distributed route selection scheme based on a gradient descent method considering the time-dependency among agents' road usage for vehicular networks. The proposed scheme first estimates the time-dependent flow on each road by considering the agents' probabilistic occupation under the first-in-first-out (FIFO) policy. Then, it calculates the optimal route choice probability of each route candidate using the gradient descent method and the estimated time-dependent flow. Each agent finally selects one route according to the optimal route choice probabilities. We first prove that the proposed scheme can exponentially converge to the steady-state at the convergence rate inversely proportional to the product of the number of agents and that of individual route candidates. Through simulations under a grid-like network and a real road network, we show that the proposed scheme can improve the actual travel time by 5.1% and 2.5% compared with the conventional static-flow based approach, respectively. In addition, we demonstrate that the proposed scheme is robust against incomplete information sharing among agents, which would be caused by its low penetration ratio or limited transmission range of wireless communications.
ER -