Sequential Online Chore Division for Autonomous Vehicle Convoy Formation
Birds do it. Cyclists do it. Why shouldn’t vehicles?
Using a combination of sensors and communication, vehicles can follow each other closely by synchronizing braking and accelerating.
Forming a convoy can result in up to 12% energy saving for the followers due to lower wind resistance.
Currently this technology is applied mostly to truck fleets where agents are not self-interested.
In order to enable spontaneous, ad-hoc convoys of differently owned vehicles, we need to find a way to equally share the gains of the followers with the leader.
We need to divide the chore of leading in a fair way.
Chore division is the dual problem of cake cutting, in which an undesirable resource must be fairly divided among agents.
But, what is a fair division?
Convoy formation is representative of a novel variation of chore division called Sequential Online Chore-division (SOCD for short):
· Where an ongoing task must be divided among agents
· The agents arrive online, and their number is not known a-priori (Online)
· Only one agent can handle the chore at any given time (Sequential)
· Every available agent, except for the active one, gains a positive utility
per unit of time
· If no agent performs the chore then none of them gain any utility
· A switch of the active agent results in a cost
incurred by the outgoing agent
SOCD can model applications such as:
Assigning a guard at a campground where travelers arrive online, or
Assigning a goal keeper in a drop-in soccer match.
In this project, we focus on convoy formation due to its social impact.
Convoy Formation can be modeled as an SOCD problem where the leading agent in the convoy is the active agent in the SOCD model, and the chore to be divided is leading the convoy.
Our goal is to Find a mechanism that produces an online assignment of one active agent at any given time, while maximizing both fairness and efficiency.
We also analyze whether the solution is strategyproof and not prone to manipulation.
In the dynamic SOCD model, we need to define what is a fair allocation.
We introduce two definitions for a proportional share of agent ai:
Ex-ante proportional share — is the relative share of the time with existing agents at ai’s arrival.
Ex-post proportional share — The relative share of the time with all available agents during ai’s availability period, both existing and future arrivals.
In the paper we prove that In SOCD, no mechanism can guarantee ex-post proportionality for a single game, in a distributed setting.
We propose three fair-division mechanisms to balance the load of the leader and equally share the energy savings of the followers among all the convoy’s participants.
The Payment Transfer mechanism assumes the existence of a central payment transfer system, and achieves optimal efficiency and fairness.
The Repeated Game Load Balancing mechanism does not rely on a central payment system, yet offers optimal efficiency and fairness in expectation, after participating in multiple repeated games.
The Single Game Load Balancing mechanism is also distributed, and is able to achieve ex-ante-proportionality, the highest attainable fairness criterion for a single game, with a minimal number of switches.
This paper’s contribution is twofold. First, in the area of fair division, it defines the general SOCD model, and second, in the area of convoy formation and platooning it introduces mechanisms that enable spontaneous formation of ad-hoc heterogeneous convoys while maintaining fairness and efficiency.
A link to the full paper can be found here:
http://www.agent-games-2020.preflib.org/wp-content/uploads/2020/05/Convoy-aamas20-GAIW1.pdf
