	This paper proposes AlphaRoute, an AlphaGo inspired algorithm for coordinating large-scale routes, built upon graph attention reinforcement learning and Monte Carlo Tree Search (MCTS). We first partition the road network into regions and model large-scale coordinated route planning as a Markov game, where each partitioned region is treated as a player instead of each driver. Then, AlphaRoute applies a bilevel optimization framework, consisting of several region planners and a global planner, where the region planner coordinates the route choices for vehicles located in the region and generates several strategies, and the global planner evaluates the combination of strategies. 
	AlphaRoute is built on graph  attention network for evaluating each state  and MCTS algorithm for dynamically visiting and simulating the future state for narrowing down the search space. AlphaRoute is capable of 1) bridging user fairness and system efficiency, 2) achieving higher search efficiency by alleviating the curse of dimensionality problems, and 3) making an effective and informed route planning by simulating over the future to capture traffic dynamics. 
	Comprehensive experiments are conducted on two real-world road networks as compared with several baselines to evaluate the performance, and results show that AlphaRoute achieves the lowest travel time, and is efficient and effective for coordinating large-scale routes and alleviating the traffic congestion problem. The code will be publicly available.

AlphaRoute: Large-Scale Coordinated Route Planning via Monte Carlo Tree Search

Smoothed online combinatorial optimization considers a learner who repeatedly chooses a combinatorial decision to minimize an unknown changing cost function with a penalty on switching decisions in consecutive rounds. We study smoothed online combinatorial optimization problems when an imperfect predictive model is available, where the model can forecast the future cost functions with uncertainty. We show that using predictions to plan for a finite time horizon leads to regret dependent on the total predictive uncertainty and an additional switching cost. This observation suggests choosing a suitable planning window to balance between uncertainty and switching cost, which leads to an online algorithm with guarantees on the upper and lower bounds of the cumulative regret. Empirically, our algorithm shows a significant improvement in cumulative regret compared to other baselines in synthetic online distributed streaming problems.

Smoothed Online Combinatorial Optimization Using Imperfect Predictions

We introduce the multi-agent transportation (MAT) problem, where agents have to transport containers from their starting positions to their designated goal positions.  Movement takes place in a common environment where collisions between agents and between containers must be avoided.
In contrast to other frameworks such as multi-agent pathfinding (MAPF) or multi-agent pickup and delivery (MAPD), the agents are allowed to separate from the containers at any time, which can reduce the makespan and also allows for plans in scenarios that are unsolvable otherwise.
We present a complexity analysis establishing the problem's NP-completeness and show how the problem can be reduced to a sequence of SAT problems when optimizing for makespan.
A MAT solver is empirically evaluated with regard to varying input characteristics and movement constraints and compared to a MAPD solver that utilizes conflict-based search (CBS).

The Multi-Agent Transportation Problem

Sharing scarce resources is a key challenge in multi-agent interaction, especially when individual agents are uncertain about their future consumption.  We present a new auction mechanism for preallocating multi-unit resources among agents, while limiting the chance of resource violations. By planning for a chance constraint, we strike a balance between worst-case approaches, which under-utilise resources, and expected-case approaches, which lack formal guarantees. We also present an algorithm that allows agents to generate bids to submit to the auction with the use of multi-objective reasoning. We then discuss how the auction can be extended to non-cooperative scenarios. Finally, we demonstrate empirically that our auction outperforms state-of-the-art techniques for chance-constrained multi-agent resource allocation in complex settings with up to hundreds of agents. 

Multi-Unit Auctions for Allocating Chance-Constrained Resources

We study fully dynamic online selection problems in an adversarial/stochastic setting that includes Bayesian online selection, prophet inequalities, posted price mechanisms, and stochastic probing problems subject to combinatorial constraints.   In the classical ``incremental'' version of the problem, selected elements remain active until the end of the input sequence. On the other hand, in the fully dynamic version of the problem, elements stay active for a limited time interval, and then leave. This models, for example, the online matching of tasks to workers with task/worker-dependent working times, and sequential posted pricing of perishable goods. A successful approach to online selection problems in the adversarial setting is given by the notion of  Online Contention Resolution Scheme (OCRS), that uses  a priori information to formulate a linear relaxation of the underlying optimization problem, whose optimal fractional solution is rounded online for any adversarial order of the input sequence. Our main contribution is providing a general method for constructing an OCRS for fully dynamic online selection problems. Then, we show how to employ such OCRS to construct no-regret algorithms in a partial information model with semi-bandit feedback and adversarial inputs. 

Fully Dynamic Online Selection through Online Contention Resolution Schemes

A central computational problem in the realm of automata theory is the problem of determining whether a finite automaton A has a synchronizing word. This problem has found applications in a variety of subfields of artificial intelligence, such as robotics, game theory, and the theory of multi-agent systems. In this work, we study this problem within the framework of diversity of solutions, an up-and-coming trend in the field of artificial intelligence where the goal is to compute a set of solutions that are sufficiently distinct from one another. In our
work, the language L is specified by a finite automaton B given at the input. First, we define a notion of diversity of solutions that is suitable to the context of synchronization. Subsequently, we show that for each fixed r ∈ N, each fixed finite automaton A, and each finite automaton B given at the input, the problem of determining the existence of a diverse set {w_1 , w_2 , . . . , w_r } ⊆ L(B) of words that are synchronizing for A can be solved in polynomial time. This result yields new applications of the notion of synchronization to the subfields of artificial intelligence mentioned above.

Synchronization and Diversity of Solutions

