Embedding a random graph via GNN: mean-field inference theory and RL applications to NP-Hard multi-robot/machine scheduling
Authors: HYUNWOOK KANG
SEUNGWOO SCHIN
James Morrison
Jinkyoo Park
Venue:  (2021)
Keywords: Graph neural network
graph embedding
multi-robot/machine scheduling
Reinforcement learning
Mean-field inference

Abstract: We develop a theory for embedding 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 reward collection problems called Multi-Robot Reward Collection (MRRC). Such MRRC problems well model ride-sharing, pickup-and-delivery, and a variety of related problems. We consider the classic identical parallel machine scheduling problem (IPMS) in the Appendix.  

For the theory, we first observe that MRRC system 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.

Our theory enables a two-step hierarchical inference for precise and transferable Q-function estimation for MRRC and IPMS. For scalable computation, we show that the transferability of Q-function estimation enables us to design a polynomial-time algorithm with 1-1/e optimality bound. 
Experimental results on solving NP-hard MRRC problems (and IMPS in the Appendix) highlight the near-optimality and transferability of the proposed methods.  


Under review as a conference paper at ICLR 2021
EMBEDDING A RANDOM GRAPH VIA GNN: MEAN- FIELD INFERENCE THEORY AND RL APPLICATIONS TO NP-HARD MULTI-ROBOT/MACHINE G
Anonymous authors Paper under double-bling review
ABSTRACT
We develop a theory for embedding 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 reward collection problems called Multi-Robot Reward Collection (MRRC). Such MRRC problems well model ride-sharing, pickup-and-delivers and variety of related problems. We consider the classic identical parallel machine scheduling problem (IPMS) in the Appendix.
For the theory, first observe that MRRC system state be represented 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.
Our theory enables a two-step hierarchical inference for precise and transferable Q-function estimation for MRRC and IPMS. For scalable computation, show that transferability of Q-function estimation enables us to design polynomial time algorithm with 1/e optimality bound. Experimental results on solving NP-hard MRRC problems (and IMPS in the Appendix) highlight the near-optimality and transferability of the proposed methods.
INTRODUCTION
Consider set of identical robots seeking to set of spatially distributed tasks. Each task is given an initial age (which then increases linearly in time). Greater rewards are given to younger tasks when service is complete according scheduling problems possessing constraints such as 'no possibility of two robots assigned to a task at once'. Such problems prevail in operations research, e.g., dispatching vehicles deliver customers in city or scheduling machines in factory. Impossibility results in asynchronous communication Fischer et [183)] make these problems inherently centralized.
predetermined reward rule. We focus NP-hard
Learning-based scheduling methods for single-robot NP-hard problems. structure2vec DDai al. (2016)) is a popular Graphical Neural Network (GNN) derived from the fixed point iteration of PGM based mean-field inference. Recently, Dai et al. (017)) showed that structure2vec can construct solution for Traveling Salesman Problem (TSP). A partial solution to TSP was considered as an intermediate state, and the state was represented using heuristically constructed probabilistic graphical model (PGM). This GNN was used to infer the Q-function, which they exploit to select the next assignment. While their choice of PGM was entirely heuristic, their approach achieved near- optimality and transferability of their trained single-robot scheduling algorithm to new single-robot scheduling problems with unseen number of tasks. Those successes were restricted to single-robot problems except for special cases when the problem can be modeled as a variant of single-robot TSP via multiple successive journeys of a single robot, c.f., (Nazari al. (2018) Kool et al. (018)).
Due this limitation, multi-agent (decentralized) methods rarely used industries (e.g., factories).

---

