Differentiable planning network architecture has shown to be powerful in solving transfer planning tasks while possesses a simple end-to-end training feature. Many great planning architectures that have been proposed later in literature are inspired by this design principle in which a recursive network architecture is applied to emulate backup operations of a value  iteration algorithm. However existing frame-works can only learn and plan effectively on domains with a lattice structure, i.e. regular graphs embedded in a certain Euclidean space. In this paper, we propose a general planning network, called Graph-based Motion Planning Networks (GrMPN), that will be able to i) learn and plan on general irregular graphs, hence ii) render existing planning network architectures special cases. The proposed GrMPN framework is invariant to task graph permutation, i.e. graph isormophism. As a result, GrMPN possesses the generalization strength and data-efficiency ability. We demonstrate the performance of the proposed GrMPN method against other baselines on three domains ranging from 2D mazes (regular graph), path planning on irregular graphs, and motion planning (an irregular graph of robot configurations). Reinforcement learning (RL) is a sub-field of machine learning that studies about how an agent makes sequential decision making (Sutton et al., 1998) to interact with an environment. These problems can in principle be formulated as Markov decision process (MDP). (Approximate) Dynamic programming methods such as value iteration or policy iterations are often used for policy optimization. These dynamic programming approaches can also be leveraged to handle learning, hence referred as model-based RL (Kober et al., 2013) . Model-based RL requires an estimation of the environment model hence is computationally expensive, but it is shown to be very data-efficient. The second common RL paradigm is model-free which does not require a model estimation hence has a lower computation cost but less data-efficiency (Kober et al., 2013) . With a recent marriage with deep learning, deep reinforcement learning (DRL) has achieved many remarkable successes on a wide variety of applications such as game (Mnih et al., 2015; Silver et al., 2016) , robotics , chemical synthesis (Segler et al., 2017) , news recommendation (Zhang et al., 2019) etc. DRL methods also range from model-based (Kurutach et al., 2018; Lee et al., 2018a) to model-free (Mnih et al., 2015; Heess et al., 2015) approaches. On the other hand, transfer learning across tasks has long been desired because it is much more challenging in comparison to single-task learning. Recent work (Tamar et al., 2016) has proposed a very elegant idea that suggests to encode a differentiable planning module in a policy network architecture. This planning module can emulate the recursive operation of value iterations, called Value Iteration Networks (VIN) . Using this network, the agent is able to evaluate multiple future planning steps for a given policy. The planning module is designed to base on a recursive application of convolutional neural networks (CNN) and max-pooling for value function updates. VIN not only allows policy optimization with more data-efficiency, but also enables transfer learning across problems with shared transition and reward structures. VIN has laid foundation for many later differentiable planning network architectures such as QMDP-Net (Karkus et al., 2017) , planning under uncertainty (Gupta et al., 2017) , Memory Augmented Control Network (MACN) (Khan et al., 2018) , Predictron (Silver et al., 2017) , planning networks (Srinivas et al., 2018) etc. However, these approaches including VIN is limited to learning with regular environment structures, i.e. the transition function forms an underlying 2D lattice structure. Recent works have tried to mitigate this issue by resorting to graph neural networks. These work exploit geometric intuition in environments which have irregular structures such as generalized VIN (Niu et al., 2018) , planning on relational domains (Toyer et al., 2018; Bajpai et al., 2018) , (Ma et al., 2018) , automated planning for scheduling (Ma et al., 2018) , etc. The common between these approaches are in the use of graph neural networks to process irregular data structures like graphs. Among these frameworks, only GVIN is able to emulate the value iteration algorithm on irregular graphs of arbitrary sizes, e.g. generalization to arbitrary graphs. GVIN has a differentiable policy network architecture which is very similar to VIN. GVIN can also have a zero-shot planning ability on unseen graphs. However, GVIN requires domain knowledge to design a graph convolution which might limit it to become a universal graph-based path planning framework. In this paper, we aim to demonstrate different formulations for value iteration networks on irregular graphs. These proposed formulations are based on different graph neural network models. These models are capable of learning optimal policies on general graphs where their transition and reward functions are not provided a priori and yet to be estimated. These models are known to be invariant to graph isomorphism, therefore they are able to have a generalization ability to graphs of different sizes and structures. As a result, they enjoy the ability of zero-shot learning to plan. Specifically, it is known that Bellman equations are written as the form of message passing, therefore we propose using message passing neural networks (MPNN) to emulate the value iteration algorithm on graphs. We will show two most general formulations of graph-based value iteration network that are based on two general-purpose approaches in the MPNN family: Graph Networks (GN) and Graph Attention Networks (GAT) (Velickovic et al., 2018) . In particular, our contributions are three-fold: • We develop a MPNN based path planning network (GrMPN) which can learn to plan on general graphs, e.g. regular and irregular graphs. GrMPN is an differentiable end-to-end planning network architecture trained via imitation learning. We implement GrMPN via two formulations that are based on GN and GAT. • GrMPN is a general graph-based value iteration network that will render existing graphbased planning algorithms special cases. GrMPN is invariant to graph isomorphism which enables transfer planning on graphs of different structure and size. • We will demonstrate the efficacy of GrMPN which achieves state of the art results on various domains including 2D maze with regular graph structures, irregular graphs, and motion planning problems. We show that GrMPN outperforms existing approaches in terms of data-efficiency, performance and scalability.
We propose an end-to-end differentiable planning network for graphs. This can be applicable to many motion planning problems
{"src": "scitldr-AIC_train", "paper_id": "HkxLiJSKwB"}