There has recently been some success in the use of reinforcement learning methods for single robot combinatorial optimization problems. In this paper, we develop the first learning-based method for multi robot/machine planning problems with combinatorial nature. One real-world concern is the capability to achieve transferability to 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, we illustrate how to represent a robot planning problem as an extension of probabilistic graphical models (PGMs) which we refer to as random PGMs. We develop a 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 a two-step sequential process. Third, we resolve the computational scalability issue of fitted Q-iteration. This is achieved by employing an auction-based heuristic as a 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 multirobot reward collection (MRRC). For such problems, with determinsitic assumptoins, we scalably achieve 97% optimality with transferability. This optimality is maintained under stochastic contexts. By extending our method to a continuous time, continuous space formulation, the approach is the first learning-based method for machine scheduling problems. Our method scalably achieves comparable performance to popular metaheuristics when applied to identical parallel machine scheduling (IPMS) problems in a deterministic context.
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.
Not 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.
minor points:
* 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.