A Negotiation-Based Global Control Approach for Large-Scale Connected Vehicles

*Abstract*—With the pervasive deployment of networked sensors in the modern vehicles, a large amount of information regarding traffic system status can be collected in real-time. This paradigm provides the potential to perform the various types of control and coordination for large-scale connected vehicles. But even that, it is still a grand challenge to develop an autonomous vehicular system in which each vehicle can autonomously coordinate with other vehicles to improve system efficiency and route itself on the road network with a safety guarantee.

In this paper we propose a negotiation-based global control approach, which eliminates the road network congestion and minimizes the resource usage for large-scale connected vehicles in the vehicular system. Specifically, we impose a congestion cost function into the control approach which iteratively performs the path search on the network. Congestion is eliminated by forcing vehicles to negotiate for a resource and thereby determine which vehicle needs the resource most in each iteration. The emphasis of our approach is to adjust the congestion costs of routing resources in a gradual, semi-equilibrium fashion is maintained to achieve an optimum distribution of resources. Simulation results show that this approach can effectively generate a feasible routing path for each vehicle. Most importantly, the congestion is eliminated to ensure inter-vehicle safety and the usage of routing resource is minimized to improve system efficiency.

I. INTRODUCTION

With the development of emerging techniques, autonomous vehicles are rapidly becoming a reality. Moreover, since its potentially significant impact on economy, environment, and energy, this area has been drawing increasing attention over the last decade from academia, industry, and government. For example, the DARPA contest has demonstrated the feasibility of autonomous vehicles in ground traffic [1]. Next-generation autonomous vehicles not only precepts the environment with their own senors, but also communicates with other vehicles to improve the vehicle safety and transportation efficiency. This paradigm provides opportunities to perform the different types of coordination and control for large-scale connected vehicles in the vehicular system. However, it is non-trivial to control these connected vehicles in smart ground vehicular systems to ensure that each vehicle has a feasible trajectory and routes itself on the road network without congestion.

The control problem can be stated as that the routing resources are assigned to vehicles in order to successfully route each vehicle while achieving a given overall performance. The main goal is to complete the routing resources by all vehicles, which is difficult to achieve in road networks because of the lack of routing resources. The common approach to implementing this goal is to minimize the usage of routing resources by constructing the minimum routing path for each vehicle. Although this approach reduces the demand for routing resources, the vehicles will still complete for the same resources and result in the traffic congestion, and the challenge is to find a global control approach to allocate resources so that all vehicles can be routed without congestion.

Central to control the large-scale connected vehicles is to guarantee the congestion avoidance in the vehicular systems. In terms of congestion, there has been no consensus on whether autonomous vehicles in general, and vehicular systems in particular, will ultimately be beneficial or detrimental. Autonomous vehicles may be able to drive more efficiency without compromising safety by using faster reaction times, and thus the capacity of road network is increased and the congestion is reduced effectively [2]. On the downside, the balancing process of vehicular systems increases the total number of vehicles on the road network. Indeed, the increasing vehicles may contribute to an increase in congestion [3]. However, these statements do not take into account that in smart vehicular systems, the routing path can be control intelligently to avoid increasing congestion or perhaps even decrease it.

Despite recent advances in autonomous vehicles, we are still at an early stage in the development of safe and efficient vehicular system. Among the many challenges needing to be addressed, we are particularly interested in the problem of achieving system-wide safety and efficiency consisting of large-scale connected vehicles. To tackle this problem we propose a negotiation-based global control approach to iteratively routes each vehicle until to find a feasible solution. In this approach, vehicles are allowed to share the same routing resources and result in the congestion initially, but subsequently must negotiate with other vehicles to determine which vehicles needs the shared resources most to reduce the congestion. A congestion analysis is performed every iteration to apply pressure continuously to each vehicle. Our approach is to adjust the cost of routing resources in a gradual, semiequilibrium fashion is maintained to achieve an optimum distribution of resources. Our contributions are summarized as follows.

- To the best of our knowledge, we are the first work to solve the congestion between large-scale connected vehicles.
- We propose a negotiation-based control approach, which resorts to a cost function to iteratively eliminate the congestion until to converge a feasible solution.
- We provide some proofs to demonstrate the convergence of negotiation-based control paradigm, which can be modeled as a conflict resolution method for bipartite matching.
- Experimental results show that our approach effectively converges a feasible solution with congestion avoidance and minimizes the usage of routing resources.

The rest of the paper is organized as follows. In Section II, we present the relevant prior works. In Section III, we provide the preliminaries and problem formulation. In Section IV, we describe the details of negotiation-based control approach which leads to a safe and efficient vehicular system. In Section V, we demonstrate the correctness of the negotiation paradigm. In Section VI, We also quantitatively analyze the experimental results, followed by the conclusion and future work in Section VII.

II. RELATED WORK

In this section we simply introduce the literatures that are closely related to this paper.

There exists various approaches to improve the performance of connected vehicle systems. An efficient work provides a model predictive control approach to maintain the safe transportation networks [4]. Moreover, the related routing and planning approaches are proposed to enable the efficiency of vehicular systems [5], [6]. And then, vehicle balancing methods are proposed to reduce the number of vehicles needed to serve all passengers with mobility-on-demand systems [7], [8]. Also, field test and simulations are conducted in tandem and iteratively to facilitate interference model selection and configuration for vehicular networks [9]. The recent work focuses on dynamic region partition such that the coordinated vehicles performs the tasks in the specified regions [10]. Almost all current approaches do not consider vehicle-tovehicle interactions that would cause more congestion and reduce system performance.