Under review as a conference paper at ICLR 2021
Proposed methods and contributions. The present paper explores the possibility of near-optimally solving multi-robot, multi-task NP-hard scheduling problems with time-dependent rewards using a learning- baaningg-based algorithm. This is achieved by first extending the probabilistic graphical model (PGM))baaed mean-field inference theory in Dai et al. (2016) for random PGM. We next consider a seemingly naive two-step heuristic: (i) approximate each edge's presence probability and (ii) apply typical GNN encoder with probabilistic adjustments. We subsequently provide theoretical results that justify this approach. We call structure2vec (Dai et al. (2016)) combined with this heuristic random structure2vec. After observing that each state of a robot scheduling problem can be represented as a random PGM, we use random structure2vec to design a transferable (to different size problems) reinforcement learning method that is, to the best of our knowledge, the first to learn near-optimal NP-hard rooti-rrobo/mmachine scheduling with time-dependent rewards. Experiments yield 97% optimality for MRRC problems in deterministic environment with linearly-varying rewards. This performance is well extended to experiments with stochastic traveling time.
Tas1 (TTF (A 14-21 10 Current Onl,) Smin
(cand tervid)
ni.55
Current age Onl,2: dasin
Task2 (Tyb (B C)
< 1-1
4+3
=f
ce
1-126
Thekk (Ty): (A 9 C) Corrent 012. 7aain
11,
4 :2:4-7
Ridesharing/ Pickup & Delivery
Sta Are _ and TOT
(s any) ), E
and w
problem 14
Figure I: Representing a pidesharing/pickup and delivery problem as an MRRC problem
2 MULTI-ROBOT SCHEDULING PROBLEM FORMULATION
We formulate a multi-robot reward collection problem (MRRC) discrete-time, discrete-state (DTDS) sequential recision-making problem. (For a closely related continuous-time and continuous- state (CTCS) formulation of IPMS problems, see Appendix A. For the DTDS formulation, time advances in fixed increments A and each such time-step is considered a decision epoch. (For the CTCS formulation, the times when robot arrives at task or completes a task are considered as decision epochs.) At such decision epochs (which occur at every time-step in our discrete-time model), we reassign all available robots to remaining tasks. We use l to index the decision epochs and let th denote the time that epoch is occurs (in discrete-time ty = k- A). We assume that at each decision epoch, we are newly given the duration of time required for robot to complete each task, which we call task completion time. Such task completion times may be constants or random variables, and in either case, they are determined by current state (e.g.. locations of the robot and the task) at each epoch P We consider initial tasks as nodes in a fully connected graph. For the edge from task p to task g, we denote as TT. The edge weight assigned is the task completion time for a robot "p.4 that has just completed task p to subsequently complete task q. Let ETT, WTT be the set of all p.g and the set of corresponding weights. All elements of TTT multiples of A).
TT
State. The state $t, at time tx is represented as (Gr, W a.x)). Go is a directed bipartite graph (R U Tr,, E where R is the set of all robots, Te, is the set of all remaining unserved tasks at time step ty. The set ε... consists of all directed edges from robots to unserved tasks at time ty. To each edge is associated weight equal to the task completion time. Let W denote the set of all such weights for all edges at t (either constants or random variables, of which values are restricted to multiples of A in the the DTDS system). For example, cRT ERT is an edge indicating robot i is assigned to serve task p. To this edge a task completion time is assigned according to current locations of the robot i and task p. Each task is given initial age which increases linearly with time (a multiple of A for DTDS). Let on, = { E RRpp E Tr, denote the set of ages where Vhs indicates the age of task p at time-step tg. We denote the set of possible states S.
It is intuitively clear how MRRC can directly model problems with stationary tasks. MRRC can also model problems such as ride-sharing or package delivery problems in which the robot location at
In the later case, our method only requires samples of the random variables; distributions are required.
2

---

Under review as a conference paper at ICLR 2021
the start of the task is different than at the end. Consider pickup and delivery tasks as illustrated in Figure Task 1, denoted as T1, is to pickup from A and deliver to location B. The weight assigned to the edge <2.1 is the task completion time for robot who has just completed task 2, and is thus located at C, who subsequently completes task 1. The traveling distance to task 1 (C + A) is 4 and the delivery distance (A -> B) is 3, the task completion time is <3.1 = 3 + 4 7. In the middle image in Figure I state Sts (robots nodes, task nodes, ares from robots to tasks and their weights, and ages), the system g (ares between task nodes) and their weights W are depicted.
Joint assignment. Once a robot has reached a task, it will conduct it until completion. Otherwise, we allow reassignment prior to arrival. Thus, available robots can change their assignments whenever a decision epoch occurs. A joint assignment of robots to tasks at current state St,- = (Gt.. W.?" at.). denoted as at., should satisfy: (i) no two robots can be assigned to the same task, and (ii) a robot may only remain without assignment when the number of rohots exceeds the number of remaining tasks. Thus, a joint assignment Ct2 is the set of edges in maximal bipartite matching of the bipartite graph Gr. The action space As, is depends upon Stg. it is defined as the set of all maximal bipartite matchings in Gr, A policy π is defined as ग ( = aty. where 5t2 E S and asy E Ase.
Transition function and reward. In the hierarchical control literature, our assignment is termed macro-action. In pursuit of the macro-action robots may make multiple sequential micro- to serve the task. The transition probability associated with macro-action is derived from the transition probabilities associated with micro-actions (Omidshafiei et al.) (201)). For a joint macro- action, assume there is induced joint micro-action denoted as uy E 2 with associated transition probabilities P (st+1 (9,, uz): S xl4, x St + [0, 1]. Omidshafici et al. 2017 proves we can calculate the corresponding 'extended transition function' P' (St2+1 (tt, at,) S. X AI x Si + [0, 1].
When task is served, reward is given according predetermined reward function that computes rewards according to the task's ' age at the time of service. Note that the state and assignment information St,, (t, and Sta+1 are thus sufficient determine the reward decision epoch fz+1- As such we denote the reward function as R(st, ata. +1) St. x At, x St. - IR.
Objective. Given an initial state Sto S, the MRRC seeks to maximize the sum of expected rewards through time by optimizing an assignment policy n as x² argmax E ET, ER k
R (t22 (sw 8..1)) |sto
SCHEDULING BY INFERENCING WITH A RANDOM PGM
3.1 BACKGROUND ON PROBABILISTIC GRAPHICAL MODEL (PGM) AND STRUCTURE2VEC
PGM. Given random variables X' = {Xg), suppose that we can factor the joint distribution p (X) as p (x)== II. Φ (D,) where (D,,) denotes marginal distribution or conditional distribution associated with a set of random variables D:; Z is a normalizing constant. Then {X+} is called a probabilistic graphical model (PGM). In PGM, Dj is called a clique and (D,)) is called a clique potential for D. When we write simply 6;. suppressing D,, D; is called the scope of é;.
Mean-field inference with PGM. popular use of PGM is PGMeb mean-fiehl fieadfieed inference. Suppose that X = {. {H2}}, where we are interested in the inference of {H,} given {Ya}. For the inference problem, our interest will be calculating p (
h2} (Y y)x)) but the calculation might not be tractable. In mean-field inference, we instead find a surrogate distribution q( (H,
h2 = II, g, (h₂) with smallest Kullback-Leibler distance to p ((11, = h23 (Y, = yu This surrogate distribution is then used to conduct the inference. Hereafter, for convenience, we suppress explicit mention of the random variable, for example, we write p(h;) for p(H, hy). Koller & Friedman (2009) shows that when we are given a PGM, the y(hh)) }) can be obtained by fixed point equation. Despite the usefulness of this approach, we are not often directly given the PGM.
Structure2vec. In some problems such as molecule classification problems, data is given as graphs. For such special cases, [Dai et al. (2016)] suggests that this graph structure information may be enough to conduct a mean-fied inference when combined with Graph Neural Network (GNN). Let us first embed p (hy {yk}) }) to vector Ay using the equation ūú = Jx ó (h₂) p (hy {yx}) dhy- Suppose that our problem has a special PGM structure that joint distribution is proportional to some factorization Ikev (he, yk) Hssev & (hs; ht), where V denotes the set of vertex indexes. Then
3

---

Under review as a conference paper at ICLR 2021
according to [Dai et al. [ the embedding of the fixed point iteration operation of PGaMd mean-field inference corresponds to a neural network operation fu: = o + W م, P5) (a denotes Relu function and W denotes parameters of neural networks). We can therefore use { to solve the original inference problem instead of p ( [ {yy}) or {) Note that their suggested neural network operation is similar to the network structure of Graph Convolutional Networks (Kipl Welling (,017),, a popular GNN-based graph embedding method. This observation enables one to interpret GNN-based graph embedding methods as mean-fiee field inference using PGM.
P D
(o(s, aq)
Dus Auniing
13
Qo (
107
Ppy
P3
Q(s..
Tosk eorrpletioo tine of TM
P(D G) Fae
Wayp O
(5tg (.)). E0H and WT
((H,)((xx) inference with Random PGM
Random graph Embedding
Estimating ((s,a,)
Figure 2: State representation and main inference procedure
3.2 INFERENCE WITH RANDOM PGM AND RANDOM GRAPH EMBEDDING WITH GNN
Random PGM. Denote the set of all random variables in the inference problem as X²= = (X,). Suppose that the set of all possible PGMs on X, denoted as Gx, is prior knowledge (e.g., for a robot scheduling problem, PGM is often specific Bayesian Network- see Appendix [A.2). A random PGM on X is then defined as (9x, P) where P: 9x + [0, 1] is the probability measure for a realization of an element of Gx- Note that the inference of P will be difficult. To avoid this task, we start by defining remi-cliques. Suppose that we are given the set of all possible cliques on X as Ex. Only a few cliques in Ex will be actually realized as an element of PGM according to P and become real cliques. So we call the elements Din E Cx as semi-cliques. Note that if we are given P then we can easily calculate the presence probability pm of semi-clique D,n as Pm. EGeg, D(G)
Mean-field inference with random PGM. The following theorem extends mean-field inference with PGM (Koller & Friedman (2009)) mean-field inference with random PGM. shows that we only need to infer the presence probability of each semi-clique in the random PGM, not P.
Theorem 1. Random PGM based mean field inference. Suppose we are given random PGM on X [X+). Also, assume that we know presence probability {pm} for all semi-cliques Dmn E Cx- The surrogate distribution {gu ( in mean-field inference is locally optimal only if qu (Ik) = Zz exp {Em:x eD... Pmm [DD=- D>y [In Φm (Dm;4x)]] where Zy. is normalizing constant and Om is the clique potential for clique m. (For the proof see Appendix A.3
Random structure2vec. From Theorem 1, can develop random structure2vec corresponding to a random PGM with ((H)), {Y&)). That is, we can combine (i) the fixed point equation of the mean field approximation for yu (hx) (Theorem 1) and (ii) the injective embedding for يu Jr o( H, H))p(h )dh,, to come up with parameterized fixed point equation for jú (see Figure 2). As in Dai al. (2016), we restrict our discussion to the case where there are semi-cliques between two random variables. In this case, the notation we use for Dm and pm is Dij and Pij.
Lemma 1. Structure2vec for random PGM. Given a random PGM on X ((H+), (Y&J). As (Dai et al. (2166), suppose that our problem has PGM structure with joint distribution proportional to some factorization II. & (hy,, yk) IIs, I (he, h2). ). Assume that the presence probabilities {piz) for all pairwise semi-che mmnicclquess Dij E Ex are given. Then fixed point equation in Theorem 1 for pl H& Hyrk)
embedded to generate the fixed point equation j. = a (W1y) W2 Ejtz Pkslit)
The proof of Lemma can be found in Appendix A.4
Remarks. Note that inference of P is in general a difficult task. One implication of Theorem 1 is that we transformed difficult inference lask to a simple inference task: inferring the presence
4

---

Under review as a conference paper at ICLR 2021
probability of each semi-clique. (See Appendix A.5 for the algorithm that conducts this task). In addition, Lemma I provides theoretical justification to ignore the interdependencces among edge presences when embedding random graph using GNN. When graph edges not explicitly given or known to be random, the simplest heuristic one can imagine is to separately infer the presence probabilities of all edges and adjust the weights of GNN's message propagation. According to Lemma 1, possible interdependencies among edges would not affect the quality of such heuristic's inference.
MultiRobot Reward Collection
Srabe Action Value Irfenerce Sequeettie Graph Emboddiing
fartion in lawed
(MRAC)
Foontt
Environment
Auction
Tasks
A
Agarn
E
Task
RET)
Farel tompiilin Eeponesis byly docaveng roward
p4r1
Reward FL
Optinize
Figure 3: Illustration of overall pipeline of our method
SCHEDULING MRRC WITH Random structure2vec
As illustrated in Appendix with factorization II. Φ (hg, yk II, e (he, h,). Therefore, according to Lemma 1, we are justified
MRRC problems with no randomness induces Bayesian networks
to use random Structure2vec to design a method to learn solutions to our MRRC problems.
4.1 DESIGNING Q Q-FUNCTION ESTIMATOR HAVING ORDER TRANSFERABILITY
Intuitively, local graph information around node k is embedded into the struclure2vec output vector iu [Dai et al. 2. Using this intuition, we propose a two-step sequential and hierarchical state- embedding neural network using random structure2vec that is designed to achieve what will later call teddf-rlanseerable Q-function estimation. This allows problem-size transferable Q-learning. i.c. the neural network parameter 0, trained calculate Q that approximates the Q-function Qth for an m-robot scheduling problem, can be well used to solve n-robot scheduling problems (n o m). For brevity, we assume task completion times are deterministic. For the detailed algorithm with random task completion times, see Appendix A.6 The following procedure is illustrated in Figure 3
Step 1. Distance Embedding. The first structure2vec layer embeds information of robot locations around each task k. i.e. local graph structure around each task k with respect to robots, to each pt (superscript 1 denotes the outcome of first layer). For the input of the first structure2vec layer (fzx) in Lemma 1), we only use robot assignment information (if k is an assigned task, we set the value of ry to task completion time of assignment (a duration); l: is not an assigned task:, we set my 0). Step 2. Value Embedding. The second structure2ved layer embeds how much value is likely in the local graph around task i to z².. Recall that the output vectors the first structure2vec layer, { carry information about the graph structure of robots locally around each task. For each task k we concatenate task k's age Ty with jil to get Ø1 and use (M/ } as the input (frx} in Lemma 1) to the second structure2vec layer. Denote the outcome of second structure2vee layer as {
Step 3. Computing (s,, ). To derive Qo at,.. we aggregate the embedding vectors for all nodes by 2 Σe / obtain one global vector ji to embed the value affinity of the global graph. We then use neural network to map jt2 into Qo(st,: )..)
Let us provide the intuition related to problem-size transferability of Q-learnig. Step above, transferability is trivial; the inference problem is scale-free task locally around each node. For Step 2, consider the ratio of robots to tasks. The overall value affinity embedding will be underesti- mated if this ratio in the training environment is smaller than this ratio in the testing environment;
5

---

Under review as a conference paper at ICLR 2021
overestimated overall otherwise. The intuition is that this over/under- esttmmttonn does not matter in Q-learning [van Hasselt et al. [2015) as long as the order of Q-function value among actions are the same. That is, as long as the best assignments chosen are the same, i.c., argmax.., ( aty) argmax at, Q (Sey, M the magnitude of imprecision (Q atr,) Q3 ( does not matter. We call this property order-transserabiiity of Q-function estimator with 0.
4.2 ORDER TRANSFERABIILTT--NNE
AUCTION FOR SCALABLE COMPUTATION
Learning- baarning-based heuristics for solving NP-hard problems have recently received attention due to their fast computation speed for large size NP-hard problems (Dai et al. (2017)] However, this advantage disappears for Q-learning methods when faced with large action spaces [Liliicrap et al. (2015)]. For multi-robot/machie scheduling problems, the set of all multi-robot assignments at each decision epoch is the action space; it grows exponentially as the number of robots and tasks increases, As such, the computational requirement of the argmax,.,, Q( ate) operation increases exponentially.
In this section, we demonstrate how order transferabilityy of Q-function estimation enables us to design a polynomial-time algorithm with provable performance guarantee (1 1/e optimality) substitute for the argmax operation. We call this algorithm an order transferabilit-ennbbbe policy (OTAP) and denote it as TQ where the Qo indicates that the Q-function estimator with current parameter 0 is used during the auction.
section-based
4.2.1 ORDER TRANSFERABILITY--NNEE
AUCTION BASEDD POLICY (OTAP)
We continue to use the notation introduced in section 4.1 Recall that state St. (Gt, , where gr, = (R TT, & OTAP finds an assignment at the edge set a maximal bipartite matching in the bipartite graph Gig after N = max (|R), [T)) iterations of Bidding and Consensus phases.
Bidding phase. In the th bidding phase, initially all robots know M the ordered set of n 1 robot-task edges in ERT determined by the previous n 1 iterations. An unassigned robot i ignores
(-= all others unassigned and calculates Q7 (Stg: MM U {< for each unassigned task as if those k robots (robot i together with all robots assigned tasks in the previous exist in the future and will serve all remaining tasks. (Here, <BT E & is the edge corresponding to assigning robot i to task j at decision epoch 44-) If task ? has the highest value, robot bids RT Q (st. M U (=(""")) }}} to the centralized auctioneer. Since the number of ignored robots varies at each iteration, transferability of Q-function inference is crucial.
iterations) only
Consensus phase. At th consensus phase, the centralized auctioneer finds the bid with the best bid value, say [eRT Q (st, (( (. }}}- (Here i" and p" denote the best robot task pair.) Denote
RT 4ppp mm
(n). The centralized auctioneer updates the shared ordered set MM(1)) =M, U Umg"
These two phases iterate until reach M {mg (1) ..... mg (N) This ! is chosen as the joint assignment of at time step tg. That is, =Q, (5ta) = ai The computational complexity for computing &Q, is ([R) [Tr,]) and is only polynomial (See Appendix A.
Provable performance bound of OTAP.
Let the true Q-functions for OTAP be (Q") Denote the outcome of OTAP with these true Q-functions as M(N) (m( "......."" (N)).
Lemma 2. If the Q-function approximator has order transferability, then M(N) = M!
For any decision epoch Le, let M denote a set of robot-task pairs (a subset of & For any robot- task pair m & define Am .M QlMu(mh (st,, MM M (m{]) (s,, as the the marginal value (under the true Q-functions) of adding robot-task pair E & Note, allow "adding" m E M for mathematical convenience the subsequent proof. In that case, we have
A (m M) = 0, E M.
Theorem 2. Suppose that the Q-finction approximation with the parameter value exhibits order
mansferability. Denote M(N) as the result of OTAP using {Q3} nz1 and let M argmax

---

Under review as a conference paper at ICLR 2021
Qlas,I ( If (m MM 2 M. Eiz Vm Ele,, and the marginal value of adding one robot diminishes the number of robots increases, i.e., A(m M) v {m IN, VN C C Etv. Wm E ERT, then the result of OTAP is at least better than 1/e of an optimal assignment. That is,
O ( (2) )2 12Q1 (Stu (1 1/e).
For proofs of Lemma 2 and Theorem 2, see Appendix A.7 and A.8
4.2.2 AUCTION-FITTED Q-ITERATION FRAMEWORK AND EXPLORATION
Auction-fitted Q-iteration. We incorporate OTAP into a fitted Q-iteration, i.e., we find that empirically minimizes ETg, (1+1)~"" (Qo (sk; ax) - [r (8k; ax) + Qo (Sk+1, QQ, (s++1)]]] Please note that this method's 's rigorous fixed point analysis is the scope of subsequent future research.
Exploration. How can we conduct exploration in the auction-fittee Q-iteration framework? Un- fortunately, cannot use e-greedy method since: (i) an arbitrary random deviation in joint assignment often induces a catastrophic failure [Maffioli] 1986)], and (ii) the joint assignment space, which is complex and combinatorial, is difficult explore efficiently with such arbitrary random exploration policy. In learning the parameters for Qo (Sk, az), we use the exploration strategy that perturbs the parameters randomly actively explore the joint assignment space with TAP. While this method was originally developed for policy-gradient based methods (Plappert et al. (001))) exploration in parameter space useful in our auction- fitted Q-iteration since generates reasonable combination of assignments.
5 EXPERIMENTS AND RESULTS
We focus on DTDS MRRC problem in the main paper and now elaborate upon our reasoning. As discussed in section 2. the formulation of MRRC problem assumes that task completion times are given as prior knowledge. Recall that in stochastic environment, task completion times given as random variables or sets of samples. In a simulation experiment standpoint, one must generate such dataset of task completion times before she can discuss algorithms solve MRRC problems. However, it is extremely difficult to generate a reasonable distribution of task completion times under continuous state continuous time (CTCS) environment (Bertsekas (2014); OOmidshafiei et al.) (017)) For example, finding an optimal control for stochastic routing problems under a CTCS environment in general intractable unless you discretize the space and time so that you transform CTCS environment to get an approximate DTDS environment [Kushner & Dupuis (2013)).
Despite this difficulty, stochastic environment experiment important since one of the main benefits of learning- based heuristics is its capability to tractably solve stochastic scheduling problems [Rossi al.) [. Therefore, in this paper, we focus on experiments under DTDS environment and target to show that our algorithm's 'ss performance for deterministic environments extends to stochastic environments. Since there no standard dataset for MRRC problems, we deliberately created a grid-world environment that generates nontrivial task completion time distributions with minimizing the selection bias. The idea we took was to use a complex maze (see Figure 3 generator ofNeller et al.) (2010) (code provided in Appendix 10) and compare it with the baselines. (For CTCS environment experiment under deterministic environment, refer IPMS experiments ( (Appendix A. A.II) ). We avoided over-fitting by randomly generating new maze for every training and testing experiment with initial task/robot locations also randomly chosen, only fixing the problem size while doing that.
To generate the task completion times, Dijkstra's 's algorithm and dynamic programming were used for deterministic and stochastic environments, respectively. To minimize artificiality, the simplest MRRC problem considered as follows. In the deterministic environment, robots always succeed in their movement. In the stochastic environment, a robot makes its intended move with a certain probability. (Cells with dot: success with 55% every other direction with 15% each. Cells without a dot: 70% and 10%, respectively.) A task is considered served when a robot reaches it. We consider two reward rules: linearly decaying rewards fage) = max
age, 0} and nonlinearly decaying rewards f fagee) Aage with X = 0.99, where age is the task age when served. The initial age of tasks are uniformly distributed in the interval [0, 100). Throughout, the performance measure used is p (%rewards collected by the proposed method/reward collected by the baseline). The baselines are: %Optimal: Gurobi was used for problems with the deterministic environment and linear rewards. Gurobi Optimization (2019) was allowed a 60-min time limit to search for optimal solution.
7

---

Under review as a conference paper at ICLR 2021
Ekici et al: For deterministic environments with linear rewards, an up-to-date, fast heuristic for MRRC (Ekici & Retharekar (2013)) was used (it claims 93% optimality for 50 tasks and 4 robots).
Sequential Greedy Algorithm (SGA): To our knowledge. there is no literature addressing MRRC with stochastic environments or exponential rewards. Instead, we construct an indirect baseline using general-purposs multi-rohot task allocation algorithm called SGA (Han-Lim Choi al. (2009). We will provide our performance divided by SGA performance as 4SGA. We will see that the %SGA in the deterministic linear-reward case is maintained for other cases.
Performance test. We tested the performance under four environments: deterministic/lnear rewards, deterministiccnoniineaa rewards, stochastic/linear rewards, stochastic/nonlinear rewards. See Table 1. For linear/deterministie rewards. our method achieves near-optimality with 3% fewer rewards than optimal on average. The standard deviation for P is provided parentheses. For others, we see that the %SGA ratio for linear/determnnistic is well maintained in stochastic nonlinear environments. Due to dynamic programming computation complexity of dataset generation, we only consider robots/50 tasks at maximum. Larger size problems were considered in IPMS experiments.
Table I: Performance test (50 trials of training for each cases)
Testing size: : Robot (R) / Task (T)
Reward
Environment
Baseline
2K/20T
3R/20T
3R/30T
3R/30T
5K/40T
8R/40T
8R/50T
4Optimal (Gumbi 60min)
98.31
97.50
97.80
95.35
96.99
96.11
96.85
Linear
Deterministic
Kikss et al.
99.86
97.50
118.33
110.42
105.14
104.63
120.16
SSGA
137.3
120.6
129.7
110.4
123.0
119.9
119.8
Stochustic
SSGA
115.7
122.8
122.5
113.3
115.9
Deterministic
ESGA
111.5
118.1
118.0
110.9
118.7
111.2
112.6
Nonlincar
Stochustic
SSGA
110.8
117.4
119.7
111.9
120.0
110.4
112.4
Transterability test. Table 2 shows comprehensive transferability test results. The rows indicate training conditions, while the columns indicate testing conditions. The results in the diagonal cells in red (cells with the same training size and testing size) serve as baselines (direct testing). The results in the off- off-diagonal show the results for the transferability testing, and demonstrate how the algorithms trained with different problem size perform well on test problems. We can see that lower-direction transfer tests (trained with larger size problems and tested with smaller size problems) show only a small loss in performance. For upper-direction transfer tests (trained with smaller size problems and tested with larger size problems), the performance loss was up 4 percent.
Scalability analysis. For scalability considerations, including computational analysis of OTAP and training data complexity, see Appendix 1
Table 2: Transferability test (50 trials of training for each cases, linear & deterministic env.)
Testing Robot (R)7 Task
(Robot/ (Tisk())
Training
2R/20T
3R/20T
3R/30T
5R/30T
5R/40T
8R/40T
8R/50T
2R/20T
98.31
93.61
97.31
92.16
92.83
90.94
93.44
3R/20T
95.98
97.50
96.11
93.64
91.75
91.60
92.77
3R/30T
94.16
96.17
97.80
94.79
93.19
93.14
93.28
5R/30T
97.83
94.89
96.43
95.35
92.63
92.40
SR/4TT
97.39
94.69
95.22
93.15
96.99
94,96
93.65
8R/40T
95.44
94.43
93.48
93.93
96.41
96.11
95.24
8R/50T
95.69
96.68
97.35
94.02
94.50
96.85
6 CONCLUDING REMARKS
We developed theory of random PGM-based mean-field inference method and provided a theoretical justification for simple modification of popular GNN methods to embed a random graph. This theory was motivated from addressing the challenge developing a near-optimal learning-based algorithm for solving NP-hard multi-rrooo/macchine scheduling problems. While precise inference of Q- Q-function is required to address this challenge, the two-layer random structure2vec embedding procedure suggested has shown an empirical success. We further address inscalability problem of Q-learning methods for multi roboo//inbomme scheduling problem by suggesting a polynomial samteeil---mee assignment algorithm with provable performance guarantee.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Dimitri P Bertsekas. Approximate dynamic programming. 2014.
Hanjun Dai, Bo Dai, and Le Song. Discriminative Embeddings of Latent Variable Models for Structured Data. 48:1-23, 2016. doi: 1603.05629.
Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning Combinatorial Optimization Algorithms over Graphs. (Nips), 2017.
Ali Ekici and Anand Retharekar. Multiple agents maximum collection problem with time dependent rewards. Computers and Industrial Engüneering, 64(4): 1018-0000110110000011011111 2013. ISSN 03608352. doi: 10. 1016/j.cie
doi htLt:ttp://// http:///...ddoooooooooooo////// wtw.o///.......1...........1.... cie 2013. 01. 010
Michael Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2)333433)2232322222223 382, apr 1985. ISSN 0004-5411. doi: 10.1 145/3
acm. ottpa//tta//oaaaaaoooo/o/oo////a
Google. Google OR-Tools, 2012.
URL hitps://develooerrs..oooo
optimization
LLC Gurobi Optimization. Gurobi uptimizer manual, 2019. wtt.:ttt::://w..uu......
com
Han-Lim Choi, Luc Brunet, and J.P. How. Consensus- Decentralized Auctions for Robust Task
Allocation. IEEE Transactions on Robotics, 25(4):912-925 aug 2009. ISSN 1552-3098. doi: 10.1 10.11090000220002022200
Thomas N. Kipf and Max Welling. Semi-supervised classificatinn with graph convolutional networks, Feb 2017. URL
02907
Daphne Koller and Nir Friedman. Probabilistic graphical models : principles and techniques, page 449-453. The MIT Press, 1st edition, 2009, ISBN 9780262013192.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv: 08445, 2018
M Kurz, R G Askin, M E Kurzy, and R G Askiny. Heuristic scheduling of parallel machines with sequence-dependent set-up times. International Journal of Production Research, 39(16): 3747-3769, 2001. ISSN 0020-7543. doi: 10.1080/002075401 10064938.
Harold Kushner and Paul G Dupuis. Numerical methods for stochastic control problems in continuous time, volume 24. Springer Science Business Media, 2013.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. sep 2015.
Francesco Maffioli. Randomized algorithms in combinatorial optimization: A survey. Dis- crete Applied Mathematics, 14(2):157 - 170, 1986. ISSN 0166-218X. doi: https:/doi..og 011016601666-111x8886608800 article/pii//0 6621 8X86900582
URL htEE::/www.cieecccireee.
www.liereeeeeecce.eeeeeeeeeeeeee com/science/
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence V. Snyder, and Martin Takáč. Reinforeement Learning for Solving the Vehicle Routing Problem. feb 2018.
Todd Neller, John DeNero, Dan Klein, Sven Koenig, William Yeoh, Xiaoming Zheng, Kenny Daniel, Alex Nash, Zachary Dodds, Giuseppe Carenini, David Poole, and Chris Brooks. Model AI Assignments. Proceedings of the Twenty-Foure AAAI Conference on Artificial Intelligence (A)AI-10), pp. 1919-1921, 2010
Shayegan Omidshafiei, Ali-Akbar Jonathan P How, and John Vian. Decentralized control of multi-robot partially observable Markov decision processes using belief space macro-actions. The International Journal of Robotics Research, 36(2):231-258, 2017. doi: 10.11770277339911722244
Christopher Amato, Shih-Yure Yuan Liu,

---

Under review as a conference paper at ICLR 2021
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y. Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter Space Noise for Exploration. pp. 1-18, 2017.
Federico Rossi, Saptarshi Bandyopadhyay, Michael Wolf, and Marco Pavone. Review of Multi-Agent Algorithms for Collective Behavior: a Structural Taxonomy. IFAC-PupersOnLime, 51(12):112-117 2018. ISSN 24058963, doi: 10. 1f.1016/..facoo.2118..777
Hado van Hasselt, Arthur Guez, and David Silver. Deep Reinforeement Learning with Double Q-learning. 2015.
A APPENDIX
A.1 IDENTICAL PARALLEL MACHINE SCHEDULING PROBLEM (IPMS) WITH MAKESPAN MINIMIZATION OBJECTIVE
A.1.1 FORMULATION
IPMS is a problem defined in continuous state/continuous time space. Once service of a task begins, it requires a deterministic duration of time T; for a machine to complete we call this the processing time. Machines are all identical, which means processing time of each tasks among machines are all the same. Processing times of each tasks are all different. Before a machine can start processing a task, it is required to first setup for the task. In this paper, we discuss IPMS with sequence-dependen setup times'. In this case, a machine must conduct a setup prior to serving each task. The duration of this setup depends on the current task and the task j that was previously served on that machine we call this the setup time. The completion time for each task is thus the sum of the setup time and processing time. Under this setting, we solve the IPMS problem for make-span minimization as discussed in [Kurz et al. (2001)). That is, we seek to minimize the total time spent from the start time to the completion of the last task. IPMS problem's sequential decision making problem formulation resembles that of MRRC with continuous-time and continuous-space That is, every time there is finished task, we make assignment decision for a free machine. We call this times as 'decision epochs' and express them as an ordered set (t1, .2......................... .t.............................. .t....). ). Abusing this notation slightly, we use (.),, (-)x. This problem can be cast as a Markov Decision Problem (MDP) whose state, action, and reward are defined as follows:
State. The state St, at time t is represented as (Gt., WART fx). Go is a directed bipartite graph (R U Tex ERRT) where R is the set of all machines, Tea is the set of all remaining unserved tasks at time step 4.. The set etr consists of all directed edges from machines to unserved tasks at time fx- To each edge is associated weight equal to the task completion time. Let W denote the set of all such weights for all edges at l. (either constants or random variables and restricted to multiples of RT A in the the DTDS system). For example, 6 E &RT is an edge indicating machine i is assigned to serve task p. To this edge a random variable denoting the task completion time (a duration) is assigned. Each task is given an initial age which increases linearly with time (a multiple of A for DTDS). Let ag, = [nk. E R lp E Te, } denote the set of ages where yfe indicates the age of task at time-step tg. We denote the set of possible states S.
Action. Defined the same as MRRC with continuous state/time space.
Reward. Let's denote the time between decision epoch k and decision epoch ks One can easily see that Tę is completely determined by 8g, ag and 8k+1- Therefore, we can denote the reward we get with 8k, d% and $1+1 as T(sk, ag, $k+1).
4+1 1 as Th- = ts - -1--1-
Transition probabilities. The transition probability P' defined the same as MRRC problem.
Objective. We now define assignment policy 6 function that maps state sy action dk- Given So initial state, an IPMS problem with makespan minimization objective can be expressed as a problem of finding an optimal assignment policy d² such that
0² = argmin E.,
T (S2, aks 1k41) |80
10

---

Under review as a conference paper at ICLR 2021
Table IPMS test results for makespan minimization with deterministic task completion time (our algorithm/ / best Google OR tool result)
Makespan
# Machines
minimization
3
5
7
10
50
106.7%
117.0%
119.8%
116.7%
Tasks
105.2%
109.6%
113.9%
111.3%
100
100.7%
111.0%
109.1%
109.0%
A.1.2 EXPERIMENTS
For IPMS, we test it with continuous time, continuous state environment. While there have been many learning-based methods proposed for (single) robot scheduling problems, the best our knowledge method is the first learning method to claim scalable performance among machine-scheduling problems. Hence, in this case, we focus on showing comparable performance for large problems, instead of attempting show the superiority of our method compared with heuristics specifically designed for IPMS (actually no heuristic was specifically designed to solve our exact problem (makespan minimization, sequence-dependen setup with restriction setup times))
For each task, processing times is determined using uniform [16, 64]. For every (task i, task j) ordered pair, unique setup time is determined using uniform [0, 32]. As illustrated in Appendix A.I. we want to minimize make-span. As a benchmark for IPMS, we use Google OR-Tools library Google (012). This library provides metaheuristics such as Greedy Descent, Guided Local Search, Simulated Annealing, Tabu Search. We compare our algorithm's 's result with the heuristic with the best result for each experiment. We consider cases with 3, 5, 7, machines and 50, 75, 100 jobs.
The results are provided in Appendix Table Makespan obtained by our method divided by the makespan obtained in the baseline provided. Although our method has limitations in problems with small number of tasks, it shows comparable performance to large number of tasks and shows its value as the first learning-basse based machine scheduling method that achieves scalable performance.
Reward rule
Current
Age at completion
10
Random urffic
Edges realized pollcy
Rewardy recliized nodes
Assignments are made policy
problem, edges derite conditional dependencies
Figure Representing MRRC as a random Bayesian Network
A.2 BAYESIAN NETWORK REPRESENTATION
Here we illustrate that robot scheduling problem randomly induces random Bayesian Network from state See figure 4
Given starting state s, and action person can repeat random experiment of "sequential decision making using policy d". In this random experiment, we can define events 'How robots serve all remaining tasks in which sequence'. We call such an event 'scenario'. For example, suppose that at time-step we are given robots {A, B). tasks {1, 2, 4, 5). and policy One possible scenario S* can be {robot A serves task + 1 + 2 and robot B serves task 5 4). Define random variable } } a task characteristic, e.g. 'The time when task & is serviced'. The question is. 'Given scenario S*, what is the relationship among random variables {H&Y } {uk} } (inputs in section 4.1)? Recall that in our sequential decision making formulation we are given all the 'task completion time' information in the 8, description. Note that, task completion time is only dependent
11

---

Under review as a conference paper at ICLR 2021
the previous task and assigned task. In example above, under scenario S "when task is served' is only dependent on "when task is served'. That is, P(Hy) H1, H3, S = = P , S*). This relationship is called "conditional independence'. Given a scenario S every relationship among {H]] can be expressed using this kind relationship among random variables. A graph with this special relationship is called 'Bayesian Network' (Koller & Friedman (2009)), probabilistic graphical model. Therefore, under fixed scenario S", this problem's 's joint distribution
can be assumed be factored as PGM structure IL @ (hx lox)) II.,, (hi]/)) where yn is the inputs considered in section 4.1 and H, denoting the time task served.
A.3 PROOF THEOREM
We first define necessary definitions for proof. Given random PGM (9x, P), PGM is chosen among Gx, the set of all possible PGMs on X. The set of semi-cliques is denoted as Cx As discussed in the main text, if we given P then can easily calculate the presence probability Pm: of semi-clique Dm as Pm EcEsx P(G)IDD..G.
For each semi-clique D in Cx, define a binary random variable V F - {0, with value O for the factorization that does not include semi-clique D and value for the factorization that include semi-clique D Let V be random vector V (V), V2 ...., VVex)). Then we can express (Ør (Di) as (Di).
x II Cxl (0 (Di)] V* We denote
Now we prove Theorem
In mean-field inference, we want to find a distribution Q .x) Q((x,) such that the cross-entropy between it and target distribution is minimized. Following the notation in Koller & Friedman (2009), the mean field inference problem can written as the following optimization problem.
min D
X.lv))
Q
(x)====1 =1 Vi
s.t.
Here D ( Q: | X.IVV) can be expressed as ID (II. Qi P =
Eq |n (II, Q:)] - EEq (X,,...,,,,[))))
12

---

Under review as a conference paper at ICLR 2021
Note that
In -n wi (D':))]
Eg
[In (P (nl...,,/[[[)) Be
[xx
(D |1
In
Texl
V'ln In ( (D')) EE(ln(Z)
[ex
Eq [V' In (Ø' (D')) Eq[In(Z)]
cxx
Ev: [BQ [v' In (ot (D')) [r]]] [X]]n(Z)]
P ((V 1) [E [In (Ø' (D')) Eq[In(Z)]
Cx
[Eq [In (0' (D)))] [[]]]
pi
Hence, the above optimization problem can be written as
cxl
n
max
EQ
Σ pi In (Ø' (D'))
EQ Σ (In Qi)
Q
s.t. (.: Vi
Koller & Friedman (2009). the fixed point equation is derived by solving an analogous equation to without the presence of the Pt. Theorem follows by proceeding in Koller & Friedman (2009)
with straightforward accounting for p;-
A.4 PROOF OF LEMMA
Since assume semi-cliques only between two random variables, can denote C. (DÚ) and presence probabilities as {pt}} where i, are node indexes. Denote the set of nodes as V.
From here, we follow the approach of Dai et al. (2016) and assume that the joint distribution of random variables can be written as
((Hx), (x+)) & II (H&) II o (Ha)H,).
REV
K.EVV
Expanding the fixed fixed-point equation for the mean field inference from Theorem 1, obtain:
Qu (ha)
Σ
B(Di-(Ha)) [In ob (He = -txnh//()]]]
exp
Z
HiEi
1
exp(Ino (H2 hx|=x)+
Zx
Σ Tev
Pt:Qi (h+) In In (He H,)HH) dh.).
13

---

Under review as a conference paper at ICLR 2021
This fixed-point equation for Qk (ht) is function of {Q, ( such that
Qu (hx) = (hx: Tk. {pa) Q2 (hy) (
As in Dai al. (2016), this equation can be expressed as Hilbert space embedding of the form a = T a [Kk. {PRSūs)
where ju indicates a vector that encodes Q1 (hx)) In this paper, we use the nonlinear mapping T (based on a neural network form suggested Dai et al. (2016):
p4
WIJ W2 Σ Phifi
jØk
A.5 SIMPLE PRESENCE PROBABILITY INFERENCE METHOD USED FOR MRRC
MM Denote ages of task j as age;, agej. Note that if we generate M samples of cij as {e 1==1- then M ΣM fee age,, agez) an unbiased and consistent estimator of Eff(Gy age;, age,)] The corresponding neural network- network-based inference is as follows: for each sample k, for each task and M
task j, we form vector of u (c);, age; age,) and compute 9i = k= M W1 (relu(W2u))) We obtain { from {9.r} using softmax.
The pseducode implementation as follows: In lines and 2, the likelihood of the existence of directed edge from each node to node is computed by calculating W1 (relu (2nn)n)) and averaging over the M samples. In lines and 4, we use the soft-max function to obtain pm.n-
1 For
do
2 Jmn E km Wi (relu (Wzutin))
3 For 17, T2 E V do
2mn/t
4.
Pmna Eyeu c9mn/7
A.6 COMPLETE ALGORITHM SECTION 4.1 WITH TASK COMPLETION TIME AS RANDOM VARIABLE
We combine random sampling and inference procedure suggested in section and Figure Denote the set of task with robot assigned to it as T Denote task in T t; and the robot assigned to t, as rt,- The corresponding edge in ERT for this assignment fr,,4- The key idea to use samples of Er,,, to generate N number of sampled Q(s, a) value and average them to get the estimate of E(Q(s, a)). First, for ( 1..NN N conduct the following procedure. For each task t; in T sample one data d'r, Using those samples and {pij}. we follow the whole procedure illustrated in section 4.1 to get Q(s, a) Second, we get the average of {Q(s, a) M=N to get the estimate of E(Q(s, a)), N
>>> a(s,a)+.
The complete algorithm of section 4. with task completion time random variable is given as below.
1 age; age of node i
2 The set of nodes for assigned tasks = TA
3 Initialize (1((0) ), (1)0)
4 for = to N:
5 for 1,
5
if E A do: sample e from Er
6
7
= rg
9
else: 2, = 0
10
for t = 1 to Ti do
11
for i E V do
14

---

Under review as a conference paper at ICLR 2021
Psiv (t-1)
12
13
p. relu (Wals + W(
(Tt)
14
A Concatenate
p4 .age)
15
for f = 1 to T2 do
16
for E V do
17
1, = Ljvv (1-1)
18
(1) relu (Wole + Wefs)
19
Q = W7 E ?i
(2)
20
Qavg = N
1 ΣN Qi
A.7 PROOF OF LEMMA 2
Statement:
Denote result of OTAP using true Q-functions {Q(m)} as M(N) = {m (N)m, If Q-function approximation method has onder transferabilityy then M =M, holds.
Proof. Recall that we say Q-function approximation method has order transferability argmaX (ntstt, at.) argmax acv 2% (st a..) We prove by induction.
Base case: For n (0) = -
(m) holds, i.c. ml my for S n. Then according to For > 0, suppose that (( m
1th step OTEP operation,
m (m+1) arginaxm Qu+1 (St,, M(n) U {m3)
Qu+1 M U {m}) (:: Order transferability assumption)
-argmax,
arggmax = m
Q
Mg (n)
u {m3) (t. inductioon argument)
(n+1)
Therefore, M(n+1) M(n) u {m(n+1) = =M!!") U Umm (mm+t))) = -Matt).
A.8 PROOF OF THEOREM 2
Statement: Denote N = max ([R),
Suppose that Q-function approximation method has order transferability. Denote M! as the result of OTAP using {Qg} and M as argmax Q (St. Ot2). If 1) the marginal value of adding one robot is positive, i.e. (SM,, U {m]) (sL,, 2 for all M E&R and 2) the marginal value of adding
robot diminishes as the robot number increases,
i... QIMI+1 (atg tay.a M U {m]) -QMM M) I QII++ (Sr, U (m)) QIi (st..N) for N MCM C CE for all m E E.RT, then the result of OTAP is at least better than 1 - 1/e of optimal
assignment, ie., QN (M QIMI (8" (1 1/e).
Proof. From the assumption that the marginal value of adding one robot is nonnegative, without loss of generality, we can consider M with [M N in the further proof procedure. Denote
- (2)) ..... m( } and denote M((N) {mg (1) . ..... my (N) 3.
(2)
For notation simplicity, define A(m (M) =: QIMMummm MU M QIM (M)
Then the optimal value OPT = QN (StL: M') s Qlum""MM (st,, UM*)
= (st +
= (mm
Mmn)
(m) U (m ... (.0)))).,,,mm-))))))))))
< ( 8
1= A (m M! (:: condition 2 decreasing marginal value condition)
I Q" M!!h)
EØ=1 (m (n+1) (M(())
(:: OTAP chooses mg
(n+1)
argmax,, Q (s u (ml) and
argmax,, 2
(st, M, (n) {m)) argmax, Q" (M u {ml) from Lemma 2)
(st,, NA(mmat)) M!nn)).
15

---

Under review as a conference paper at ICLR 2021
(1+1) Therefore, A A | (M 2 QOPT Mb
Note that OPT (s M denotes current iteration (= nh outcome Mf size of sub-
optimality compared to OPT. Denote OPT - (", Mg = Sn. Then since . Φ) = 0.
(
3 OPT. Therefore, we have A(mg
(1+1) ((
) 2 N Bn.
Also, note that A A(mg (n+1)
M Qu+! M, (n) L fmg
Mb
(st
= (Qt M ((att))) (8,, = (OPT - ("t (1)) -
-OPP - Quutt ($L, ( ))
Bn Bn-1. Therefore, Bn Sn+11 2 N Bn, i.e. But1 S Bn (1-
w) =0P((1 - ) and thus we get
This implies OPT - Q" (St,, Mb (1)) BN S &80(1 =0(1-))"=OPTL'
(sr,, Mb )0= = OPT(1 (1 )) OPT(1 - -)) as N - x0.
A.8.1 SCALABILITY ANALYSIS
Computational complexity. MRRC can be formulated semi-MDP (SMDP) based multi-robot planning problem (c.g.. Omidshafici et al. (2017)). This problem's 's complexity with At robots and tasks and maximum H time horizon is O(R!/T!(
*) For example, Omidshafiei al. (2017) state that problem with only 13 task completion times ("TMA nodes' in their language) possessed a policy space with cardinality 5.622 10"7 In our proposed method, this complexity is addressed by combination of two complexities: computational complexity and training complexity. For computational complexity of joint assignment decision at each timestep, (( = ((11 (2) (3) (4) (5)) where (1) (5) are follows.
(1) # of Q-function computation required in one time-step O( Shown in section 4.2
(2) # of mean-field inference in one Q-function computation = 2 (constant): Two embed- ding steps (Distance embedding, Value embedding) each needs one mean-field inference procedure
(3) # of structure2vec propagation operation in one mean-field inference= O(TT)): There is one structure2vec operation from a task to another task and therefore the total number of operations is [T] x ([T) 1).
(4) # of neural net computation for each structure2vec propagation operation=C (constant): This is only dependent the hyperparameter size of neural network and does not increase as number of robots or tasks.
(5) # of neural net computation for inference of random PGM=O([7)*) As an offline stage, we infer the semi-clique presence probability for every possible directed edge, i.c. from task to another task using algorithm introduced in Appendix 6. This algorithm complexity is O((T) x ([T) - 1)) ((7
Training data efficiency. Training efficiency also is required obtain scalability. To quantify this measured the training time required to achieve 93% optimality. As before, we consider a deterministic environment with linear rewards and compare with the exact optimum. Table demonstrates that training time many not necessarily increase with problem size.
Table 4: Training complexity (mean of 20 trials of training, linear & deterministic env.)
Testing size
Robot (R)
Task (T)
Linear & Deterministic
2R/201
3R/20T
3R/30T
5R/30T
3R/40T
8R/40T
8R/SOT
Performance with full training
98.31
97.50
97.80
95.35
96.99
96.11
96.85
Training for 93 optimality
19261.2
61034.0
99032.7
48675.3
48217.5
45360.0
47244.2
A.9 CODE FOR THE EXPERIMENT
For the entire codes used for experiments, please go to the following Google drive link for the codes
16


Reviews:
[{"review_id": "dDM5DooCVh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Summary\nThe paper considers the problem of multi-robot reward collection (MRRC) in which a number of robots are supposed to perform a number of tasks, in a centralized setting. Finding the optimal scheduling (assigning robots to tasks) under reasonable assignment constraints poses an NP-hard problem. The paper casts this problem as a mean-field inference over random probabilistic graphical models (PGMs) and proposes a two-step hierarchical inference method that employs Q-function estimation for a graph neural network (GNN) representation of MRRC. \n\n#### Strength\n1. The paper tackles a very difficult combinatorial problem that is of significant importance in a variety of applications, e.g., in manufacturing and ride-sharing.\n2. The proposed method is capable of being trained with a certain number of robots and tasks and then transferred to an instance with a different number of robots and tasks. Therefore, it is, to some extent, generalizable in terms of problem size.\n3. The figures in the paper are very illustrative.\n4. The authors have made the code available.\n\n#### Weakness\n1. The main drawback of the paper is that it lacks clarity. It seems that understanding the paper heavily relies on another paper (Dai et al. 2016). \n2. It is hard to understand the theoretical contribution of the paper, e.g., how the local optimality condition in Theorem 1 translates into the overall performance. Also, it is unclear to me whether the order-transferability is guaranteed or not. Since this property is an assumption to the theoretical results regarding the auction-based policy (Lemma 2 and Theorem 2), it is important that it holds.\n\n#### Recommended Decision\nDue to insufficient clarity of the presentation and the significance of the theoretical results, I think the paper is borderline in its current form.\n\n#### Supporting Arguments\n1. The transition from the first paragraph to the second paragraph in the introduction is abrupt.\n2. Please clarify explicitly how the reward function is related to the assignments, states, and actions.\n3. It is unclear why certain steps of the algorithm are required. For instance, in the paragraph about structure2vec, some explanation is needed regarding the definition of $\\tilde{\\mu}_j$ and the particular structure for factorizing the joint distribution (similar to the one in the beginning of Section 4).\n4. The proof of Theorem 2 resembles that of the near-optimality result for a greedy algorithm that aims to maximize a submodular function under a cardinality constraint.  Therefore, it may make sense to cite the following paper:\nNemhauser, George L., Laurence A. Wolsey, and Marshall L. Fisher. \"An analysis of approximations for maximizing submodular set functions—I.\" Mathematical programming 14.1 (1978): 265-294.\n5. The video in the supplementary material is not mentioned in the paper (nor the appendix).\n\n#### Questions\n1. Does the proposed algorithm ensure order-transferability, or does it promote that? Are there any guarantees for being order-transferable?\n2. The order-transferability is only tested for the deterministic environment with a linear reward. Does it also hold in the stochastic environment or with a nonlinear reward? \n3. What does “minimizing the selection bias” mean in Section 5?\n\n#### Additional Feedback for Improving the Paper\n1. It is better to keep the abstract as a single paragraph. \n2. The writing is satisfactory. But there are several typos in the paper.\n3. Please make the bibliography consistent in terms of details provided for each reference (some references have missing information) and the formatting. \n4. To be consistent in the appendix, provide the statements of Lemma 1 and Theorem 1 as well (similar to Lemma 2 and Theorem 2).\n5. There are redundant vertical spaces in the appendix.\n6. For evaluating the training data efficiency, please clearly denote the unit for computing the training time (e.g., number of steps).\n\n---\n#### UPDATE\nI thank the authors for their response. My major concerns regarding the paper's clarity and the implications of its theoretical results still hold. Therefore, I would keep my initial score and recommendation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "VuXHPNJb9j1", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents how to embed a random graph using GNN and shows how  to use this to solve NP-hard scheduling problems for multiple robots. Each state of a Multi-Robot Reward Collection problem is represented as a random probabilistic graphical model.  Then random structure2vec is  used to design a reinforcement learning method that learns near-optimal NP-hard multi-robot scheduling problems with time-dependent rewards. \n\nThe core contribution is to show how to solve the scheduling problem using random structure2vec and then design a polynomial time auction algorithm the replace the argmax operation in the order transferability of the Q function.\n\nExperimental results obtained using syntetic data are presented for combinations of tasks and robots in different environments and with different reward functions.  Transferability of learning on different problem sizes and scalability are also presented.\n\nThe paper is dense, but it is clearly written and provides background information on the methods proposed.   \n\nThe work makes a significant contribution to solve a hard problem that has many real applications in manufacturing, ride-sharing, pickup and delivery, etc.\n\nPros:\n1. The problem addressed is important for many real applications.\n2. The formulation of the problem and of the proposed solution is presented clearly. \n3. The results presented are built on theoretical results.  Some parts require more theoretical developments, but the empirical results support the validity of the approach.\n\nCons:\n1. The figures are too small, very hard to see.\n2. The  use of synthetic data for the experimental results is reasonable, but it would have been interesting to use existing data sets (for instance, data sets for vehicle routing problems with temporal constraints or data sets for job shop scheduling) even if not exactly for the same problem to enable comparison and duplication of results. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "80kRcg1xsVG", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a class of problems called the Multi-Robot Reward Collection problems. These are scheduling problems that are combinatorial in nature and hard to solve efficiently (in polynomial time). Traditionally, such hard problems have been solved with approximation algorithms or heuristics. Approximation algorithms are useful since they provide theoretical guarantees on the output solution, however their design requires significant problem-specific expertise. On the other hand, heuristics are easy to develop however the solution has no performance guarantees. In contrast to these two approaches, this paper proposes to use graph neural networks (GNN) to solve scheduling problems in graphical settings. \n\nThe presented method takes inspiration from structure2vec by Dai et al. (2017), which uses GNNs to compute solutions to several well-known NP-hard problems including the vertex cover and traveling salesperson problems (TSP). Although NP-hard problems are known to be reducible from another problem in the same hardness class, it is not straightforward to extend the solutions to problems involving multiple agents and time scheduling. This paper presents a method to embed graph environments to select actions.\n\nThe paper’s main contribution is the probabilistic graphical model for multi-robot multi-task scheduling problems. There are also theoretical and empirical justifications for the method’s performance. \n\nOverall, I think the method will be interesting to the community and the paper is written well except for the points listed below:  \n \n- The $(1 - 1/e)$ optimality bound: The approximation factor presented in Theorem 2 is obtained by the greedy maximization over the Q-values. This is computed using the bound on diminishing returns with greedy selection, as presented previously by Nemhauser et al. (1978). Although this result can be used to claim approximation of the optimal Q-values, it is not clear to me how it would translate to performance comparison against the optimal algorithm’s solution. For instance, if the objective function is a minimization problem (not expected return maximization), then we cannot claim that $OPT = Q^N(s, M^*)$ and the approximation to the optimal solution would not hold anymore -- a greedy minimization does not yield $(1 - 1/e)^{-1} = e / (e - 1)$-approximation. I encourage authors to clarify this point. \n- The improvement in the computational complexity from $O((R!=T !(R − T )!)^H)$ to $O(|R||T|^3)$ looks impressive. I believe it would be useful to address scalability with the polynomial time runtime of the presented method. For example, can the method work with 100s of robots and tasks -- similar scales were presented before in Dai et al. (2017)? If not, are there any limitations other than the computational resources? I also think that presenting the computation times for each setting will be useful to the reader. \n- The experimental evaluations are performed in simulation examples. It would be helpful to show results on real-world data and present generalization performance across different datasets.\n- It would be also good to see an explanation of the assumption made in Appendix A.8 with the nonnegative marginal improvement with adding one robot. Can multiple robots occupy the same node of a graph? Is there a notion of traffic in the flow of the graph?\n- The method performs auctions in a centralized manner. Any comments on how to make the action selection decentralized would be welcome.\n \nMinor comments:\n- Appendix 10 -> Appendix 9\n- assigning robot i to task j -> assigning robot i to task p\n \nReferences:\n- Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L. (2017). Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems (pp. 6348-6358).\n\n- Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical programming, 14(1), 265-294.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7XKT3CPME9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers multi-robot, multi-task scheduling problems. By introducing the notion of random PGM, authors develop a mean-field inference method and further prove that a modification of a GNN embedding is sufficient to embed a random graph. Experimental results show the near-optimality of the proposed method.\n\nThis paper extends the structure2vec algorithm to multi-robot multi-task scheduling problems. I like the idea of formulating the MRRC problem as a sequential decision making problem with graph-structured states. By doing so, the MRRC problem can be solved using random structure2vec with a nearly optimal solution. The proofs seem to be correct and theoretically support the optimality of the proposed method. A reasonable experiment is designed to evaluate the performance of the proposed method. \n\nOverall, this paper is well written. The idea of treating the multi-robot multi-task problem as a sequential decision making problem with directed bipartite graphs is novel.  This new idea naturally transforms the problem into a Bayesian network that can be solved efficiently.  \nI only have a minor concern regarding the stochastic task completion time. In real cases, it is hard to calculate the exact task completion distribution when tasks are more complex. There is no discussion about this in the paper. And a more complex example should be included in the experiment section. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work develops an approach to embed random graphs (some even with dependent edges, hence going beyond classical models such as Erdos-Renyi G(n,p)) using GNNs, and uses these to develop approximation algorithms for solving NP-hard scheduling problems, which typically involve some notion of minimizing weighted completion time (or equivalently, the reward incentivizes early completion, where the age of a job is a linear function of time). This is then used to schedule multiple identical robots  to solve a given set of spatially-distributed tasks. The problems considered---Multi-Robot Reward Collection (MRRC) model vehicle-routing, rideshare etc., and are well-motivated. 

This paper takes as motivation earlier work on “structure2vec” by Dai et al. (2016) that uses GNNs to (approximately) solve other NP-hard graph problems: specifically, the random structure2vec developed here is used for an RL approach that learns near-optimal solutions for the MRRC problems considered. 

While the paper’s contributions were appreciated in general, its clarity, the fact that the (1 – 1/e) bound of Theorem 2 follows from classical work of Nemhauser et al. (1978), and the fact that real-life examples were not considered, were considered weaknesses. The authors are encouraged to work on these aspects of the paper. 

Decision: Reject