New Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning

2022-07-19 · Dimitri Bertsekas

We consider some classical optimization problems in path planning and network transport, and we introduce new auction-based algorithms for their optimal and suboptimal solution. The algorithms are based on mathematical ideas that are related to competitive bidding by persons for objects and the attendant market equilibrium, which underlie auction processes. However, the starting point of our algorithms is different, namely weighted and unweighted path construction in directed graphs, rather than assignment of persons to objects. The new algorithms have several potential advantages over existing methods: they are empirically faster in some important contexts, such as max-flow, they are well-suited for on-line replanning, and they can be adapted to distributed asynchronous operation. Moreover, they allow arbitrary initial prices, without complementary slackness restrictions, and thus are better-suited to take advantage of reinforcement learning methods that use off-line training with data, as well as on-line training during real-time operation. The new algorithms may also find use in reinforcement learning contexts involving approximation, such as multistep lookahead and tree search schemes, and/or rollout algorithms.

📄 PDF Abstract BibTeX arXiv:2207.09588

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Collaborative vehicle routing: a survey

2017-06-13 · Margaretha Gansterer, Richard F. Hartl

In horizontal collaborations, carriers form coalitions in order to perform parts of their logistics operations jointly. By exchanging transportation requests among each other, they can operate more efficiently and in a m…

Survey

Deep Reinforcement Learning Based Dynamic Route Planning for Minimizing Travel Time

2020-11-03 · Yuanzhe Geng, Erwu Liu, Rui Wang, Yiming Liu

Route planning is important in transportation. Existing works focus on finding the shortest path solution or using metrics such as safety and energy consumption to determine the planning. It is noted that most of these s…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)

An Auction-based Coordination Strategy for Task-Constrained Multi-Agent Stochastic Planning with Submodular Rewards

2022-12-30 · Ruifan Liu, Hyo-Sang Shin, Binbin Yan, Antonios Tsourdos

In many domains such as transportation and logistics, search and rescue, or cooperative surveillance, tasks are pending to be allocated with the consideration of possible execution uncertainties. Existing task coordinati…

Approximating Auction Equilibria with Reinforcement Learning

2024-10-17 · Pranjal Rawat

Traditional methods for computing equilibria in auctions become computationally intractable as auction complexity increases, particularly in multi-item and dynamic auctions. This paper introduces a self-play based reinfo…

reinforcement-learning Reinforcement Learning

Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning

2024-02-29 · Greg d'Eon, Neil Newman, Kevin Leyton-Brown

Iterative combinatorial auctions are widely used in high stakes settings such as spectrum auctions. Such auctions can be hard to analyze, making it difficult for bidders to determine how to behave and for designers to op…

Multi-agent Reinforcement Learning Navigate reinforcement-learning Reinforcement Learning