06 May

Delta Tolling for Improved Route Planning

Pehuen Moure reinforcement learning multi-agent path planning marginal cost pricing delta tolling

Delta-Tolling in Grid-Based Multiagent Systems

For a single agent, the problem of warehouse navigation can be considered a simplistic path finding problem over a gridworld environment. With multiple agents existing and acting in this environment, however, the problem of coordinating actions over all agents becomes more difficult. In order to learn the optimal sequence of actions to reach their individual goals, agents must also learn to plan around the actions of others in order to avoid deadlock. This problem is exacerbated in environment configurations prone to congestion.

This problem of multi-agent pathfinding can be framed as a traffic flow problem in which the delta-tolling framework introduced in [1] can be applied. Under this framework, the environment is characterized by a directed, weighted graph where the goal of each agent is to traverse from its current vertex to some other vertex via a least cost path. Each edge in the graph is associated with a latency l representing the travel time over that edge and a toll t which is a dynamic value estimating cost of traversing that edge. Delta-tolling is a model free method of evaluating marginal-cost tolling (charging each agent a cost equivalent to the cost it inflicts on all other agents) which requires only the latency on each edge and requires no internal traffic model [1]. Delta-tolling is parameterized only by a proportionality constant beta, and a smoothing parameter R. In each iteration, the toll of each edge is updated as the weighted average of the current toll and the difference between the observed and freeflow latencies. The weight assigned to each is dependent on R.

The multi-agent warehouse pathfinding problem can be framed as a degenerate case of this delta-tolling framework. In transforming this gridworld environment into a traffic flow network such as those used in delta-tolling, we construct a graph with vertices represented by reachable (i.e. non-obstacle) states and edges represented by actions that allow agents to transition between these reachable states. In this graph, edges will only be associated with latencies of 0 or 1 representing that the state into which the agent is transitioning is either obstructed or unobstructed respectively. The freeflow latency of each edge in this graph is 1 since only one agent can occupy a state at a given time.

References:

  1. Ramos et al., 2018, Learning System-Efficient Equilibria in Route Choice Using Tolls

  2. Mirzaei et al., 2018, Enhanced Delta-tolling: Traffic Optimization via Policy Gradient Reinforcement Learning

Next Post Previous Post

Search

Popular Tags

foray origami robots blimp ducky vr edg SLAM computer vision computational design roco slam Origami rocolib arduino RoCo design Robot Compiler simulation Motion Planning autonomy edg-model mesh reinforcement learning; multi-agent; mean-field; logics create; kalman filter; motors imu friction mesh network tank esp32 networking contacts multi-agent pushing auxetic machine learning dynamics esp now visual processing wireless control communication webapp pcbs structure ROCO i2c path planning cars Robotica reinforcement learning computer skill openmv test motor dataset visual DARPA odometry Battery surface structure power consumption dash port-arrays modeling origami paper frequency diversity semantic infrastructure auxetics feedback gondola machine vision Consensus bistable auxetic controller gestural intuition mixed reality unit cell robot crawler gestural interface open house network create; kalman filter; EM; refactoring 4-wheeled darpa; create; icra2021 apriltags lidar logic control FORAY perception Quantum Information crazyflie 433mhz optimization propeller Foray structures sensors environmental design radio DER Kullback-Leibler Divergence lasercutter tutorial von Mises Fisher Distribution IR simulink legs project management localization distributed optimization blynk Auxetics painlessmesh experiment results offline reinforcement learning exam research proposal altimeter thrust PCB sensor fusion gate or webots multi-agent path planning UAV RL integration test arnhold joystick balloon test vision processing pushing problem modeling contacts mesh networking motor configuration nodemcu swarm object detection fusionbot ros2 rviz2 gazebo conference matlab arduino nano decentralized surfaces keyboard IROS Integrated Demo throughput peripheral device paper review reinforcement learning; motorized boats Writing slam; paper review rhino Short Post range distance surp origami robot nylon pvdf elastic polymers plastic hot plates reinforcement learning; multi-agent; mean-field; game theory; mean field; reinforcement learning current reinforcement learning; multi-agent; Xbee Zigbee robot compiler spi contact neural network dynamic modeling quasi-static modeling edg-examples Kalman Filter port-array von Mises Fisher von Mises-Fisher literature review multipack car Zero Elastic Energy modes swarm control solar cars system ID serial monitor edg-ide Discrete Elastic Rods ceres debug Consensus Algorithms coriolis force dynamic model proposal wtf deep learning pdms interpolation wireless signal strength reinforcement learning; multi-agent; decentralized misc reinforcement learning; multi-agent; mean-field; stationary demo video flytrap papers steering structured field pivoting differential power detectionrate color shape edg-refactoring pain python vision Machine Learning Q-Learning Model-Free release conferences quasi-static pushing liquid crystal elastomer nonholonomic systems iot grant feedback-controlled controls trajectory optimization surface contact Characterization tool ML multi-agent path finding Liquid Crystal Elastomers Learning kinematic_model reservoir computing 2.4 GHz concept 433 MHz Bayesian Network creative Computer skill internal silicone integrated system instance segmentation marginal cost pricing bootstrapping Bayesian networks ensemble methods offline Rl hardware manipulation COVID 19 paper cutter ESP32 kalman filter; multi-robot state space delta tolling buoyancy chiral square unit cell pressure distribution model prediction thrust configuration grid fabrication firmware protobuf #activecapturingmechanism #claw 3D-CHESS; kalman filter boxboat tracking model-based RL von Mises Distribution slam; flowchart; spring-mass 3D-CHESS; 433 rssi signal strength multirobot system writing in-situ design buoyancy equations boat deployment cell cameras der newton's method Barycenter Euler-Bernoulli beam sma-based actuator game theory Bessel functions von Mises-Fisher Distributions ide HDL board design battery current sensor ZMP center of friction Multi-Agent Systems code balloon semantic segmentation MIMO communications ICRA ICML guassian processes probabilistic neural networks graph generators MBRL batch learning ros edg-compiler multirobot optitrack adaptive control motor driver submission DNN kalman filtering point cloud 2.4ghz latency scenic codesign presentations machine training preliminary exam multiple devices inkscape material multi-object tracking ICLR Python actuation catching mechanism integration flapping color_segmentation lab_data result segmentation on multiple object and centers finding competition prelab multiple blimps pid defender Synthesizable Radio 3d printing kalman filter motor distribution barometer detection lift force depth estimation cad solidworks design tool pixracer pixhawk ardupilot flight controller regression fly test sensor selection