Another topic of traffic congestion that stand out in this studies is that caused by the constraint of resources between the connected vehicles. The first work [11] attempts to design the congestion model to formalize the relationship between vehicle speed, density, and flow. Since then, several approaches are proposed to improve the accuracy of congestion model, including optimization [12], [13], empirical [14], simulation [15], and the queuing-theoretical [16]. While these works can predict traffic patterns, the models are inefficient and the primary goal has been the analysis of traffic behavior rather than on control. Efforts to control congestion have been limited to control of connected vehicles because human-level behave is non-cooperative [17], [18]. And then, a lane-level cooperative collision avoidance system is proposed based on vehicular sensor networks [19]. The cooperative, system-wide vehicle control is similar to the dynamic traffic assignment [12] and to [20] in the cased of online routing. The key difference is that these approaches only optimize the routes for vehicles while we globally optimize the routes and eliminates the congestion for large-scale connected vehicles.

In this paper we propose a negotiation-congestion global control approach in which the resource usage is minimized and the congestion is avoided in large-scale vehicular systems.

III. PROBLEM STATEMENT

The control of connected vehicles is an important process in intelligent vehicular systems. It consists in assigning ground routing resources to each vehicle of vehicular system in order to connect its current location to the destination.

The resources in a road traffic network and their connections are represented by a graph *G** _{A }*= (

*N,E*). The set of vertices

*N*corresponds to a routing resource such as the road segments and the edges

*E*to the feasible links that connect these nodes in the ground traffic network. Each vehicle consists of one node of

*G*

*, the vehicle’s source*

_{A}*s*

*, along with a subset of nodes corresponding to its sink*

_{i}*t*

*.*

_{i}Moreover, in routing resource graph *G** _{A }*= (

*N,E*), the weight associated with each node

*n*is either the length of road segment or vehicle travel time. Here we assume that each node of the graph is assigned a weight that represents the road segment length. Thus each node

*n*in the graph is related with a constant length

*d*

*and a congestion cost*

_{n }*c*

*determined by the competition among vehicles for*

_{n }*n*.

Given a vehicle *i *in a graph mapped onto the ground traffic network, the vehicle routing path *RP** _{i }*is the set of terminals including the source terminal

*s*

*and destination*

_{i }*t*

*.*

_{i}*RP*

*forms a subset of*

_{i }*N*. A feasible solution to the control problem for vehicle

*i*is the routing path

*RP*

*mapped onto the graph*

_{i }*G*

*and connecting*

_{A }*s*

*with its*

_{i }*t*

*.*

_{i}The objective of this work is to leverage a negotiationbased scheme to design a performance-driven control approach for connected vehicles in large-scale vehicular systems. The control problem of large-scale connected vehicles consists in the actual minimization of the routed length to drive from a selected origin to a destination in the road network with congestion avoidance. Minimization of a length cost in a graph can be solved by means of a standard shortest path algorithm. However, it is non-trivial to eliminate the congestion between vehicles in the same time to guarantee the safety.

Notice that vehicle control is a technology-specific variation of the disjoint path problem from graph theory, which is one of Karp’s original NP-complete problems [21]. In a graph, two routing paths are disjoint if they share no vertices or edges.

IV. METHODOLOGY

In this section, we present a negotiation-based global control approach, which provides the minimal resource usage and congestion avoidance between vehicles in large-scale vehicular systems.

# A. Overview

The design flow is summarized in Fig. 1. At first, we enable all vehicles in a vehicular system to be routed in the best manner possible to minimize the routing resources. And at the meanwhile, the congestion is permitted, which means that two or more different vehicles may use the same routing resources on a road network. Specifically, in practice, the occupation of a resource must be less than or equal to the capacity to maintain the congestion avoidance.

Fig. 1. Overview of negotiation-congestion scheme.

Initially, each vehicle is controlled with its ideal routing path, while it is infeasible owing to the congestions. And at the next, the routed paths will be ripped-up and the penalties associated with congestions are increased so that the vehicles are re-routed with the increased penalties. The process of increasing the penalties for congestion and re-controlling the vehicle routing continues iteratively until all congestions are removed and the solution is feasible.

In essence, the vehicles coordinate with each other to determine which vehicle gets to keep a shared resource.

# B. Congestion Cost Function

The principal idea is to permit unlimited sharing of road resources initially and then repeatedly re-control the vehicle routing until no resources are shared. By assigning congestion costs to the shared road resources, and increasing these costs with each iteration through the vehicles, this control approach encourages alternative routing paths to be explored until all the congestions are resolved.

Here we impose the congestion cost function for each road resource *n*. In negotiation-congestion scheme, this cost function *c** _{n }*has three terms, which can be adjusted to eliminate the congestion between vehicles.

*c** _{n }*= (

*b*

*+*

_{n }*h*

*) ×*

_{n}*p*

*(1)*

_{n}where *b** _{n }*is the base cost of using road resource

*n*, which can be used to reflect the length of the road resource. A reasonable choice for

*b*

*is the intrinsic length*

_{n }*d*

*of the node*

_{n }*n*, since minimizing the routing path length of a vehicle is equivalent to minimize the road resources of a vehicle in nature. In the remainder of our work, we set

*b*

*=*

_{n }*d*

*.*

_{n}The first-order congestion term *p** _{n }*is present cost, which represents the number of vehicles that are presently occupying the same road resource. The second-order congestion term

*h*

*is history cost, which is related to the history of congestion on a road resource*

_{n }*n*during previous iterations. This history cost

*h*

*grows monotonically with each iteration in which the road resource is shared. In fact, the*

_{n }*h*

*increases by a fixed amount each time when a vehicle is re-routed through an already occupied node.*

_{n }# C. Negotiation-Based Control Algorithm