We consider the problem of large-scale Fisher market equilibrium computation through scalable first-order optimization methods. It is well-known that market equilibria can be captured using structured convex programs such as the Eisenberg-Gale and Shmyrev convex programs. Highly performant deterministic full-gradient first-order methods have been developed for these programs. In this paper, we develop new block-coordinate first-order methods for computing Fisher market equilibria, and show that these methods have interpretations as tâtonnement-style or proportional response-style dynamics where either buyers or items show up one at a time. We reformulate these convex programs and solve them using proximal block coordinate descent methods, a class of methods that update only a small number of coordinates of the decision variable in each iteration. Leveraging recent advances in the convergence analysis of these methods and structures of the equilibrium-capturing convex programs, we establish fast convergence rates of these methods. 

Fast and Interpretable Dynamics for Fisher Markets via Block-Coordinate Updates

Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. In such games, agents maximize their utility by choosing strategies (i.e., actions) that differ from their neighbors’ strategies. Two important problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time of the dynamics. In this work, we study these two problems for anti-coordination games under sequential and synchronous dynamics. For each type of dynamics, we examine two decision-making modes based on whether an agent considers its own previous action (self essential mode) or not (self non-essential mode) in choosing its next action. Using a relationship between anti-coordination games and discrete graphical dynamical systems, we show that for both forms of dynamics, finding an NE can be done efficiently for the self non-essential mode but is computationally intractable under the self essential mode. To cope with this hardness, we identify some special cases for which an NE can be found efficiently, and present the corresponding algorithms. With respect to convergence time, we show that the dynamics converges in a polynomial number of steps in the synchronous case for both modes; for the sequential case, the convergence time is polynomial only for the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.

Networked Anti-Coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence

Applications such as employees sharing office spaces over
a workweek can be modeled as problems where agents are
matched to resources over multiple rounds. Agents’ require-
ments limit the set of compatible resources and the rounds in
which they want to be matched. Viewing such an application
as a multi-round matching problem on a bipartite compati-
bility graph between agents and resources, we show that a
solution can be found efficiently if one exists. To cope with
situations where a solution does not exist, we consider two
extensions. In the first extension, a benefit function is defined
for each agent and the objective is to find a solution to maxi-
mize the total benefit. For a general class of benefit functions
satisfying certain properties (including diminishing returns),
we show that this multi-round matching problem is efficiently
solvable. This class includes utilitarian and Rawlsian wel-
fare functions. For another benefit function, we show that the
maximization problem is NP-hard. In the second extension,
the objective is to generate advice to each agent (i.e., a subset
of requirements to be relaxed) subject to a budget constraint
so that the agent can be matched. We show that this budget-
constrained advice generation problem is NP-hard. For this
problem, we develop an integer linear programming formu-
lation as well as a heuristic based on local search. We exper-
imentally evaluate our algorithms on synthetic networks and
apply them to two real-world situations: shared office spaces
and matching courses to classrooms.

Resource Sharing Through Multi-Round Matchings

Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1-o(1)) ln k)-approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our problem to submodular objective functions and Matroid rank constraints.

Multiagent MST Cover: Pleasing All Optimally via A Simple Voting Rule

We study the online Traveling Salesman Problem (TSP) on the line augmented with machine-learned predictions. In the classical problem, there is a stream of requests released over time along the real line. The goal is to minimize the makespan of the algorithm. We distinguish between the open variant and the closed one, in which we additionally require the algorithm to return to the origin after serving all requests. The state of the art is a 1.64-competitive algorithm and a 2.04-competitive algorithm for the closed and open variants, respectively. In both cases, a tight lower bound is known.

In both variants, our primary prediction model involves predicted positions of the requests. We introduce algorithms that (i) obtain a tight 1.5 competitive ratio for the closed variant and a 1.66 competitive ratio for the open variant in the case of perfect predictions, (ii) are robust against unbounded prediction error, and (iii) are smooth, i.e., their performance degrades gracefully as the prediction error increases.

Moreover, we further investigate the learning-augmented setting in the open variant by additionally considering a prediction for the last request served by the optimal offline algorithm. Our algorithm for this enhanced setting obtains a 1.33 competitive ratio with perfect predictions while also being smooth and robust, beating the lower bound of 1.44 we show for our original prediction setting for the open variant. Also, we provide a lower bound of 1.25 for this enhanced setting.

Learning-Augmented Algorithms for Online TSP on the Line

Vaccine delivery in under-resourced locations with security
risks is not just challenging but also life threatening. The
COVID pandemic and the need to vaccinate added even more
urgency to this issue. Motivated by this problem, we propose
a general framework to set-up limited temporary (vaccination)
centers that balance physical security and desired (vaccine)
service coverage with limited resources. We set-up the
problem as a Stackelberg game between the centers operator
(defender) and an adversary, where the set of centers is not
fixed a priori but is part of the decision output. This results in
a mixed combinatorial and continuous optimization problem.
As part of our scalable approximation solution, we provide a
fundamental contribution by identifying general duality conditions
of switching max and min when both discrete and continuous
variables are involved. Via detailed experiments, we
show that the solution proposed is scalable in practice.

Underline digital video library

AlphaRoute: Large-Scale Coordinated Route Planning via Monte Carlo Tree Search

Smoothed Online Combinatorial Optimization Using Imperfect Predictions

The Multi-Agent Transportation Problem

Multi-Unit Auctions for Allocating Chance-Constrained Resources

Fully Dynamic Online Selection through Online Contention Resolution Schemes

Synchronization and Diversity of Solutions

Fast and Interpretable Dynamics for Fisher Markets via Block-Coordinate Updates

Networked Anti-Coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence

Resource Sharing Through Multi-Round Matchings

Multiagent MST Cover: Pleasing All Optimally via A Simple Voting Rule

Learning-Augmented Algorithms for Online TSP on the Line

Securing Lifelines: Safe Delivery of Critical Services in Areas with Volatile Security Situation via a Stackelberg Game Approach

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES