Learning scalable and transferable multi-robot/machine sequential assignment planning via graph embedding
Authors: Hyunwook Kang
Aydar Mynbay
James R. Morrison
Jinkyoo Park
Venue:  (2020)
Keywords: reinforcement learning
multi-robot/machine
scheduling
planning
scalability
transferability
mean-field inference
graph embedding

Abstract: Can the success of reinforcement learning methods for simple combinatorial optimization problems be extended to multi-robot sequential assignment planning? In addition to the challenge of achieving near-optimal performance in large problems, transferability to an unseen number of robots and tasks is another key challenge for real-world applications. In this paper, we suggest a method that achieves the first success in both challenges for robot/machine scheduling problems.
  
Our method comprises of three components. First, we show any robot scheduling problem can be expressed as a random probabilistic graphical model (PGM). We develop a mean-field inference method for random PGM and use it for Q-function inference. Second, we show that transferability can be achieved by carefully designing two-step sequential encoding of problem state. Third, we resolve the computational scalability issue of fitted Q-iteration by suggesting a heuristic auction-based Q-iteration fitting method enabled by transferability we achieved.
  
We apply our method to discrete-time, discrete space problems (Multi-Robot Reward Collection (MRRC)) and scalably achieve 97% optimality with transferability. This optimality is maintained under stochastic contexts. By extending our method to continuous time, continuous space formulation, we claim to be the first learning-based method with scalable performance in any type of multi-machine scheduling problems; our method scalability achieves comparable performance to popular metaheuristics in Identical parallel machine scheduling (IPMS) problems.