Controlling a vehicle routing involves assigning the road resources such that the destination are reachable from the source. When controlling a fleet of vehicles, the order in which the vehicle routing are controlled may be critical since some road resources needed by a vehicle may be occupied by other vehicles. But our approach is not sensitive to the ordering, and the vehicles are routed in sequential to minimize the routing resource usage and eliminate the congestion in vehicular systems.

Algorithm 1 The negotiation-based control algorithm

1: NC(vehicles {*V** _{i}*}, network

*G*

*= h*

_{A }*N,E*i)

2: while route incomplete or congestion exists do

3: for each unrouted or congestion vehicle *V** _{i }*do

4: rip-up *RP** _{i }*if exists

5: *RP** _{i }*← {

*n*

*} (source node of*

_{s}*V*

*)*

_{i}6: *RP** _{i }*← Find-Shortest-Path(

*RP*

_{i}*,n*

*) 7: update present cost of*

_{s}*RP*

*nodes.*

_{i }8: end for

9: update history cost of *RP** _{i }*nodes.

10: end while 11: end NC

12:

13: Find-Shortest-Path(*RP*, *n** _{s}*) 14: for each node

*n*in

*RP*do 15: enqueue

*n*onto

*Q*with key 0.

16: end for

17: while a new sink of *n** _{s }*has not been found do 18: dequeue node,

*m*, with lowest key from

*Q*.

19: if *m *was not previously dequeued then

20: for neighbor *n *of *m *do 21: enqueue *n *on *Q *with cost of *n *+ key of *m*.

22: end for

23: end if

24: end while

25: backtrace from sink to a node of *RP** _{i }*that is reached

26: return this path

27: end Find-Shortest-Path

The implementation details of negotiation-based control (NC) algorithm are shown in Algorithm 1. This algorithm can be divided into three nested iterations. In outermost iterations, we enable the vehicles to coordinate with each other to decide who will make a detour around the congested resource nodes, until all the congestions are resolved to obtain a complete legal control solution. In middle iterations, the sequential control loop starts at step 3. The vehicle routing path *RP** _{i }*from the previous outermost iterations is ripped-up and initialized to the vehicle source. and at the meanwhile, it will invoke the shortest-path algorithm, which computes a path from the source to the sink in the network resource graph. In innermost iterations, it employs the single source shortest path algorithm, which is implemented by Dijkstra’s algorithm. After a sink is found, all nodes along a backtraced path from the sink to source are added to

*RP*

*, and at last, if the solution is feasible, the algorithm is complete.*

_{i}Specifically, the length of the points chosen by this global control algorithm is a challenge problem. However, finding the optimal or even near-optimal points is not essential in this algorithm. The key of algorithm is successfully feasible in adjusting costs to eliminate the congestion between vehicles to route itself on a road with a safety guarantee.

# D. Negotiation-Congestion Example

Here we give a example which leverages the history and present costs to reduce the congestion. We show a very simple case, where two vehicle iteratively negotiates with each other until to find a feasible solution.

(a) Routing graph (b) Routing paths

Fig. 2. Initial iteration, routed with base cost.

(c) Penalized by present (d) Control the vehilce 2

congestion cost routing

Fig. 3. Second iteration, negotiation-congestion scheme.

Fig. 2(a) shows that vehicles 1 and 2 need to be controlled to route their source *S*1 and *S*2 to their respective sinks *D*1 and *D*2. The dot line in the graph represent partial paths with the associated costs. Ignoring congestion, the minimum cost path for each vehicle would use node *A *as shown in Fig. 2(b). If a simple congestion avoidance routing scheme is used, the order in which the vehicles are routed becomes important. Some orderings will not be successfully routed. Moreover, the total routing cost will be a minimum only if we start with vehicle 2. Our algorithm is not sensitive to the ordering and easy to find the feasible solution.

Fig. 3 shows that this control algorithm imposes the penalty into the congestion node in the subsequent iterations. With the negotiation-congestion scheme, each vehicle is controlled to find feasible routing path, respectively. With the routing iteration proceeds, the history cost is increased slightly and the present cost is gradually increased depending on how many vehicles share the congestion node. This negotiation scheme for routing resources depends on a relatively gradual increase in the cost of sharing nodes. And this scheme ensure that each vehicle can find a feasible routing path in smart vehicular systems.

From the example we see that we impose the cost penalty to iteratively route these vehicles to avoid the congestion. Thus, this case demonstrates the effectiveness to design a negotiation-based control approach to route the connected vehicles in large-scale vehicular systems.

V. CORRECTNESS AND CONVERGENCE

In this section, we formulate the negotiation paradigm as a conflict resolution method for bipartite matching to analyze the convergence and correctness of control approach.

# A. Modeling via Graph Matching

The problem to control the connected vehicles which can be modeled by a graph or hypergraph matching problem. Two sets of vertices are existed in the graph, *G** _{M }*= (

*X*∪

*Y,E*), and the edges (or hyperedges) connect one vertex in

*X*with one (or more) vertices in

*Y*. Here

*X*represents the vehicles to be routed and

*Y*is the set of routing resources. The edges of a vertex

*x*∈

*X*represent the subsets of resources that correspond to routing paths for the vehicles associated with

*x*. A solution is a subset of |

*X*| edges, exactly one edge for each

*x*∈

*X*, such that for each

*y*∈

*Y*no more than one of these edges includes

*y*. The former condition guarantees that each vehicle is assigned a routing path, and the latter condition ensures that there are no congested routing resources.

