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. Suppose that we are given a set of robots and seek to serve a set of spatially distributed tasks. A reward is given for serving each task promptly -resulting in a time-decaying reward collection problem -or when completing the entire set of tasks -resulting in a makespan minimization problem. As the capability to control and route individual robots has increased [Li (2017) ], efficient orchestration of robots arises as an important remaining concern for such problems. Multi-robot planning problems. In this paper, we focus on orchestration problems that can be formulated as robot planning problems. A key assumption in such orchestration problems is that we are given information on the "duration of time required for an assigned robot to complete a task". This duration may be deterministic (e.g. as in a Traveling Salesman Problem (TSP) or Vehicle Routing Problem (VRP)) or random with given probability distribution (c.f., [Omidshafiei et al. (2017) ]). 1 . 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 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 s at each decision step, they select the next task a to minimize the future cost estimate. [Dai et al. (2017) ]'s 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 as a probabilistic graphical model (PGM) [Koller & Friedman (2009) ]. 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 Q(s, a) can be learned by the reinforcement framework called fitted Q-iteration. We create a 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 heuristically 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 corresponding new structure2vec iteration. 2. Sequential encoding of information for transferability. To achieve transferability in terms of the number of robots and tasks, we carefully design a two-step hierarchical mean-field inference [Ranganath et al. (2015) ]. Each step is designed to infer certain information. The first step is designed to infer each task's relative graphical distance from the robots. 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. (2015) ]. That is, the relative magnitudes of Q(s, a) values are sufficient to select an action a. 3. Auction-based assignment. Even if we can infer Q(s, a) precisely, the computation time required to select an action a 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 transferability of our Q(s, a) inference. Even though this heuristic auction selects a 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.) time τ i to 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-dependent 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 i 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. The IPMS formulation resembles our MRRC formulation in continuous-time and continuous-space and we relegate the detailed formulation to Appendix B. We presented a learning-based method that achieves the first success for multi-robot/machine scheduling problems in both challenges: scalable performance and tranferability. We identified that robot scheduling problems have an exact representation as random PGM. We developed a meanfield inference theory for random PGM and extended structure2vec method of Dai et al. (2016) . To overcome the limitations of fitted Q-iteration, a heuristic auction that was enabled by transferability is suggested. Through experimental evaluation, we demonstrate our method's success for MRRC problems under a deterministic/stochastic environment. Our method also claims to be the first learning-based algorithm that achieves scalable performance among machine scheduling algorithms; our method achieves a comparable performance in a scalable manner. Our method for MRRC problems can be easily extended to ride-sharing problems or package delivery problems. Given a set of all user requests to serve, those problems can be formulated as a MRRC problem. For both ride-sharing and package delivery, it is reasonable to assume that the utility of a user depends on when she is completely serviced. We can model how the utility of a user decreases over time since when it appears and set the objective function of problems as maximizing total collected user utility. Now consider a task 'deliver user (or package) from A to B'. This is actually a task "Move to location A and then move to location B". If we know the completion 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 have to consider simple relocation of vehicles or robots since we don't consider random customer arrivals). Therefore, both ride-sharing problems and package delivery problems can be formulated as MRRC problems. 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 R 2 . At every moment at least a robot finishes a task, we make assignment decision for a free robot(s). We call this moments as 'decision epochs' and express them as an ordered set (t 1 , t 2 , . . . , t k , . . . ). Abusing this notation slightly, we use (·) t k = (·) k . 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 i is given a set of tasks it can assign itself: if it is in the traveling phase or setup phase, it can be assigned to any tasks or not assigned; if it is in the processing phase, it must be reassigned to its unfinished task. This problem can be cast as a Markov Decision Problem (MDP) whose state, action, and reward are defined as follows: R k is the set of all robots and T k is the set of all tasks; The set of directed edges where a directed edge is a random variable which denotes task completion time of robot i in R k to service task j in T k and a directed edge titj ∈ E T T k denotes a task completion time of a robot which just finished serving task i in T k to service task j in T k . E RT k contains information about each robot's possible assignments: , where E ri t is a singleton set if robot i is in the processing phase and it must be assigned to its unfinished task, and otherwise it is the set of possible assignments from robot r i to remaining tasks that are not in the processing phase. Action. The action a k at decision epoch k is the joint assignment of robots given the current state s k = G k . The feasible action should satisfy the two constraints: No two robots can be assigned to a 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 a k at time t as a maximal bipartite matching in bipartite sub-graph ((R k ∪ T k ), E RT k ) of graph G k . For example, robot i in R k is matched with task j in T k in an action a k if we assign robot i to task j at decision epoch t. We denote the set of all possible actions at epoch k as A k . Reward. In MRRC, Each task has an 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 as R(k). One can easily see that whether a task is served at epoch k is completely determined by s k , a k and s k+1 . Therefore, we can denote the reward we get with s k , a k and s k+1 as R(s k , a k , s k+1 ). Objective. We can now define an assignment policy φ as a function that maps a state s k to action a k . Given s 0 initial state, an MRRC problem can be expressed as a problem of finding an optimal assignment policy φ * such that
RL can solve (stochastic) multi-robot/scheduling problems scalably and transferably using graph embedding
{"src": "scitldr-AIC_train", "paper_id": "rJxRJeStvB"}