Under review as a conference paper at ICLR 2020
LEARNING SCALABLE AND TRANSFERABLE WULTI-ROBOT/MACHING SEQUENTIAL ASSIGNMENT PLANNING VIA GRAPH EMBEDDING
Anonymous authors Paper under double-blind review
ABSTRACT
There has recently been some success in the use of reinforcement learning meth- ods for single robot combinatorial optimization problems. In this paper, we de- velop the first learning- based method for multi robot/machine planning problems with combinatorial nature. One real-world concern is the capability to achieve transferability an unseen number of robots and tasks. The method developed here, for the first time, enables such transferability.
Our method is comprised of three components. First, illustrate how to repre- sent a robot planning problem as an extension of probabilistic graphical models (PGMs) which we refer to random PGMs. We develop mean-field inference method for such random PGMs and use it for Q-function inference. Second, we show that transferability can be achieved by carefully encoding the problem state via two-step sequential process. Third, we resolve the computational scalability issue of fitted Q-iteration. This achieved by employing an auction-basee heuris- tic substitute for the max operation in the Bellman equation. The auction is enabled by the transferability achieved.
Our method is applicable to discrete-time, discrete space problems such as multi- robot reward collection (MRRC). For such problems, with determinsitic assump- toins, we scalably achieve 97% optimality with transferability. This optimality is maintained under stochastic contexts. By extending our method continu- ous time, continuous space formulation, the approach is the first learning based method for machine scheduling problems. Our method scalably achieves com- parable performance to popular metaheuristies when applied to identical parallel machine scheduling (IPMS) problems in a deterministic context.
INTRODUCTION
Suppose that we are given a set of robots and seek to serve set of spatially distributed tasks. A reward is given for serving each task promptly - resulting in a time-decaying reward collection prob- lem or when completing the entire set tasks resulting the capability to control and route individual robots has increased (017), efficient orchestration of robots arises as an important remaining concern for such problems.
makespan minimization problem. As
Multi-robot planning problems. In this paper, focus orchestration problems that can be formulated as robot planning problems. A key assumption in such orchestration problems is that we given information on the "duration of time required for an assigned robot complete task". This duration may be deterministic (e.g. as a Traveling Salesman Problem (TSP) or Vehicle Routing Problem (VRP)) random with given probability distribution (c.f., (Omidshafiei et al. 2017 We call this duration the task completion time.
Due to their combinatorial nature, robot planning problems suffer from exponential computational complexity. Even in the context of single-robot scheduling problems (e.g.. TSP) scalability is a concern. Planning for multiple robots exacerbates the scalability issue. While scalable heuristic methods have been developed for various deterministic multi-robot planning problems (c.f., [Rossi
For the proposed method, samples of this distribution sufficient and the distribution itself is required.

---

Under review as a conference paper at ICLR 2020
et al. 2018)), )), heuristic methods have been developed for stochastic multi-robo planning prob- lems that are simultaneously both near optimal and scalable.
Learning-based planning methods. Recently, seminal learning- based planning algorithms have been developed for the scalable solution of TSPs [Bello et al. (2016); Dai et al. (2017); Kool et al. [2018]] They showed that learning methods can exploit the recurring structure of TSP and thus can generate near-optimal solution in a very fast computation time. However, those successes were restricted single-robot problems except for special cases when the problem can be modeled as variant of single-robot TSP via multiple successive journeys of a single robot (Nazari et al. (2018).
Kool
Near-optimal planning with scalability. In this paper, we address a general type of problem called Multi-Robot Reward Collection (MRRC) and show that this problem can be scalably solved by our method with near-optimal performance. Generally, the training requirements for learning- based methods increase exponentially with the problem size (number of robots and tasks); c.f., [Li (2017)] We empirically demonstrate that the training requirements of proposed method scale well while maintaining near-optimal performance. While we assumed discrete-state discrete-time condi- tions for MRRC, the method extends to continuous also the first Sarninggbased method with scalable performance that can address machine schedul- ing problems. The approach achieves scalability (e.g. 10 machines, 100 tasks) with comparable performance to popular heuristics when applied to Identical Parallel Machine Scheduling (IPMS).
continuous-tii tiimu problems. Our method is
Transferability. The proposed method possesses transfcrability in that a trained policy can be applied to new environments with small loss of performance (Wang et al. (2018)]. Such capability is important for real-world applications. Engineers are rarely able to trai a heuristic on a large- scale system during operation, but rather use small-scale testbed for training. Even if the whole system is available for training, the system design or number of robots may frequently change during operation. We show that our method achieves transferability with small performance loss.
Proposed methods. In the seminal paper [Dai et al. (2017)). the authors observed that combinatorial optimization problems such as TSP can be formulated as sequential decision making problems. Decision making in such a sequential framework relies on an estimate of future costs Q(s, a) for an existing task sequence s and candidate next task a. With this estimate, given the prior decisions at each decision step, they select the next task to minimize the future cost estimate. (Dai et al. 12s solution framework relies on the following three assumptions. 1) For each combinatorial optimization problem, one can heuristically choose how to induce a graph representation of (s, a). In the case of TSP, the paper induces a fully connected graph for every possible next task. 2) This induced graph representation can be considered
probabilistic graphical model (PGM) [Koller& & Friedman (2099] ]. This PGM can be used with a graph-based mean-field inference method called structure2vec [Dai et al. [2016) to infer Q(s,, a) for use in combinatorial optimization problems. 3) Inference of ((, a) can be learned by the reinforcement framework called fitted Q-iteration.
We create solution framework to achieve scalability and transferability for multi-robot planning that builds in numerous directions upon the foundation of (Dai et al. (2017) as follows:
1. State representation and mean-field inference theory for random PGM. Instead of heuristi- cally inducing a PGM, we show that a robot scheduling problem exactly induces a random PGM. Since there exists no mean-field inference theory for random PGM, we develop the theory and cor- responding new structure2vec iteration.
Sequential encoding of information for transferability. To achieve transferability in terms of the number of robots and tasks, we carefully design two-step hierarchical mean-field inference |Ranganath et al. (.015)]. Each step designed to infer certain information. The first step is de- signed to infer each task's relutive gruphical distance from the robols. The second step is designed to infer Q(s, a) (a here refers to a joint assignment of robots). While the first step is by its nature transferable to any number of tasks and robots. the transferability in inference of the second step is achieved by the scale-free characteristic of fitted Q-iteration [van Hasselt et al. (201)). That is, the relative magnitudes of Q(s, a) values are sufficient to select action a.
3. Auction-bass
assignment. Even if we can infer Q(s, a) precisely, the computation time re- quired to select an action using the maximum Q(s, a) operation exponentially increases as robots and tasks increase. To resolve this issue, we suggest a heuristic auction that is enabled by the trans- ferability of our Q(s, a) inference. Even though this heuristic auction selects with only polynomial computational complexity, it provides surprisingly good choices for a. (In fact, this heuristic auction increases the performance empirically relative to using the max operation.)
2

---

Under review as a conference paper at ICLR 2020
4. Auction-fitted Q-iteration. The heuristic auction- based action selection can be incorporated into learning (fitting) Q(s, a). To be specific, we use the auction- action selection scheme, instead of the typical max-operator based action selection, in the Bellman equation during fitted Q-iteration. We call this new learning framework as auction-fitted Q-iteration.
2 MULTI-ROBOT/MACHING SCHEDULING PROBLEM FORMULATION
We consider centralized sequential assignment planning problems. We assume perfect communica- tion, that is, the decision maker can always determine the distribution of task completion times.
2.1 MULTI-ROBOT REWARD COLLECTION (MRRC)
While we consider extended versions of the problem in Appendix AP here formulate MRRC as discrete-time, discrete-state planning problem. The initial location and ending location of robots and tasks are arbitrary on a grid (e.g., grid world). We assume that task is served immediately after a robot arrives. Under these assumptions, at each time-step, we can assign every robot to every remaining task. This MRRC problem can be cast as a Markov Decision Process (MDP) whose state, action, and reward are defined as follows.
State. The state 8t at time step is a directed graph 9. (R, &T, R2 is the set of available robots at time step f. Ti is the set of all remaining unserved tasks at time step t. The set of directed edges & E, RT ETT. A directed edge Crat, E E.R has a random variable as its weight which denotes the task completion time for robot in R2 if it is assigned at time step to serve task j in Tr (note this time subsumes the information about the robot's present location). A directed edge Ctd, E ETT has as its weight the task completion time for robot which just finished serving task i in Te (and is therefore located where task i resided prior to its completion) to serve task j in Te if assigned time step I.
Action. The action a at time step f is the joint assignment of robots given the current state 8 = Gi- Feasible actions should satisfy
robots can be assigned the same task and (ii) robot may not be assigned when the number of robots exceeds the number of remaining tasks To articulate an action, note first that the two set of nodes R, and Tr disjoint. As such, the sub-graph (R, U Tr, E of graph G. is bipartite. We thus define an action ae at time / as a maximal bipartite matching in the bipartite sub- aub-graph (R, U E gRRT) ). For example, robot in R2 is matched with task j in Te in an action a, if we assign robot i to task j at time step t. We denote the set of all possible actions time step as Ar-
constraints: (i)
Reward. In MRRC, each task has an arbitrarily determined initial age. At each time-step, the age of each task increases by one. When a task served, a reward is determined based only on its age at the time of service. Note that the state and assignment information 8t, d, and 5 is sufficient to determine the reward at time step & + As such we denote the reward as R(se, Gr, 8t+1).
Objective. We can now define an assignment policy d as a function that maps a state to an action ay. Given an initial state sg, the MRRC seeks to maximize the sum of expected rewards through time by the selection of an assignment policy d² satisfying
Φ argimax E
R (st, O2 8141) 1sp
2.2 IDENTICAL PARALLEL MACHINE SCHEDULING (IPMS) MAKE-SPAN MINIMIZATION
IPMS is continuous-time continuous-state problem consisting of diverse tasks which must be served by identical machines. Once service of a task begins, requires a deterministic duration of
II Appendix A we discuss how an MRRC can be formulated with continuous-ting time and continuous-state and addressed by methods. Further, we explain how method can be easily extended to address setup times and processing times.
We assume also that when the number of tasks is greater or equal to the number of robots, all robots will receive an assignment. However, because robots can be reassigned at any decision epoch, there is no loss of optimality in this assumption.
3

---

Under review as a conference paper at ICLR 2020
time Ty complete we call this the processsing time. This time is the same independent of which machine serves the task. We incorporate one popular extension and allow 'sequence-dependen setup times'. In this case, machine must conduct 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 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 minimize the total time spent from the start time to the completion of the last task. The IPMS formulation resembles our MRRC formulation in continuous- time and continuous-spar and we relegate the detailed formulation to Appendix [
3 CHOICE OF ASSIGNMENT AT EACH SIME-STEP
In Section? 2 we formulated multi montmmcobbo plamning problems as sequential joint assignment decision problems. As in (Dai et al. (2017) we will select a joint assignment using Q-function based policy. Since we thus choose action a, with the largest inferred Q(s,, az) value in state St, the development of (ss,, az) inference method is key issue. Toward this end and motivated by these robot planning problems, we provide new results in random PGM-based mean-field in- ference methods and subsequent extension of the graph-neural network based inference method called structure2vec [Dai et al. (2016)] in Section 3.1 In Section 3.2 we discuss how a careful encoding of information using the extended structure2vec of Section 3.1 enables precise and trans- ferable Q(st, ax) inference. Since the computational complexity required to identify the best joint assignment is exponential with respect to the number of robots and tasks, Section [.3 discusses how the transferability of our ((+e; 0z) inference method enables good action choice heuristic with polynomial computational complexity.
3.1 ROBOT SCHEDULING AS RANDOM PGM-BASED MEAN-FIRLD INFERENCE
PGM. Given random variables {X*]. suppose that joint distribution of {Xx} can be factored as P( X,,) = = 1I: Øi (D+) where of (D') denotes marginal distribution or conditional dis- tribution on a set of random variables D' Z is a normalizing constant. Then {Xx,} is called a probabilistic graphical model (PGM). In a PGM, D' is called a clique and d' d'(D)) is called a clique potential for D'. When we suppress o² (D( as t², DD is referred to as the scope of d².
PGM-based mean-field inference. One popular use of this PGM information is PGM--ased mean-field inference. In mean-fiek field inference, we find surrogate distribution QX Xx,) =
II: Qi(2;) that has smallest Kullback-Leibler distance to original joint distribution P(X,.. PX......, Xn).
We then use this surrogate distribution to solve the original inference problem. (Koller & Friedman [009)] shows that when we are given PGM information, (1,)), can be analytically computed by a fixed point equation. Despite that this usefulness, in most inference problems it is unrealistic to assume we know or infer probability distributions of a PGM. This limitation was addressed in
Dai et al. (0166) using a method called structure2vec.
Structure2vec. (Dai et al. [2016)] suggests that inference problem with graph-structured data (e.g. a molecule classification problem) can be seen as a particular PGM structure that con- sists of two types of random variables. One type of random variables {Xx} is one that serves as input of inference problem (e.g. X₁ denotes atomic number of atom k). Another type of random variables {H₂} is latent random variable where Hę latent random variable related to Xg. Existence of probabilistic relationships among }H₂} are assumed heuristically from graph structure of data. Then the particular PGM structure they assume P ((HH)) (Xxt) xx IEk @ (X&) II.. ø HH,, where V denotes the set of vertex indexes. The goal of mean-field inference problem is to find surrogate distribution Q& for posterior marginal P([he ((hheHHzx)). However, we can't 't compute (Qu( since we are not given & (Hş H.) nor (x)) To overcome this limitation, [Dai et al. [2016)] develops method called structure2vec that only requires the structure of the PGM for mean-field inference. structure2vec embeds the mean-field inference procedure, i.e. fixed point iteration on (Q+(hu)), into fixed point iterations of neural networks on vectors }. Derivation of such fixed point iterations of neural networks can be
found in Dai et al. 2016) and can be written as μī = a (iiz + W2 Ejzk (2:)) where a denotes Relu function and W denotes parameters of neural networks
4

---

Under review as a conference paper at ICLR 2020
Robot scheduling random PGM-based mean-field inference. All applications of structure2vec in [Dai et al. (2016) 2017 heuristically decide the structure of PGM each data point from its graph structure. The key observation we make is that inference problems in robot scheduling exactly induce 'random' PGM structure (to be precise, a 'random' Bayesian Network). Given that we start from state 8, and action at, consider random experiment "sequential decision making using policy 6". In this experiment, we can define an event as 'How robots serve all the remaining tasks in which sequence'. We call one such event 'scenario'. For each task i, Tr, define random variable X; as 'a characteristic of task t;" (e.g. when task is served). Given a scenario, the relationships among {X,) satisfy as Bayesian Network. For details, see Appendix C)
Note that we do not know which scenario will occur from time t and thus do not know which PGM will be realized. Besides, the inference of probability of each scenario is challenging. Putting aside this problem for a while, we first define 'random PGM' and "semi-cliques'. Denote the set of all random variables the inference problem as X (X,). A random PGM is probabilistic model of how PGM is randomly chosen from set of all possible PGMs on x Next, denote the set of all possible probabilistic relationships on X as Cx. We call them 'semi-cliques'. problem, semi-clique Dij Cx is conditional dependence X, XX The semi-clique Diy presents as an actual clique if and only if the robot which finishes task t, chooses task ł as the next task.
robot scheduling
We will now prove that we don't t have to infer the probability of cach scenario, i.c. random PGM model itself. The following theorem for mean-fiell inference with random PGM is an extension of mean-field inference with PGM [Koller & Friedman (2009) and suggests that only simple inference task is required: inference of the presence probability of each semi-cliques.
Theorem 1. Random PGM based mean field inference Suppose we are given random PGM on X = {. Also, assume that we know presence probability {Pm} for all semi-cliques ex = {Dm). The latent variable distribution {Qx(2 in mean-field inference locally optimal only if
(ZK)
1 Zk
exp
Σ
(mBB(Dn-(Xxx)<ee [In 6th (Dms Tw.i]
where Zu is a normalizing constant and 6th the clique potential for clique m.
From this new result, we can develop the structure2vec inference method for random PGM. As in Dai et al. (2016), we restrict our discussion to when every semi-clique between two random variables. In this case, semi-clique can be written Dij with its presence probability Piy.
Lemma 1. Structure2vec for random PGM. Suppose we are given a random PGM model with X {Xa}. Also, assume that we know presence probability {pi}} for all semi-cliques Cx = (D,)). The fixed point iteration in Theorem 1 for posterior marginal P( (xx)) can be embedded in nonlinear function mapping with embedding vector få
(WiTA + W2
WiTx
Σ Pkips j&k
fs =
Proof of Thorem 1 and lemma 1. For brevity, proofs are relegated to the Appendix and
Corollary 1. For robot scheduling problem with of tasks t, Tr, the random PGM represen- tation for structure2vec in lemma is ((Te, ETT), {pis1) where {púz} } denotes the probability of a robot choosing task after serving t..
{pg}} } inference procedure employed in this paper is as follows. Denote ages of task i.j as ages agez. Note that if we generate M samples of eij as ) then के ΣM f(e age,, age;) is an unbiased and consistent estimator of Elf(cej age,, age,)] For each sample k for each task and task j. we form a vector uty (ež age,, age;) and compute dūj = >' 37 W, (relu(Waat)
We obtain {pi}} from { using softmax. Algorithm details are Appendix
'The concept of 'random choice among all possible PGM might look unfamiliar, but this concept has been studied in various PGM literature; for example, see (Ritchie et al, (2066) to see applications in prohabilistic programming language (PPL.).
5

---

Under review as a conference paper at ICLR 2020
Mult: Collection (MRRC)
Auctinn boeed
Graph State Rop Eseniaiion
Ostaine Erilecdiing
Value Embeediing
Extimotiion
Action Seledtion
(G..)))
Suction
80
Agrnn
Reward T.
Auctio Fitted hortsontto Octiviice Mode Ryrometers
Figure 1: Illustration of overall pipeline of our method
3.2 INFERENCE OF Q-FUNCTION USING NEW STRUCTURE2VEC
In this section, we show how (s,, ax) can be precisely and transeferably inferred using a two-step structure2vec inference method (For theoretical justifications on hierarchical variational inference, see Ranganath et al. (2015)). We here assume that we are given (Te, E and inferred {Pij} J so that Corollary can applied. For brevity, we illustrate the inference procedure for the special case when task completion time is deterministic (Appendix G illustrates how we can combine random sampling to inference procedure to deal with task completion times as a random variable).
Step 1. Distance Embedding. The output vectors { of structure2vec embeds local graph information around that vector node [Dai al. (0T6))] We here focus on embedding information of robot locations around task node and thus infer each task's 'relative graphical distance' from robots around it. As the input of first structure2vec (fza) in lemma 1), we only use robot assignment information (if tg is an assigned task, we set æy as 'task completion time of assignment'; if 4 is not an assigned task:, we set 3y = 0). This procedure illustrated in Figure | According to [Dai et al. [2016]], the output vectors { of structure2vec will include sufficient information about the relative graphical distance from all robots to each task.
Value Embedding. The second step is designed infer 'How much value is likely in the local graph around each task'. Remind that vectors {it)} ). output vectors of the first step, carries information about the relative graphical distance from all robots to each task. We concatenate 'age' of each tasks {ages} to each corresponding vector in [ and use the resulting graph as an input (1a3 in lemma 1) of second structure2vec, as illustrated Figure [ Again, vectors { } of the output graph of second structure2vec operation embeds a local graph structure around each node. Our intuition that { includes sufficient information about 'How much value is likely in the local graph around each task'.
Step 2.
Step Computing at). To infer Q(se, 0t), we aggregate the embedding vectors for all nodes, i.e., ji2 = Σx i to get one vector ji? which embeds the "value likeliness' of the global graph. We then use layer of neural network to map ji2 into (5st, az). The detailed algorithm of above whole procedure (combined with random task completion times) is illustrated in Appendix G
Why are each inference steps transferable? For the first step, it is trivial; the inference problem is a scale-free task. In the second step, the 'value likeliness' will be underestimated or overestimated according to the ratio of (number of robots/ number of tasks) in local graph: underestimated if the ratio in training environment smaller than the ratio in the testing environment; overestimated otherwise. The key idea solving this problem is that this over/under-essimatio does not matter in Q-function based action decision [van Hasselt et al. 2015)] as long as the order of Q-function value among actions the same. While analytic justification of this order invariance is beyond this paper's 's scope, the fact that there is no over/underestimation issue in the first step inference problem helps this justification.

---

Under review as a conference paper at ICLR 2020
3.3 ACTION SELECTION USING HEURISTIC AUCTION
In Q-function based action choice, at each time-step we find an action with largest (ss, at). We call this action choice operation max-operation'. The problem in max-operation in the multi-robot setting is that the number of computation exponentially increases as the number of robots and tasks increases. In this section, we show that transferability of Q-ffucctoon inference enables designing an efficient heuristic auction that replaces max operation. We call it auction-basee -ased policy(ADP) and denote it as ΦQ.+ where Qe indicates that we compute ΦQ, using current Qa estimator.
At time-step I, state &t is graph G. = (R,UT, &.) as defined in section 2.1 Our ADP, &2.. finds an action de (which is a matching in bipartite graph ((R, UT::) E of graph Gi) through iterations between two phases: the bidding phase and the consensus phase. We start with a bidding phase. All robots initially know the matching determined in previous iterations. We denote this matching as V, bipartite subgraph of UT)), ) When making a bid, robot ignores all other unassigned robots. For example, suppose robot r; considers t, for bidding. For rss y U Cij is proper action (according definition in section 2.I in 'unassigned robot-ignored" problem. Robot thus can compute (s+t. y U fr.s,) of "unassigned robot-ignored problem for all unassigned task 43- If task 1" is with the highest value, robot bids {fr.r-, (s,,, J/ J'U,,, <r,a)) )} to auctioneer. Since number of robots ignored by is different at each iteration, transferability of Q-function inference plays key role. The consensus phase is simple. The auctioneer finds the bid with the best value, say {E*, bid value with e" }. Then auctioneer updates everyone's ' y as y {
These bidding and consensus phases are iterated until we can't add edge y anymore. Then the central decision maker chooses y as ΦQ. (sx). One can easily verify that the computational complexity of computing &Q, is O (|LRl Lrl), which is only polynomial. While theoretical per- formance guarantee of this heuristic auction is out of this paper's scope, in section 5 we show that empirically this heuristic achieves near-optimal performance.
4 LEARNING ALGORITHM
4.1 AUCTION-FITTED Q-ITERATION FRAMEWORK
In fitted Q-iteration, we fit 0 of Qe(se, a.) with stored data using Bellman optimality equation. That is, chooses f that makes E IQa (sk, 0&) rr (Sk, 0x)) + max.' (Qo (14411% small. Note that every update of needs least one max-operation.
To solve this issue, we suggest a learning framework we call auction-fitted Q-iteration. What we do is simple: when we update 0, we use auction-based policy(ADP) defined in section 3.3 instead of max-operation. That is, we seek the parameter 0 that minimizes E [Qa (kk, ax) - [r (sk, ax) + (Q& (5/+1, &Qo (sb+1)))].
4.2 EXPLORATION FOR AUCTION-FITTER Q-ITRRATION
How can we conduct exploration in Auction-fitted Q-iteration framework? Unfortunately, we can't use e-greedy method since such randomly altered assignment is very likely to cause a catastrophic result in problems with combinatorial nature.
In this paper, we suggest that parameter space exploration Plappert et al. 2017) can be applied. Recall that we use Qo ($k, a3) to get policy &Q. (sx). Note that e denotes all neural network param- eters used in the structure2vec iterations introduced in Section 5. Since Qo (#k, ag) is parametrized by 0, exploration with ΦQ. (sx) can be performed by exploration with parameter Such exploration in parameter space has been introduced in the policy gradient RL literature. While this method was originally developed for policy gradient based methods, exploration in parameter space can be par- ticularly useful in auction-fitted Q-iteration.
The detailed application is as follows. When conducting exploration, apply a random perturbation on the neural network parameters 0 in structure2vec. The resulting perturbation in the Q-function used for decision making via the auction- based policy Φo (sx) throughout that problem. Similarly, when conducting exploitation, the current surrogate Q-function is used throughout the problem.
7

---

Under review as a conference paper at ICLR 2020
Updates for the surrogate Q-function may only occur after each problem is complete (and typically after a group of problems).
5
EXPERIMENT
5.1 MRRC
For MRRC, we conduct a simulation experiment for a discrete time, discrete state environment. We use maze (see Figure I generator of UC Berkeley CS188 Pacman project [Neller et al. (2010) to generate large size mazes. We generated a new maze for every training and testing experiments.
Under the deterministic environment, the robot succeeds its movement 100%. Under stochastic environment, a robot succeeds its intended movement in 55% on the grid with dots and for every other direction 15% each; on the grid without dots, the rates are 70% and 10%. As described in section 2 routing problems are already solved. That is, each robot knows how to optimally (in expectation) reach a task. To find an optimal routing policy, we use Dijkstra's is algorithm for deterministic environments and dynamic programming for stochastic environments. The central assignment decision maker has enough samples of task completion time for every possible route.
We consider two reward rules: Linearly decaying rewards obey fage) = 200 age until reaching 0, where age is the task age when served; For nonlinearly decaying rewards, f(t) = X for À = 0.99. Initial age of tasks were uniformly distributed in the interval [0, 100).
Performance test. We tested the performance under four environments: deterministicllinear re- wards, deterministicnoonlinear rewards, stochastic/linear rewards, stochastic/nonlinaar rewards.
There are three baselines used for performance test: exact baseline, heuristic baseline, and indirect baseline. For the experiment with deterministic with linearly decaying rewards, an exact optimal solution for mixed-integer exists and can be used as a baseline. We solve this program using Gurobi with 60-min cut to get the bascline. We also implemented the most up-to-date heuristic for MRRC in [Ekici & Retharekar (2013)]. For any other experiments with nonlinearly decaying rewards or stochastic environment, such an exact optimal solution or other heuristics methods does not exist. In these cases, we should be conservative when talking about performance. Our strategy is to con- struct a indirect baseline using universally applicable algorithm called Sequential greedy algorithm (SGA) [Han-Lim Choi et al.) ]. SGA is a polynomial-time task allocation algorithm that shows decent scalable performance to both linear and non-linear rewards. For stochastic environments, we use mean task completion time for task allocation and re-allocate the whole tasks at every time- steps. We construct our indirect baseline as 'ratio between our method and SGA for experiments with deterministii-lineanli decaying rewards'. Showing that this ratio maintained for stochastic environments in both linear/nonlinear rewards suffices our purpose.
Table shows experiment results for (# of robots, # of tasks) (2, 20), (3, 20), (3, 30). (5, 30), (5, 40). (8, 40), (8, 50); For linear/deterministic rewards, our proposed method achieves near- optimality (all above 95% optimality). While there is no exact comparable performance base- line for experiments under other environments, indirect bascline (%SGA) at least shows that our method does not lose &SGA for stochastic environments compared with %SGA for deterministic environments in both linear and nonlinear rewards.
Scalability test. We count the training requirements for 93% optimality for seven problem sizes (# of robots NR, # of tasks Ny) (2, 20). (3, 20), (5.30) 30), (5, 40), (8, 40), (8, 50) with determinis- tic/linearly decaying rewards (we can compare optimality only in this case). As we can see in Table the training requirement shown not to scale problem size increases.
Transferability test. Suppose that we trained our learning algorithm with problems of three robots and 30 Tasks. We can claim transferabilitty of our algorithm if our algorithm achieves similar per- formance for testing with problems of 8 robots and 50 tasks when compared with the algorithm specifically trained with problems of 8 robots and 50 tasks, the same size as testing. Table shows our comprehensive experiment to test transeferability. The results in the diagonals (where training size and testing size is the same) becomes baseline, and can compare how the networks trained with different problem size did well compare to those results. We could see that lower-direction transfer tests (trained with larger size problem and tested with smaller size problems) shows only
8

---

Under review as a conference paper at ICLR 2020
Table 1: Performance (50 trials of training for each cases)
Robots (R)
Tasks (T)
Reward
Environment
Baseline
2R/201
3R/201
3R/30T
5R/30T
5K/40T
8R/40T
8R/50T
98.31%
97.50%
97.80%
95.35%
96.99%
96.11%
96.85%
Optimal
1:4.33
1:.71
15.14
#5.28
15,42
14.56
13.40
Deterministic
Ekisi et al.
99.45%
100%
82.65%
86.35%
92.25%
91.85%
80.60%
Linear
(%SGA)
(137.3)
(120.6)
(129.7)
(110.4)
(123.0)
(119.9)
(119.8)
Optimal (%SGA)
N/A
Stochastic
(130.9)
(115.7)
(122.8)
(115.6)
(122.3)
(113.3)
(115.9)
Optimal (%SGA)
N/A
Deterministic
(111.5)
(118.1)
(118.0)
(110.9)
(118.7)
(111.2)
(112.6)
Nonlinear
Optimal
N/A
Stochastic
(%SGA)
(110.8)
(117.4)
(119.7)
(111.9)
(120.0) (110.4)
(112.4)
Table 2: Scalability test (mean of 20 trials of training, linear & deterministic env.)
Testing size (Robot (R)
Task (1))
Linear & Deterministic
2R/20T
3R/20T
3R/30T
5R/30T
5R/40T
8R/0T
8R/50T
Performance with full training
98.31%
97.50%
97.80 77880%
95.35%
96.99%
96.11 10.11%
96.85%
# Training for 93% optimality
19261.2
61034.0
99032.7
48675.3
48217.5
45360.0
47244.2
small loss in performance. For upper-direction transfer tests (trained with smaller size problem and tested with larger size problem), the performance loss was up 4 percent.
Ablation study. There three components in proposed method: careful encoding of information using two-layers of structure2vec, 2) new structure2vec equation with random PGM and 3) an auction-based assignment. Each component was removed from the full method and tested to check the necessity of the component.
We test the performance in deterministic/lnnarly decaying rewards (so that there is an optimal solution available for comparison). The experimental results are shown in Figure 2 While the full method requires more training steps, only the full method achieves near-optimal performance.
5.2 IPMS
For IPMS, we test with continuous time, continuous state environment. While there have been many learning-based methods proposed for (single) robot scheduling problems, the best our knowledge our 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 to 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-dependent setup with no 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 section we want to minimize make-span. As benchmark for IPMS, we use Google OR-Tool, library
Table Transferability test (50 trials of training for each cases, linear & deterministic env.)
Testing Rize(Roobo(((///ask(()
Training size (Robot(R)/ass(TT)
2R/20T
3R/20T
3R/30T
5R/30T
5R/4TT
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%
93.28%
92.63%
92.40%
5R/40T
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%
94.86%
96.85%

---

Under review as a conference paper at ICLR 2020
1.0
Performance (% optimality)
0.6
ours
single layer
0.2
heuristic PGM
# training steps (1 training step / episades)
Figure 2: Tested with 1) single layer, 2) heuristic PGM 3) Max- Max-operation
Table 4: IPMS test results for makespan minimization (our algorithm / best Google OR tool result)
Makespan minimization for
Machines 5
Deterministic environment
3
7
10
50
106.7%
117.0%
119.8%
116.7%
Tasks
75
105.2%
109.6%
113.9%
111.3%
100
100.7%
111.0%
109.1%
109.0%
Google 2012). 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 Table 4 Makespan obtained by our method divided by the makespan obtained the baseline is provided. Although our method has limitations problems with a 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.
6 CONCLUSIONS
We presented a learning- based method that achieves the first success for molti-robot/mmcchie scheduling problems in both challenges: scalable performance and tranferabilityy We identified that robot scheduling problems have an exact representation as random PGM. We developed mean- field inference theory for random PGM and extended structure2vec method of Dai et al.] (2016). To overcome the limitations of fitted Q-iteration, heuristic auction that was enabled by transfer- ability is suggested. Through experimental evaluation, we demonstrate our method's 's success for MRRC problems under determinnssticsstocassie environment. Our method also claims to be the first learning- based algorithm that achieves scalable performance among machine scheduling algo- rithms; our method achieves comparable performance in a scalable manner.
Our method for MRRC problems can be easily extended to ride-sharing problems or package de- livery problems. Given a of all user requests serve, those problems can be formulated MRRC problem. For both ride-sharing and package delivery, it is reasonable to assume that the utility of user depends on when she is completely serviced. We can model how the utility of user decreases over time since when it appears and set the objective function of problems as max- imizing total collected user utility. Now consider a task 'deliver user (or package) from to B'. This is actually a task "Move to location A and then move to location B". If we know the comple- tion time distribution of each move (as we did for MRRC), the task completion time is simply the sum of two random variables corresponding to task completion time distribution of the moves in the task. Indeed, ride-sharing or package delivery problems are of such tasks (We can ignore charging moves for simplicity, and also we don't 't have to consider simple relocation of vehicles or robots since we don't 't consider random customer arrivals). Therefore, both ride-sharing problems and package delivery problems be formulated as MRRC problems.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural Combi- natorial Optimization with Reinforcement Learning. Annual Review of Cell and Developmental Biology, 15(1):81-12, nov 2016. ISSN 1081-0706. doi: 10. 1
15.1.11.
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 depen- dent rewards. Computers and Industrial Engineering, 64(4):1009--0118 2013, ISSN 03608352. doi: 10. 10.1016/j.iee20113.01
URL http://aa..oo...rg//0000001///.. 2011.
010
Google. Google OR-Tools, 2012.
URL http:://eevelopezssgooglls
optimi zatiinn/
Han-Lim Choi, Luc Brunet, and J.P. How. Consensus-Bas -asse Decentralized Auctions for Robust
Task Allocation. IEEE Transactions on Robotics, 25(4):912-926, aug 2009. ISSN 1552-3098. doi: 10.1 N0.1099/TR0.20092222244
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! mar 2018.
M E Kurz, R G Askin, M E Kurzy, and R G Askiny. Heuristic scheduling of parallel machines with sequence-dependen set-up times. International Journal of Production Research, 39(16): 3747-3769, 2001. ISSN 0020-7543. doi: 10. 10.10800002075401 10064938.
Yuxi Li. DEEP REINFORCEMENT LEARNING: AN OVERVIEW. 2017. URL https:/ //
arxiv. ortppdf..g/pf..oooo /1701. 07204. fdd
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáč. Reinforcement 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-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), pp. 1919-1921, 2010.
Shayegan Omidshafici, AliAkbar AghaMohammadi, Christopher Amato, Shih Yuan Liu, Jonathan 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.117702733649176922
Matthias Plappert. Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y. Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter Space Noise for Explo- ration. pp. 1-18, 2017.
Rajesh Ranganath, Dustin Tran, and David M. Blei. Hierarchical Variational Models. 2015.
Daniel Ritchie, Paul Horsfall, and Noah D. Goodman. Deep Amortized Inference for Probabilistic Programs. pp. 1-31, 2016. httL:tttpp//axii.ooooo hwapgg/bbs/155 05735
Federico Rossi, Saptarshi Bandyopadhyay, Michael Wolf, and Marco Pavone. Review of Multi- Agent Algorithms for Collective Behavior: Structural Taxonomy. PapC-PapersOnL.ine, 51(12): 112-117, 2018. ISSN 24058963. doi:
Hado van Hasselt, Arthur Guez, and David Silver. Deep Reinforcement Learning with Double Q-learning. 2015.
11

---

Under review as a conference paper at ICLR 2020
Tingwu Wang, Renjie Liao, Jimmy Ba, and Sanja Fidler. NerveNet: Learning Structured Policy with Graph Neural Networks. In International Conference on Learning Representations, 2018.
A MRRC WITH CONTINUOUS STATE/CONTINUOUS TIME SPACE FORMULATION, OR WITH SETUP TIME AND PROCESSING TIME
In continuous state/continuous time space formulation, the initial location and ending location of robots and tasks are arbitrary on I22. At every moment at least a robot finishes task, we make assignment decision for free robot(s). We call this moments as 'decision epochs' and express them as an ordered set (41, f2, ...., ......). ). Abusing this notation slightly, we use (-)s, = (-)s-
Task completion time can consist of three components: travel time, setup time and processing time. While a robot in the travel phase or setup phase may be reassigned to other tasks, we can't reassign a robot in the processing phase. Under these assumptions, at each decision epoch robot r; is given set of tasks it can assign itself: if it is in the traveling phase setup phase, it can be assigned to any tasks or not assigned; if it is in the processing phase, must be reassigned to its unfinished task. This problem can be cast Markov Decision Problem (MDP) whose state, action, and reward are defined as follows:
State. State S at decision epoch i is a directed graph G. (R, Tk, Eg): Rs is the set of all robots and Ta is the set of all tasks; The set of directed edges & E Crit, E E is a random variable which denotes task completion time of robot in R2 to service task j in To and a directed edge ct,t, E gTT denotes a task completion time of a robot which just finished serving task i in Ta to service task j in Te. EKT contains information about each robot's s U, where ET is a singleton set if robot i is in the processing phase
ERT UE% where a directed edge
possible assignments: E and it must be assigned to its unfinished task, and otherwise it is the set of possible assignments from robot r; to remaining tasks that are not in the processing phase.
Action. The action ag at decision epoch & is the joint assignment of robots given the current state 8% Gz- The feasible action should satisfy the two constraints: No two robots can be assigned to task; some robots may not be assigned when number of robots are more than remaining tasks. To best address those restrictions, we define an action ag time t maximal bipartite matching in bipartite sub-graph ((R, U Tk),, e of graph GR. For example, robot in R2 is matched with task j in Ty in action dę if we assign robot to task j decision epoch t. We denote the set of all possible actions at epoch l as Ag.
Reward. In MRRC, Each task has arbitrarily determined initial age. At each decision epoch, the age of each task increases by one. When a task is serviced, a reward is determined only by its age when serviced. Denote this reward rule R(k). One easily see that whether task is served at epoch & is completely determined by Sj. Og and 8841- Therefore, we can denote the reward we get with Sk, ag and 5k+1 as R(sk, ake 8k+1).
Objective. We can now define an assignment policy & as a function that maps a state to action ag. Given 8n initial state, an MRRC problem can be expressed problem of finding an optimal assignment policy o² such that
= argmax E
Σ R (5y, ag 8641) 150
B IDENTICAL PARALLEL MACHINE SCHEDULING PROBLEM FORMULATION
As written in 2.2 IPMS is problem defined in continuous state/continuous time space. Machines are all identical, but processing times of tasks are all different. In this paper, we discuss IPMS with "sequence-deependent setup time'. A machine's 's setup time required for servicing a task is determined by its previously served task j. In this case, the task completion time is the sum of setup time and processing time. Under this setting, objective discussed in [Kurz et al.) (200T)) (The constraints are different in this problem though); That is, minimizing total time spent from start to end to finish all tasks.
solve IPMS problem for make-span minimization
12

---

Under review as a conference paper at ICLR 2020
Every time there is a finished task, make assignment decision for a free machine. We call this times as 'decision epochs' and express them as an ordered set (f1, (2,,2,..., tg....). Abusing this notation slightly, use (+)s, = (-)x.
Task completion time for a machine to a task consists of two components: processing time and setup time. While machine in setup phase may be reassigned to another task, can't reassign machine the processing phase. Under these assumptions, at each epoch, a machine r; is given a of tasks can assign: if is in the setup phase, it can be assigned any tasks not assigned; if it is in the processing phase, it must be reassigned to its unfinished task. This problem can be cast as Markov Decision Problem (MDP) whose state, action, and reward are defined as follows:
State. State Sk at decision epoch k is a directed graph GE = (RR U Tx. RR is the set of all machines and Tk is the set of all tasks; The set of directed edges Es = E U where directed edge er,t, E is random variable which denotes task completion time of machine i in Rx to service task j TE and a directed edge ct,t, E E denotes task completion time of a machine which just finished serving task i in Ts to service task j in Tk- E contains information about each robot's possible assignments: &RT U,Eg' where g a singleton set if machine is in the processing phase and it must be assigned to its unfinished task, and otherwise it is the set of possible assignments from machine rę to remaining tasks that are not in the processing phase.
Action. Defined the same as MRRC with continuous state/time space.
Reward. IPMS, time passes between decision epoch I and decision epoch / + 1. Denote this time as T₁. One easily see that Tj is completely determined by Sk, ag and 8k+1. Therefore, we can denote the reward we get with 8k, dg and 8k+1 as T(sk: ak; 8k+1).
Objective. We can now define assignment policy & as a function that maps state są action ag. Given 8p initial state, an MRRC problem can be expressed as a problem of finding an optimal assignment policy o' such that
Φ" argmin E
T (sk, Ck, 82+1)
C BAYESIAN NETWORK REPRESENTATION
Here we analytically show that robot scheduling problem randomly induces random Bayesian Network from state st. Given starting state st and action a, a person can repeat a 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 a 'scenario'. For example, suppose that at time-step t
given robots {A, B), tasks {1, 2, 4, 5), and policy 6. One possible scenario S* can be (robot serves task 3 > 1 - 2 and robot В serves task 5 4). Define random variable X₃ a task characteristic, e.g. 'The time when task k is serviced'. The question is, 'Given scenario S*,, what is the relationship among random variables {Xa}") Recall that in our sequential decision making formulation we are given all the 'task completion time' information in the description. Note that, task completion time is only dependent on the previous task and assigned task. In our example above, under scenario S 'when task 2 is served' is only dependent on "when task is served'. That is, P(X, X3. relationship is called 'conditional independence'. Given a scenario S every relationship among S* can be expressed using this kind of relationship among random variables. A graph with this special relationship is called 'Bayesian Network' [Koller & Friedman (2009)), probabilistic graphical model.
XXX St). This
D PROOF OF THEOREM 1.
We first define necessary definitions for our proof. In a random PGM, a PGM is chosen among all possible PGMs on {Xx) and semi-eliques C. Denote the set of all possible factorization as F S2.,S..... ...,Sy) } where a factorization with index & is denoted as Sg C C. Suppose we are given P([S = Sm
13

---

Under review as a conference paper at ICLR 2020
For each semi-clique D' in C, define binary random variable V F - {0, 1} with value for the factorization that does not include semi-clique Di and value 1 for the factorization that include semi-clique Di Let V be random vector V = (V1, V2 ,..., Viei). Then we can express
.V. P(X,,....x,I1V)) x II [ot (Di)]* We denote [ (Di)] V as (Di).
c
Given {P([S = Sm })). each semi-clique D presence probability ps can be simply calculated; clique i's presence probability ps simply the sum of probabilities of all factorizations which in- clude clique i, that is, p, mm.Diss... P P(SS- = =m
Now we prove Theorem
In mean-field inference, want to find distribution Q xx)= Qi(X.) such that cross-entropy between and target distribution minimized. Following the notation in Koller & Friedman (2009). the mean field inference problem can written as the following optimization problem.
min [X. x.,V))
D
Q
(.) =1 Vi
s.t.
Here ID (TI, Q: PX.......... X,IV)) can be expressed D (II, Q: P PXI Eq In (II, Q.) - EQ [n ( X,(V))).
Note that
Be In (Lul we (D'. (Di.1)]
Eq [In (P (A,
Xal v)) Xn/V)
w (D', Vn )
=EQ
ln
Eq
V In (0 (D'))
EBqIn(()
[
Eq [V' (Ø² (Di)) - Eo[In(Z)]
[0]
Ey. [Eq [ In (6 (D*)) [r] [2)]
[e]
P P(v =1) [EQ [In (Ø' (Di))] [n(ln(2)
[
Σ Pa [Bq [In (ot (D)))] Eq(In(Z))
Hence, the above optimization problem can be written as
C
max
EQ
Σ
Pr In (6' (Di))
+ Eq
(In Q:)
1=1
1=1
s.t. Σ (x.)=
=1 Vi
14

---

Under review as a conference paper at ICLR 2020
In
Koller & Friedman (2009). the fixed point equation is derived by solving analogous equation
to
without the presence of the p,. Theorem 1 follows by proceeding as in Koller & Friedman with straightforward accounting for pj-
2009
E
PROOF OF LEMMA 1.
Since assume semi-cliques only between two random variables, denote DD and presence probabilities as } 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
p ([H+} (X++) & II
(H&)
II V (Ha)H.).
KEV
K
Expanding the fixed-point equation for the mean field inference from Theorem 1, we obtain:
1
E(Di-(HAH) [In 1/ (Hx hha 1na/D')]
Qk (ha) = exp
Zs
In Φ (Hp = hx( + Σ Qs (h.) In (H+ = hu (H,) dhg
Zk
iEV H
This fixed-point equation for Qu (ha) is function of (Q, (h₂)) jeu such that
Qk (hx) (hx, 22, (pk, Qi (hg)) jym)
As in Dai et al. (2016), this equation can be expressed as a Hilbert space embedding of the form
Nu = 7 о (IR (PEskj
where üi indicates a vector that encodes Qu (ha) In this paper, we use the nonlinear mapping Ý (based on neural network form suggested in Dai al. (2016):
WiTK W₂ Σ Pkjli
J#k
F PRESENCE PROBABILITY INFERENCE
Let V denote the set nodes. In lines and 2, the likelihood of the existence of a directed edge from each node to node n is computed by calculating W1 (relu (W2ufn)) and averaging over the M samples. In lines 3 and 4, we use the soft-max function to obtain Pm,
1 For m, n E V.Vo do
2 Jmn 1 DM Wi (relu (Wzuthn))
3 For m, n E 1 do
c9mm/r
4 Pm, Ejer esma/r.
G TASK COMPLETION TIME AS A RANDOM VARIABLE
We combine random sampling and inference procedure suggested in section 3.2 and Figure 1 note the set of task with a robot assigned to it as T Denote a task in 7 as f, and the robot assigned to & Tt. The corresponding edge in etT for this assignment is cr, The key idea is to use samples of Cr to generate N number of sampled Q(s, a) value and average them to get the estimate of El ( (8, a)). First, for I 1... N conduct the following procedure. For each task I,
De-
15

---

Under review as a conference paper at ICLR 2020
in TA, we sample data e/,, Using those samples and (pty). we follow the whole procedure illustrated in section 3.2 to get Q(s,a)'. Second, we get the average of {Q(s, a) to get the estimate of F(Q((s, a)). E (ss,a)*.
i=N
The complete algorithm of section 3.2 with task completion time as a random variable given as below.
age; = age node
2 The set of nodes for assigned tasks TA
3 Initialize {ug (0) ), )
4 for = to N:
5 for t, E T:
5
if E T do: sample en,, from 6
6
7
2; 7
clse: 2; = 10
for = 1 to Ti do
11
for E V do
12
4 = jev Pjilly
(t-1)
13
14 (t) relu (Wali W4rs)
14
T Concatenate
(4 ,
(T1) ,ge;
15
for = 1 to 72 do
16
for e V do
17
4 = Ejev (t-1)
18
7, (8)
relu (Woli + We).)
Qi = W7 >i (T)
19
20
Qavg = 1. ΣN Qi
16


Reviews:
[{"review_id": "rkgBtXVhFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "In this paper, the authors propose a reinforcement learning method for multi-robot scheduling problems. They state the method's scalable performance and transferability. My major concerns are as follows.\n\n1. The paper is not easy to read. In my understanding, multi-robot scheduling is a very important problem and is very similar to many scheduling problems in complex platforms such as the dispatch system for ride sharing and package delivery. However, I did see any real application in this paper. It is very difficult to understand how this proposed method works and what is the benefit under non trivial environment.\n\n2. The experiments (2~8 robots, 20~50 tasks) cannot support the scalable performance or large problems very well. How about thousands and millions of robots/tasks, e.g. routing planning or dispatching for vehicles in a ride sharing platform?  \n\n3. It is not convincing without comparison with necessary baseline methods.\n\n4. There is no in-depth analyses for the transferability.\n\n5. There are many typos, such as the missing figure citation with Figure ??.   \n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Hkg7ErgLcr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 authors study a combinatorial multi-robot scheduling problem (in fact the robot part is a bit inflated, since the experiments only involve agents in a simulated discrete state-space maze) using a method that builds upon recent advances from [Dai et al. (2017)]. The main contribution is to consider each of the steps taken by Dai et al. to solve combinatorial problems on graphs, and adapt them to the considered scheduling problem.\n\nNot being an expert in RL, my assessment should be discounted. However, I am not sure I follow properly the main idea of the paper. The point of Dai et al. was to use RL to solve a wide family of combinatorial problems. Now, the authors claim to build upon these ideas to solve... what looks essentially like a far more standard RL problem, and not necessarily a combinatorial optimization problem. The main insight by Dai et al. was to highlight the fact that combinatorial problems are usually solved (or approximated) without \"warm starts\", i.e. they do not consider distributions on problem instances to learn from. The problem considered by the authors is, quite on the contrary, a typical RL problem where information is extracted from the problem's structure (here a maze). Therefore, I feel there is something of a fundamental contradiction going on at a fairly high-level, in the sense that the paper \"uses RL to solve a subset of combinatorial problems that were studied by RL before\". The absence of other baselines in experiments make this even more suspicious. Therefore I believe the paper's presentation could be greatly improved if it were better \"located\" within the RL literature (which is almost non-existent in the very brief bibliographic section) and that the authors were able to show that  their proposals are original, within an RL context.\n\nminor points:\n* the comment \"While learning-based methods are generally believed to suffer exponentially increasing training requirements as problem size (number of robots and tasks) increases, our method’s training requirement is empirically shown not to scale while maintaining near-optimal performance\" --> this is too loose a statement. Provide more evidence or references.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BkxFKINy5S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Paper addresses the problem of centralized multi-machine task assignment in an RL setting (\"multi-robot reward collection\"). Claim is that this has not been successfully done in a RL setting before, so a new problem is proposed (multi-agent pac-man) and results are presented on this problem. Approach proposed extends prior work from Dai 2017 and 2016 (which I am a priori unfamiliar with), and it seems to me that the exposition of this method leans a bit too heavily on presumed familiarity with those works. An auction-consensus approach is proposed whereby each machine makes a bid for each unclaimed task, then the coordinator picks the highest bid and assigns that task-machine pairing, after which the remaining machines make bids for the remaining tasks, and so forth.\n\nAs it stands, part of me leans toward rejecting for a couple reasons.\n1. The exposition of the method needs to be improved to assume less background knowledge of the heuristic PGM and  structure2vec methods, investing some text introducing them. Appendix C seems to do part of this, and probably should be integrated into the body of the paper.\n2. Another view of \"random graphical models\" is the sampling trace of a universal PPL. This is studied in, e.g. https://cocolab.stanford.edu/papers/daipptr.pdf so it seems like this deserves at least a brief additional literature review as opposed to simply diving into MFI. Appendix D looks OK: since the action space is discrete, then a fixed point approach becomes feasible.\n\nOn the other hand, the experiments are good, the auction approach is a nice idea/novel. The ablation experiment is good, and the comparison against OR tools is also good to have. Insofar as the structure2vec is representation-oriented, it seems like a decent fit to the venue.\n\nOn balance, I think the paper needs too much polish and revision to accept at this time.\n\nMinor nits:\nThe word \"seminar\" is used a couple times, where from context I think \"seminal\" is intended.\nSome figure refs are broken.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Unfortunately, the reviewers of the paper are all not certain about their review, none of them being RL experts.  Assessing the paper myself—not being an RL expert but having experience—the authors have addressed all points of the reviewers thoroughly.  

Decision: Reject