To model a control problem as a hypergraph matching problem, a hyperedge should be generated for each possible routing path of a vehicle. The number of different routing paths for a vehicle can easily be exponential in the size of graph. However, the negotiation paradigm does not require the explicit enumeration of all hyperedges. Moreover, it is also sufficient only to be able to identify the cheapest hyperedge for a given vehicle. Notice that this amounts to a shortest-path calculation in the negotiation congestion control scheme.

The hypergraph matching problem is a more general version of the three-dimensional matching problem and, thus, it is NPcomplete. In the remainder of this section, we provide the proof to guarantee that the negotiation-based control approach can converge on graphs under the different uses of fist-order present and second-order history congestion items and with or without delaying the history congestion updates to the end of the iterations. While there exists clearly better algorithms to solve the bipartite graph matching problem in polynomial time, these methods are not practical for our application due to they require the enumeration of all edges.

# B. Negotiation-Based Matching Algorithm

Given a bipartite graph *G** _{M }*= (

*X*∪

*Y,E*) with |

*X*| ≤ |

*Y*|, the objective is to find a matching which assigns an edge to each vertex in |

*X*|. The pseudocode for the negotiation-based matching (NM) algorithm is given in Algorithm 2.

The algorithm constructs an assignment *a *: *X *→ *Y *of *X *vertices to *Y *vertices. The number of *X *vertices currently assigned to a *Y *vertex is given by *n*(*y*) which captures the present congestion information. When *n*(*y*) *> *1, *y *is congestion and when *n*(*y*) = 0, *y *is open. A solution has been found when *a*() is 1 − 1; all *y *have *n*(*y*) ≤ 1. An initial assignment is given and each vertex *y *in *Y *has a base cost *cost*(*y*) which is incremented in between iterations if *y *is congestion at that point. In NC, this cost would initially be *d** _{y }*and with the algorithm progresses it would be

*d*

*+*

_{y }*h*

*. Here,*

_{y}*n*(

*y*) represents the present congestion information while

*cost*(

*y*) represents the history. In this NM version, the costs are only updated in between iterations. The effects of immediately updating the costs after an assignment is made, will be discussed in Section V-F.

Algorithm 2 The negotiation-based matching algorithm

1: NM(*a*()*,cost*()*,select*()*,reassign all*)

2: while ∃*y *∈ *Y *with *n*(*y*) *> *1 do

3: for *i *= 1 to |*x*| do

4: if *reassign all *or *n*(*a*(*x** _{i}*))

*>*1 then

5: *n*(*a*(*x** _{i}*)) ←

*n*(

*a*(

*x*

*)) − 1 6:*

_{i}*a*(

*x*

*) ← Select(*

_{i}*x*

*)*

_{i}7: *n*(*a*(*x** _{i}*)) ←

*n*(

*a*(

*x*

*)) + 1*

_{i}8: end if

9: end for

10: for each *y *∈ *Y *with *n*(*y*) *> *1 do

11: *cost*(*y*) ← *cost*(*y*) − 1

12: end for

13: end while

14: end NM

During each iteration seen from line 3 to 9 in Algorithm 2, the NM scheme uses one of two routines Select-Cheapest or Select-Open to determine which *Y *vertex is assigned to a given vertex in *X*. If boolean parameter *reassign all *is false, vertices of *X *assigned to currently non-congested *Y *vertices will be skipped, not reassigned. When *reassign **all *is false, this corresponds to this situation where only those vehicles that currently routing path has the congestion nodes with other vehicles are ripped up and rerouted. We assume that the vertices of *X *are ordered *X *= {*x*_{1}*,x*_{2}*,…,x*_{|}_{X}_{|}}.

The two routines in Algorithm 3 which determine the assignment for a given *X *vertex do not use (1) to select a vertex in *Y *. To facilitate the proofs, the cost function for assigning vertices has been simplified. However, the only important factors in determining convergence are whether the present and history congestion information are used and that the cost of congestion resources keep increasing with each iteration.

Algorithm 3 The pseudocode for two routines

1: Select-Cheapest(*x*)

2: *y** _{new }*←

*a*(

*x*)

3: for each *y *adjacent to *x *do

4: if cost(*y*) *< *cost(*y** _{new}*) then

5: *y** _{new }*←

*y*

6: end if

7: end for

8: return (*y** _{new}*) 9: end Select-Cheapest

10:

11: Select-Open(*x*)

12: *found open *← false

13: *y** _{new }*←

*a*(

*x*)

14: for each *y *adjacent to *x *do

15: if *n*(*y*) = 0 then

16: *found open *← true 17: iffalse or cost(*y*) *< *cost(*y** _{new}*) then

18:

19: end if

20: else if *found open *= false and cost(*y*) *< *cost(*y** _{new}*) then

21: *y** _{new }*←

*y*

22: end if

23: end for

24: return (*y** _{new}*)

25: end Select-Open

TABLE I

SUMMARY OF CONVERGENCE BEHAVIOR OF NM WITH ALL FOUR COMBINATIONS OF PARAMETERS

NM with | Select-Open | Select-Cheapest |

reassign all = true |
converge | not converge |

reassign all = false |
converge | converge |

Select-Open will always select an open vertex (*n*(*y*) = 0) over a used vertex (*n*(*y*) ≥ 1), and uses *cost*(*y*) to choose among the open vertices or occupied vertices if there are no open ones. Select-Cheapest selects a *Y *vertex only on the basis of *cost*(*y*). Thus, Select-Cheapest is not using the present congestion information. In either case, it is assumed that ties are broken consistently. That is, there is an underlying order on the neighbors of each vertex used to break ties. In our discussion, two *Y *vertices adjacent to an *X *vertex never have the same cost since the tie breaking order determines the cheapest.

# C. Convergence Behavior of Negotiation Paradigm

