A Novel Congestion Avoidance Algorithm for Autonomous Vehicles Assessed by Queue Modeling

A Novel Congestion Avoidance Algorithm for Autonomous Vehicles Assessed by Queue Modeling

Khashayar Kotobi (University of Tennessee at Chattanooga, Chattanooga, USA) and Mina Sartipi (University of Tennessee at Chattanooga, Chattanooga, USA)
DOI: 10.4018/IJITN.2019040101

Abstract

Autonomous vehicle (AV) fleet management is one of the major aspects of AV development that needs to be standardized before AV deployment. There has been no consensus on whether AV deployment in general will be beneficial or detrimental in terms of road congestion. There are similarities between packet transmission in computer networks and AV transportation in road networks. In this work, the authors argue that congestion avoidance algorithms used in computer networks can be applied for AV fleet management. Authors modify and evaluate a novel adaptation of additive increase and multiplicative decrease (AMID) congestion avoidance algorithm. The authors propose assigning different priorities to transportation tasks in order to facilitate sharing the limited resources in such as usage of the road network. This will be modeled and assessed using a queueing model based on AVs arrival distribution. This will result in a load balancing paradigm that can be used to share and manage limited resources. Then, by using numerical study authors merge congestion avoidance and load balancing to analyze the authors' scheme in term of road network throughput (number of cars in network for a given time) for AV fleet management. Their evaluation demonstrates the improvement in terms of road network throughput.
Article Preview
Top

Introduction

As the development of autonomous vehicles (AV) rapidly increases, there is a higher sense of urgency for engineers and regulator bodies to become more engaged in how these AVs will be integrated into the current road system. According to Federal Highway Association (FHWA), in 2016 there were more than 35,000 fatality crashes in the United States (FHWA 2018). Implementation of AVs can reduce these numbers significantly, if their sensors maintained carefully, since AVs do not have human limitation (Lutin et al., 2013). The sensing technology used in AV provides a “360”- degree visualization of the dynamic surrounding environment that the regular driver cannot access. By 2030, 1 in every 5 citizens will be the share of older population according to U.S. Census (USA Census 2018). As driver age increases, decline in visual capability, reaction time, and memory will impact their ability to drive. AVs also increase productivity significantly; autonomous trucks do not require the resting time as it is necessary for the regular trucks. In this paper we aim to focus on AV fleet management deployment by introducing other benefits that can arise from studying the AVs as a group. Here, we study the AVs in a macro level to identify a global optimal AV fleet deployment. By quantitatively studying a fleet of AVs in terms of arrival rate and waiting time in road network, we aim to propose routing and scheduling algorithms that reduce and/or reshape the traffic. Next, we aim to develop optimization algorithms and models that consider necessary trade-offs (e.g., quality of service, traffic congestion, travel time and cost) to determine how to best deploy AVs spatially and temporally. With proper data gathering and analysis, these algorithms can be used to manage a fleet of AVs.

AVs are being tested in few cities and they are expected to be deployed in more urban areas such as Pittsburgh and Seattle (AV Deployment 2018). These tests have been mainly focused on the performance of a single AV and its interaction with a dynamic environment in a real time (Dolgov et al., 2010 and Goerzen et al., 2010). We argue that there is an urgent need for a comprehensive protocol to manage the fleet of AVs (also called autonomous mobility-on-demand or AMoD) that is adaptable to a dynamic and fast paced road network. In order to achieve that protocol, we aim to build a scheduling protocol that will lead to a global optimal in terms of using the road capacity for the traffic containing both AV fleets and regular vehicles. By introducing a scheduling algorithm assessed by queueing theory based on real time and historical traffic data, we aim to avoid and/or reduce traffic congestion. The queue type is determined by the probability distribution of arrival time for each traffic type (regular or hybrid cars and AVs) in a queue. Then we allocate the number of AVs in each queue based on a corresponding routing protocol and the chosen queue type for each case study. Accordingly, fleet size will need to be tailored for each route. By combining routing, scheduling, and fleet size, we claim that one can provide a comprehensive algorithm for deployment of fleet of AVs in urban setting (Figure. 1).

Figure 1.

AV deployment using queueing theory and congestion avoidance algorithm by real time and historic data feedback block diagram

IJITN.2019040101.f01

In AV fleet management and routing schemes, multiple resources must be allocated among competing regular and hybrid cars and AVs. These resources include but not limited to electric charging, usage of road capacity, and parking. This multiple resource allocation is generally more difficult to solve than a single resource problem. These vehicles can achieve optimal allocation of these resources via regular communication with each other and traffic control units implemented in smart cities. Our resource allocation scheme is based on additive-increase and multiplicative-decrease (AMID) algorithm that is used to avoid congestion in transmission control protocol (TCP). Here by using numerical analysis we demonstrate that our new congestion avoidance algorithm for AVs can improve the road network throughout (number of cars in network for a given time) similar to algorithms used in computer networks.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 12: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing