Learning NP-Hard Multi Agent Assignment Planning using GNN: Inference on a Random Graph and Provable Auction-Fitted Q-iteration
Nov 28, 2022
Speakers
Hyunwook Kang
Speaker · 0 followers
Taehwan Kwon
Speaker · 0 followers
Jinkyoo Park
Speaker · 0 followers
James Morrison
Speaker · 0 followers
About
We develop a theory of inference on a random graph using graph neural networks (GNN) and illustrate its capability to solve NP-hard scheduling problems. We apply the theory to address the challenge of developing a near-optimal learning algorithm to solve the NP-hard problem of scheduling multiple robots/machines with time-varying rewards. In particular, we consider a class of robot/machine scheduling problems called the multi-robot reward collection problem (MRRC). Such MRRC problems well model ride-sharing, pickup-and-delivery, and a variety of related problems. In representing the MRRC problem as a sequential decision-making problem, we observe that each state can be represented as an extension of probabilistic graphical models (PGMs), which we refer to as random PGMs. We then develop a mean-field inference method for random PGMs. We prove that a simple modification of a typical GNN embedding is sufficient to embed a random graph even when the edge presence probabilities are interdependent. We then propose (1) an order-transferable Q-function estimator and (2) an order-transferability-enabled auction to select a joint assignment in polynomial-time. These result in a reinforcement learning framework with at least 1-1/e optimality. Experimental results on solving MRRC problems highlight the near-optimality and transferability of the proposed methods. We also consider minimax multiple traveling salesman problems (minimax-mTSP) and identical parallel machine scheduling problems (IPMS) in the Appendix.We develop a theory of inference on a random graph using graph neural networks (GNN) and illustrate its capability to solve NP-hard scheduling problems. We apply the theory to address the challenge of developing a near-optimal learning algorithm to solve the NP-hard problem of scheduling multiple robots/machines with time-varying rewards. In particular, we consider a class of robot/machine scheduling problems called the multi-robot reward collection problem (MRRC). Such MRRC problems well model…
Organizer
NeurIPS 2022
Account · 954 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Incentive-Aware Machine Learning: A Tale of Robustness, Fairness, Improvement, and Performativity
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Non-Gaussian Tensor Programs
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Deep Learning for Rapid Landslide Detection using Synthetic Aperture Radar (SAR) Datacubes
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Featured Papers Panels 4B
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Hand-Object Interaction Image Generation
Watch later
Hezhen Hu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Providing Intelligible Explanations in Autonomous Driving
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%