If the NM algorithm terminates, then the final mapping *a*() is a solution. The NM is said to converge if it always terminates when a solution exists. Table I summarizes the results in this paper on the convergence behavior of NM on graphs. Its convergence depends on the selection routine and the use of *reassign all*.

To show that NM converges we show that no solution exists if it does not terminate.

DEFINITION 1. A vertex in *Y *currently with *n*(*y*) = 0 is said to be *open *and otherwise *used*. A vertex in *Y *currently with *n*(*y*) ≥ 1 is said to be *congested*.

During the course of the algorithm, a vertex can change its status between open, used, and congested. The next two definitions are properties of vertices which do not change.

DEFINITION 2. A vertex of *Y *is said to be *profoundly congested *if it is congested at the end of an infinite number of iterations.

Since all congested vertices that vertices with *n*(*y*) *> *1 have their costs increased at the end of an iteration, the cost of a profoundly congested vertex is unbounded.

DEFINITION 3. A vertex *y *∈ *Y *is said to be *stable *if *a*^{−1}(*y*) remains constant and *n*(*y*) ≤ 1 after some finite number of iterations. That is, either no *X *vertex is ever again assigned to *y *or the vertex *x *is assigned to *y *from that point on and no other vertex is ever assigned to *y *from that point on; *y *becomes *fixed*. Otherwise the vertex is said to be *unstable*.

By definition if the NM algorithm terminates, then no vertex is profoundly congested and all vertices are stable. Thus these two definitions are only useful when NM scheme does not terminate. Clearly, a stable vertex is not profoundly congested although it might be congested in a finite number of times before its assignment becomes fixed. It is not immediate that an unstable vertex is profoundly congested, because of a vertex could temporarily have *n*(*y*) *> *1 during an iteration but be back to *n*(*y*) = 1 by the end of that iteration. However, we shall show that an unstable vertex must always be congested again at the end of some later iteration. We let *C *be the set of all profoundly congested vertices and *S *be the set of all stable vertices.

We prove that the NM scheme converges with *reassign all *= false in Section V-D, and that it converges with *reassign **all *= true using Select-Open in Section V-E.

# D. Convergence on Graphs Without Reassign All

In NM scheme with *reassign all *= false, a vertex *y *never changes its status from used to open. This is because only vertices with *n*(*y*) *> *1 can lose their assignees and only one at a time. Since used vertices can never become open, if the algorithm does not terminate, the number of open vertices stops decreasing at some point. The open vertices at this point become fixed and, hence, are stable. The first step in the convergence proof is to show that all *Y *vertices are either stable or profoundly congested.

LEMMA 1. In NM scheme with *reassign all *= false using either Select-Cheapest or Select-Open, if a vertex *y *∈ *Y *is not profoundly congested, then it is stable.

*Proof. *By contradiction.

Assume that there are unstable vertices which are not profoundly congested: *U *= *Y *−(*C*∪*S*) is not empty. Let *t *be an upper bound on the last iteration after which any vertex in *U *is never congested at the end of an iteration, and all vertices in *S *have become fixed.

Since vertices in *C *have costs which are unbounded while vertices in *U *have fixed costs after iteration *t*, there is an iteration *t*^{0 }after which the cost of any vertex in *C *will exceed the cost of any vertex in *Y *− *C*. At this point the algorithm will never reassign a vertex *x *with *a*(*x*) = *y *∈ *U *to a vertex of *C *since *C *vertices are never open after iteration *t*^{0 }and their costs will always exceed the costs of *U *vertices. After iteration *t *no more than one vertex can be reassigned to a given *y *∈ *U *within an iteration, since otherwise *y *would remain congested at the end of the iteration. So if within an iteration *x*_{1 }is assigned to vertex *y*_{1 }∈ *U*, then later in the same iteration the vertex previously assigned to *y*_{1 }must be moved to another *y*_{2 }∈ *U*, and the vertex previously assigned to *y*_{2 }must be moved to *y*_{3 }∈ *U *and so on. Eventually this chain must end, and it can only end if a second *x *is assigned to some vertex in *y** _{k }*∈

*U*. The other vertex assigned to

*y*

*at the start of the iteration will not be reassigned. However, this means that*

_{k }*y*

*will remain congested at the end of the iteration which contradicts the assumption that no vertex in*

_{k }*U*will have such a congestion after iteration

*t*.

Hence, it is not possible for unstable vertices not to be profoundly congested.

By Lemma 1 all *Y *vertices are either profoundly congested or stable. Let *T *be the iteration after which all stable vertices become fixed that no longer change their assignment, and the number of open vertices no longer decreases. Let *a** _{t}*(

*x*) denote the vertex assigned to

*x*at the end of iteration

*t*. Then for stable vertices

*y*we know that, for

*t*≥

*T,a*

^{−}

_{t }^{1}(

*y*) =

*a*

^{−}

_{T}^{1}(

*y*). Let

*X*

*= {*

_{S }*x*|

*x*∈

*a*

^{−}

_{T}^{1}(

*y*) for some

*y*∈

*S*}, the set of vertices permanently assigned to

*S*vertices after iteration

*T*. Let

*X*

*=*

_{C }*X*−

*X*

*be the other vertices of*

_{S }*X*, the profoundly congested vertices. No vertex in

*X*

*is ever assigned to a vertex in*

_{C }*S*after iteration

*T*, so they must all be assigned to vertices in

*C*by Lemma 1.

LEMMA 2. If NM scheme with *reassign all *= false using either Select-Cheapest or Select-Open does not terminate, then there is no edge between any *x *∈ *X** _{C }*and

*y*∈

*S*.

*Proof. *By contradiction.

