Multi-agent Approach to Resource Allocation in Autonomous Vehicle Fleets

1 Introduction

Our transport systems are changing rapidly due to technological developments like Artificial Intelligence and emerging communication technologies (e.g. 5G, LP-WAN protocols, and ITS-G5). Also, due to changing preferences of companies and customers, which highlights the need for customized On-Demand Transport (ODT) and Smart Mobility Systems. These new mobility solutions may have the capability to change the transportation domain fundamentally. For instance, ODT can lead to the transition from vehicle ownership to vehicle as a service, which reduces the number of vehicles. It can also increase transportation efficiency and thus reduce unnecessary movements. These potential benefits are claimed to have environmental, social, and economic impacts [EU TRAN Committee, 2020].

Developing autonomous vehicle fleets capable of peer-topeer communication, as well as the interest in on-demand solutions (e.g., Uber, Lyft, Heetch) are the primary motivations for this study. We are interested in setting up a fleet of autonomous vehicles capable of responding in the absence of central control to trip requests throughout a city.

The modeling and development of decentralized systems are well suited to the multi-agent domain [Bazzan and Kl¨ugl, 2014]. Therefore, vehicle allocation is a relevant application area for such techniques. On the other hand, centralizing the allocation process with an automatic dispatcher is still quite common in multi-agent approaches. [Maciejewski, 2014; Shen and Lopes, 2015].

2 Challenges and Research Questions

Allocation problems are major issues in the management of ODT systems. They have been studied for decades, and various solutions have been proposed.

Allocation objective trade-offs. In practice, centralizing or decentralizing the solving methods depends on the problem constraints and the environment's dynamics. However, even the most straightforward cases of resource allocation lead to debates on efficiency vs. fairness or privacy, business quality vs. user experience, and optimality vs. real-time feasibility.

Communication bottleneck. One of the main issues of multi-agent resource allocation approaches to solve ODT problems is the communication bottleneck. Developing decentralized solutions based on vehicle-to-vehicle interactions could be an essential source of savings and resilience.

Our objective is to define implementation guidelines and analytical methods to support the decisions on the choice of ODT solution methods in different settings. Using uniform representations of problem instances and so of their solutions allow the implementation of a generic multi-agent framework for comparing alternative methods to ODT problem variants. Then, analytical tools could be used for supporting decisions to choose solution methods in different contexts. We address four research questions (RQs) derived from this objective.

RQ1 How can we define a uniform representation of the different solution methods?

RQ2 How can we define a uniform representation of the vehicle communication model?

RQ3 How can we assess the feasibility and quality of solution methods?

RQ4 Can we combine efficiency, responsiveness, and conflict avoidance in one dynamic-setting solution method?

3 Contribution 1: AV-OLRAMetamodel

To tackle the modeling-related RQs, we introduce our generic model for online resource allocation problem with autonomous vehicles AV-OLRA [Daoud et al., 2021a]. This model defines the hypothesis of the problem (components, constraints) and the indicators to evaluate the different allocation strategies. We formulate the AV-OLRA problem as a tuple 〈R, V, G, T 〉; where the set of resources R defines a dynamic set of passenger requests; the fleet V of m autonomous vehicles defines the set of consumers; The graph G represents the urban road network and T defines the time horizon within which vehicles must respond to passenger requests. Connectivity between two components in the system is achieved by direct messages within limited communication ranges. To maximize their connectivity, two vehicles vi and vj are connected transitively if there exists vk that is connected directly or transitively to both of them. This leads to the definition of connected sets as dynamic sets of entities connected to each other directly or by transitivity.

We also propose a generic multi-agent model for solution methods to AV-OLRA problem instances. We can distinguish three different sub-behaviors of Autonomous Vehicle (AV) agents: (acting, communicating, and planning). A solution method is defined by its coordination mechanism, which is characterized by three components 〈DA, AC, AM〉. DA denotes the level of decision autonomy which is either centralized (C) or decentralized (D); AC indicates the agents' cooperativeness level with (S) or without sharing (N) of schedule information, and AM is the allocation mechanism. We instantiate our generic model to implement coordination mechanisms from the literature, like: classical selfish behavior 〈D, N, Greedy〉, centralized dispatching 〈C, S, MILP〉, cooperative team using DCOP to coordinate 〈D, S,DCOP〉, and auction-based allocation 〈D, S, Auction〉.

4 Contribution 2: ORNInA

This contribution tackles the fourth RQ. Starting from a feasible, not optimal solution, we present a new coordination mechanism (ORNInA) consisting of two parallel coordination processes [Daoud et al., 2021b]. The first one is a decentralized insertion-heuristic-based algorithm to build vehicle schedules to solve ODT problem instances. The second coordination scheme is a continuous optimization process, namely Pull-demand protocol, based on auctions, in order to improve the quality of the global solution achieved by decentralized decision at run-time by exchanging resources between vehicles (k-opt). In its most straightforward implementation, k = 1 so that vehicles can exchange only one resource at a time. We show through examples that the request exchange protocol can be a promising improvement in the quality of the solutions. To assess the feasibility of the proposed protocol, we evaluated our technique's results on synthetic data for taxis operating in the city of Saint- ´Etienne. We showed that it outperforms a classical greedy approach. Moreover, compared to classical centralized MILP-based solvers (computing the optimal allocation either at each simulation step or at each connected set update), ORNInA provides very good quality results on both QoB and QoS while following fully decentralized decision-making.

5 Conclusion and Future Directions

This document summarizes the main challenges and research questions that we consider for resource allocation problems in ODT systems. Focusing on the instances that use autonomous vehicles with a limited communication range, we introduced our two contributions to tackle these challenges; the first is a meta-model for the problem and a multi-agent generic model for solution methods. The second is a solution method that quickly achieves a feasible solution, then tries to optimize it at run-time. We plan to explore the direction of defining further constraints on vehicle motion to achieve more connectivity between vehicles or to ensure that each emission source is located within the communication space of at least one vehicle. We also plan to analyze in-depth the relationship between stability, completeness, and feasibility of the solutions with and without prior knowledge of the request announcement and how this knowledge could affect the solution quality. Furthermore, we need to implement more sustained approaches of different types and explore the direction of machine learning spatio-temporal prediction models. Once implemented, we will be able to systematically compare performance, quality, feasibility, stability, and technical issues for these approaches' practical application.