Suppose there is an edge between *x *∈ *X** _{C }*and

*y*∈

*S*. Since

*x*∈

*X*

*, it is always assigned to a vertex in*

_{C}*C*after iteration

*T*. Some number of iterations after

*T*, say at iteration

*T*

^{0}, the cost of any vertex in

*C*will exceed the cost of any vertex in

*S*, because the cost of vertices in

*C*are unbounded while the costs of vertices in

*S*are fixed after iteration

*T*.

Suppose *a*(*x*) = *y *∈ *C *at iteration *T*^{0}. Since *y *is in *C *at some point another vertex *x*^{0 }will be reassigned to *y*. Let *x*^{0 }be the first such vertex. *x *is still assigned to *y *at this point since the algorithm will not move *x *until *n*(*y*) *> *1. There are two cases to consider depending on the ordering of *x *and *x*^{0}.

Case 1: *x *is first. Then *y *will still have both *x *and *x*^{0 }assigned to it at the start of the next iteration. Since *x *is processed first, *x*^{0 }will still be assigned to *y *and, hence, *n*(*y*) *> *1 when *x *is processed. Since *x *has an edge to a vertex in *S *and all vertices in *S *have smaller cost than *C *vertices, *x *will be reassigned to a vertex in *S*.

Case 2: *x*^{0 }is first. In this case *x*^{0 }will be moved to *y *and later in the same iteration *x *will be processed. Since *n*(*y*) *> *1 when *x *is processed, *x *will be reassigned to a vertex in *S*.

Both cases lead to the reassignment of *x *to a vertex in *S *after iteration *t *which is a contradiction.

THEOREM 1. *If NM scheme with reassign **all = false using either Select-Cheapest or Select-Open does not terminate, then the bipartite graph *(*X *∪ *Y,E*) *has no matching which contains an edge for each **x *∈ *X**.*

*Proof. *By Lemma 2 there is no edge from *X** _{C }*to

*S*. this means that all of the vertices of

*Y*incident on vertices of

*X*

*are in*

_{C }*C*:

*N*(

*X*

*) ⊆*

_{C}*C*. After iteration

*T*, a profoundly congested vertex is never open. All vertices in

*X*

*are assigned to*

_{C }*C*and there is always one vertex of

*C*with two or more vertices of

*X*

*assigned to it. It follows that |*

_{C }*X*

*|*

_{C}*>*|

*C*|. Then |

*X*

*|*

_{C}*>*|

*C*| ≥ |

*N*(

*X*

*)| which means that the bipartite graph (*

_{C}*X*∪

*Y,E*) has no matching with an edge for each vertex in

*X*

*and, hence,*

_{C }*X*.

# E. Convergence on Graphs With Reassign All

In NM scheme with *reassign all *= false, a vertex *y *never changes its status from used to open because only vertices with *n*(*y*) *> *1 are reassigned. This is still the case when *reassign all *= true, which means that all vertices of are processed, but it now requires a proof and an assumption on how vertices are initially assigned.

DEFINITION 4. An assignment *a*() : *X *→ *Y *is minimal if for each vertex *x *∈ *X*, none of the open neighbors of *x *are cheaper than *a*(*x*).

An initial minimal assignment can be constructed by assigning each *X *vertex to its cheapest neighbor regardless of its occupancy. This is what happens in negotiation-based control algorithm.

LEMMA 3. If NM scheme with *reassign all *= true using Select-Open starts with a minimal assignment, then no vertex in *Y *ever changes its status from used to open.

*Proof. *By contradiction.

Suppose there is a vertex *y *∈ *Y *which changes its status from used to open at some point during the course of the algorithm. Let *y *be the first vertex to become open. This means that in some iteration *t*, we have *a*(*x*) = *y *and *n*(*y*) = 1 when vertex *x *is processed and after *x *is processed *a*(*x*) = *y*^{0 }and *n*(*y*) = 0. In order for *x *to switch from *y *to *y*^{0}, we must have *n*(*y*^{0}) = 0 before *x *is processed and *cost*(*y*^{0}) *< cost*(*y*). Since *y *is the first vertex to become open, *y*^{0 }must have been open in the initial assignment and remained open up till this point.

Case 1: *x *switched from *y *to *y*^{0 }in the first iteration (*t *= 1). In order for the switch to occur in the first iteration, the base cost function would have to satisfy *cost*(*y*) *> cost*(*y*^{0}). However, this contradicts the assumption that the initial assignment is minimal since *y*^{0 }is open in the initial assignment.

Case 2: *x *switched from *y *to *y*^{0 }in the second or later iteration (*t > *1). Since *x *was assigned to *y *rather than *y*^{0 }in iteration *t *− 1, it must have been the case that *cost*(*y*) *< cost*(*y*^{0}) in iteration *t*−1. Since *cost*(*y*) *> cost*(*y*^{0}) in iteration *t*, the cost of *y *must have increased at the end of iteration *t*−1, which means that *y *was congested at the end of iteration *t*−1. We know *x *was one of the vertices assigned to *y *at the end of iteration *t*−1. Let *x*^{0 }be any other vertex assigned to *y *at the end of iteration *t *− 1. Since *x *is the last one to be removed from *y *in iteration *t*, *x*^{0 }must precede *x *in the processing order. However, then *x*^{0 }was already assigned to *y *in iteration *t *− 1, and at the time, *x *was processed. Under Select-Open, *x *is assigned to *y *rather than to *y*^{0 }only if *y*^{0 }was not open in iteration *t*−1. This contradicts the fact that *y*^{0 }has been open since the start of the algorithm.

Since either case leads to a contradiction, it follows that no vertex can become open if NM scheme uses Select-Open and starts with a minimal assignment.

After establishing that vertices do not become open, the convergence of NM scheme can be shown in exactly the same manner for *reassign all *= true as for *reassign all *= false. Lemma 2 and Theorem 1 hold.

# F. Immediate Update of History Costs

The negotiated-congestion based method employed by NC scheme updates the history costs of the vehicles after each vehicle is routed rather than waiting until the end of the iteration. As a result the cost of a *Y *vertex increases by the number of vehicles assigned to that vertex within an iteration minus one, rather than just by one if the vertex remains congested. Not only do the history costs rise more rapidly in proportion to the demand for a *Y *vertex, but also the cost changes affect other assignments within the same iteration. Experimentally immediate update of the history costs appears to decrease the number of iterations required for finding a solution.

In showing that using immediate update of the history costs still results in convergence, we modify the definition of profoundly congested to include vertices, which are congested as a result of an infinite number of assignments rather than only at iteration boundaries. These are now the vertices that have unbounded costs during the course of the algorithm. In this case it is much easier to see that all unstable vertices are profoundly congested. A vertex *y *∈ *Y *cannot change its assignment without either becoming open (impossible with *reassign all *= false or by Lemma 3 for *reassign all *=true) or becoming congested. The proofs for Lemma 2 and Theorem 1 can then be adapted to cover this case.

# G. Implications for NC Scheme

Although the NC scheme will not always converge, the convergence properties of NM scheme on graphs identify the following factors which affect the convergence of NC scheme.

- The vehicles should be examined in a fixed order in each iteration.
- The history costs may either be updated immediately after a vehicle is rerouted or only at the end of the iteration.
- The history costs updates may be proportional to the number of vehicles occupying a node, or simply constant.
- The present information must be updated within an iteration and may be used either to select assignments, determine which vehicles should be rerouted, or both.

In this section We analyze in-depth the convergence of the negotiation-based control approach by modeling it as a conflict resolution method for bipartite matching. We also present results on the convergence of the negotiation-based conflict resolution method for graphs, and show that it will not always converge for hypergraphs. Nevertheless, our provide useful guidelines to design a negotiation-based control approach for large-scale connected vehicles.

VI. EVALUATION

In this section we provide simulation results and evaluate the performance of the negotiation-congestion control approach for large-scale connected vehicles.

# A. Experimental Setup

The negotiation-based control approach was implemented in the C++ programming language on a Intel Xeon E5-2430 processor at 2.2GHz and 32GB memory. We first conduct extensive simulations based on a San Francisco taxi data set [22]. The information for every record includes the number of vehicles, the start and end points of trip information, and the GPS coordinators of locations, as summarized in Table II. Moreover, the ground traffic network of San Francisco city can be formulated into a routing resource graph, which contains 321,270 nodes and 800,172 edges. Our algorithm can be executed on this real graph while it is small scale.

TABLE II

SAN FRANCISCO TAXI DATA SET

Name | Vehicles | Trip Information | Trip Locations |

Record | 500 | Start and end points | GPS coordinates |

To evaluate the performance of negotiation-based control approach for lager-scale connected vehicles. The extra simulation study and the experimental campaign were conducted on ten large-scale test cases, all of which are extracted from the ground traffic network of the California state (*i.e.*, about 1,965,206 nodes and 2,766,607 links) [23]. Because there are no available free data sets about the road segment length, trip information, and current traffic conditions as previously discussed, we implemented a random algorithm to produce these information, including the number of vehicles with different origin-destination pairs in the considered network. By this way, we can compute the feasible routing path for each vehicle in this routing resource graph while it is synthetic.

TABLE III

ROAD NETWORK INFORMATION

Bench. | #Nodes | #Vehicles |

case1 | 27120 | 788 |

case2 | 76386 | 1946 |

case3 | 43872 | 2380 |

case4 | 104176 | 3710 |

case5 | 110250 | 3953 |

case6 | 283792 | 5224 |

case7 | 305082 | 6606 |

case8 | 283338 | 7154 |

case9 | 311112 | 7474 |

case10 | 492570 | 8078 |

Table. III shows the extracted ground traffic network benchmarks. Specifically, the size of road network is increased in a gradual manner, because the scalability of control algorithm is very crucial in the large-scale connected vehicles. In our simulation study, our mainly focus on the runtime and routing resource usage of control algorithm. In general, we leverage the number of nodes to evaluate the usage of road segment resources. Notice that our experimental methodology is to check whether the number of congestion nodes has stopped decreasing monotonically in the iteration procedure, because this is a sign whether the algorithm is having difficulty converging.

# B. Experimental Results

Fig. 4 shows the proportion of congestion nodes gradually decrease to zero with a limited number of iterations for real San Francisco dataset. The convergence time of control algorithm will take about 1.83 seconds to achieve a feasible solution for 500 connected vehicles. While we only present one real case here, we observe from our experiments very similar trends to Fig. 4 across a broad range of designs.

Fig. 4. Convergence with real case.

Fig. 5 gives the total runtime of control algorithm for each case of large-scale connected vehicles on ground traffic networks. The convergence time will take the average 258 seconds to achieve a feasible solution, which all vehicles can route itself on a road with a congestion-avoided guarantee. Specifically, our algorithm only takes about 5 seconds to find a practicable solution for the case1, it is close to a city scale. It is very meaningful for large-scale intelligent vehicular systems, which can be processed by region partitioning so that coordinated vehicles can parallel perform tasks in their specified regions to accelerate the runtime and improve the real-time.

Fig. 5. Runtime with large-scale cases.

To analyze the resource consumption, we impose an resource consumption ratio, which is between the total resource consumption of all vehicles and the available resource of ground traffic networks. Fig. 6 reports the probability distribution of the resource consumption ratio provided by proposed algorithm. On average, the resource consumption ratio is only about 29% using our negotiation-congestion framework to control such a large-scale connected vehicles. In particular, our algorithm only consumes about 10% resources to achieve a feasible solution for the case6. The proposed negotiation-based control framework has the potential to implement the resourceefficient control for the large-scale connected vehicles in intelligent vehicular systems.

Fig. 6. Resource consumption with large-scale cases.

VII. CONCLUSION AND FUTURE WORK

The control of connected vehicles is an important process in autonomous vehicular system. In this paper, we propose a

negotiation-based control approach for large-scale connected vehicles. Moreover, We provide some proofs to demonstrate the effectiveness of negotiation-congestion paradigm. Notably, system efficiency is maintained by minimizing the resource consumption and traffic safety is guaranteed by eliminating the vehicle congestion. While the control time is possibly length for very-large-scale connected vehicles, it is still practically meaningful for the autonomous transportation applications.

The future work is to leverage the parallelization techniques to accelerate this process to improve the ability of real-time control for large-scale connected vehicles.

REFERENCES

- M. Campbell, M. Egerstedt, J. How, and R. Murray. “Autonomous driving in urban environments: Approaches, lessons and challenges.” in the proceedings of the Philosophical Trans. on Royal Society, 2010.
- B. Templeton. “Traffic Congestion & Capacity.” in the websites of http:www.templetons.com/brad/robocars/congestion.html. 2015.
- M. Barnard. “Autonomous Cars Likely to Increase Congestion.” in the websites of http://cleantechnica.com/2016/01/17/autonomous-cars-likely-increase-congestion. 2016.
- K. Kim. “Collision free autonomous ground traffic: A model predictive control approach.” in the proceedings of the 4th ACM International Conference on CyberPhysical Systems (ICCPS), 2013.
- L. Kiet, K. Walid, and B. Alexandre. “On learning how players learn: Estimation of learning dynamics in the routing game.” in the proceedings of the 7th ACM International Conference on Cyber-Physical Systems (ICCPS), 2016.
- J. Tumova, S. Karaman, C. Belta, and D. Rus. “Least-violating planning in road networks from temporal logic specifications.” in the proceedings of the 7th ACM International Conference on Cyber-Physical Systems (ICCPS), 2016.
- R. Zhang and M. Pavone. “Control of robotic mobility-on-demand systems.” in the proceedings of the International Journal of Robotics Research, 2016.
- R. Zhang, F. Rossi, and M. Pavone. Model predictive control of autonomous mobility-on-demand systems. in the proceedings of the International Conference on Robotics and Automation (ICRA), 2016.
- B. Cheng, A. Rostami, and M. Gruteser. “Experience: accurate simulation of dense scenarios with hundreds of vehicular transmitters.” in the proceedings of the 22th annual international conference on Mobile computing & networking (MobiCom), 2016.
- F. Miao, S. Han, A. Hendawi, M. Khalefa, J. Stankovic, G. Pappas. “Data-driven distributionally robust vehicle balancing using dynamic region partitions.” in the proceedings of the 8th ACM International Conference on Cyber-Physical Systems (ICCPS), 2017.
- M. Lighthill and G. Whitham. “On kinematic waves. I. flood movement in long rivers.” in the proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 1955.
- B. Janson. “Dynamic traffic assignment for urban road networks.” in the proceedings of the Transportation Research Part B: Methodological, 1991.
- S. Peeta and H. Mahmassani. “System optimal and user equilibrium time-dependent traffic assignment in congested networks.” in the proceedings of the Annals of Operations Research, 1995.
- B. Kerner. “Introduction to modern traffic flow theory and control: the long road to three-phase traffic theory.” in the proceedings of the Springer Science & Business Media, 2009.
- M. Balmer, M. Rieser, K. Meister, D. Charypar, N. Lefebvre, K. Nagel, and K. Axhausen. “ATSim-T: Architecture and simulation times.” in the proceedings of the multi-agent systems for traffic and transportation engineering, 2009.
- C. Osorio and M. Bierlaire. “An analytic finite capacity queuing network model capturing the propagation of congestion and blocking.” in the proceedings of the European Journal of Operational Research, 2009.
- T. Le, P. Kov, N. Walton, H. Vu, L. Andrew, and S. Hoogendoorn. “Decentralized signal control for urban road networks.” in the proceedings of the Transportation Research Part C: Emerging Technologies, 2015.
- N. Xiao, E. Frazzoli, Y. Luo, Y. Li, Y. Wang, and D. Wang. “Throughput optimality of extended back-pressure traffic signal control algorithm.” in the proceedings of the 23th Mediterranean Conference on Control and Automation (MED), 2015.
- L. Chen and P. Chou. “A lane-level cooperative collision avoidance system based on vehicular sensor networks.” in the proceedings of the 19th annual international conference on Mobile computing & networking (MobiCom), 2013.
- D. Wilkie, J. Berg, M. Lin, and D. Manocha. “Self-Aware traffic route planning.” in the proceedings of the association for the Advancement of Artificial Intelligence (AAAI), 2011.
- R. Karp.
*Reducibility among combinatorial problems.*in Proc. Symp. Complex. Comput. Comput., pp. 85103, 1972. - M. Piorkowski, N. Djukic, and M. Grossglauser.
*A parsimonious model of mobile partitioned networks with clustering.*In the proceedings of the First International Communication Systems and Networks and Workshops (COMSNETS), 2009. - J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney.
*Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters.*in Internet Mathematics, 2009.