Constrained Shortest Path Search with Graph Convolutional Neural Networks

Constrained Shortest Path Search with Graph Convolutional Neural Networks

Kevin Osanlou1,3, Christophe Guettier1, Andrei Bursuc2, Tristan Cazenave3, Eric Jacopin4, 1

Safran Electronics & Defense 2

Safran SA

1. LAMSADE, Universite Paris-Dauphine´
2. MACCLIA, Ecoles de Saint-Cyr Coetquidan¨

kevin.osanlou@safrangroup.com christophe.guettier@safrangroup.com andrei.bursuc@safrangroup.com

tristan.cazenave@lamsade.dauphine.fr eric.jacopin@st-cyr.terre-net.defense.gouv.fr

Abstract

Planning for Autonomous Unmanned Ground Vehicles (AUGV) is still a challenge, especially in difficult, off-road, critical situations. Automatic planning can be used to reach mission objectives, to perform navigation or maneuvers. Most of the time, the problem consists in finding a path from a source to a destination, while satisfying some operational constraints. In a graph without negative cycles, the computation of the single-pair shortest path from a start node to an end node is solved in polynomial time. Additional constraints on the solution path can however make the problem harder to solve. This becomes the case when we need the path to pass through a few mandatory nodes without requiring a specific order of visit. The complexity grows exponentially with the number of mandatory nodes to visit. In this paper, we focus on shortest path search with mandatory nodes on a given connected graph. We propose a hybrid model that combines a constraint-based solver and a graph convolutional neural network to improve search performance. Promising results are obtained on realistic scenarios.

1. Introduction

Autonomous unmanned ground vehicle (AUGV) operations are constrained by terrain structure, observation abilities, embedded resources. Missions must be executed in minimal time, while meeting objectives. This is the case, for examples, in disaster relief, logistics or area surveillance, where maneuvers must consider terrain knowledge. In most of applications, the AUGV ability to maneuver in its environment has a direct impact on operational efficiency.

AUGV integrates several perception capabilities (on-line mapping, geolocation, optronics, LIDAR) in order to update its situation awareness on-line. This knowledge is used by various on-board planning layers to maintain mission goals, provide navigation waypoints and dynamically construct platform maneuvers. Resulting actions and navigation plans are used for controlling the robotic platform. Once the plans are computed, the AUGV automatically manages its trajectory and follows the navigation waypoints using control algorithms and time sequence. Such autonomous system architectures are challenging, especially because some mission data (terrain, objectives, available resources) are known offline and others are acquired on-line. The planning problem also involves technical actions (observations, measurements, communications, etc.) to realize on some mandatory waypoints along the navigation plan [Guettier and Lucas, 2016].

Figure 1 presents the eRider, a UGV that has high mobility abilities, and is able to perform cross-over maneuvers on difficult terrain for exploring disaster areas.

The paper focuses on the automatic planning algorithms, and more specifically, on the ability to guide the problem solving with machine learning techniques.

For such problems, classical robotic systems integrate A* algorithms [Hart et al., 1968], as a best-first search approach in the space of available paths. For a complete overview of static algorithms (such as A*), replanning algorithms (D*), anytime algorithms (e.g. ARA*), and anytime replanning algorithms (AD*), see [Ferguson et al., 2005]. Representative applications to autonomous systems can be very realistic, as reported in [Meuleau et al., 2009] and [Meuleau et al., 2011]. Algorithms stemming from A* can handle some heuristic metrics but can become complex to develop when dealing with several constraints simultaneously like mandatory waypoints and distance metrics. Our approach combines a Constraint Programming (CP) method, with novel machine learning techniques. CP provides a powerful baseline to model and

[pic 1]

Figure 1: The eRider, developed by SAFRAN, is an all-purpose optionally piloted vehicle that can patrol a given area, observe at long range or carry goods for various off-road applications in difficult environments. These specific vehicles can be either piloted or turned instantaneously into AUGV.

solve combinatorial and / or constraint satisfaction problems (CSP). It has been introduced in the late 70s [Lauriere, 1978` ] and has been developed until now [Hentenryck et al., 1998; Ajili and Wallace, 2004; Carlsson, 2015], with several realworld autonomous system applications, in space [Bornschlegl et al., 2000; Simonin et al., 2015], aeronautics [Guettier et al., 2002; Guettier and Lucas, 2016] and defense [Guettier et al., 2015].

Convolutional neural networks (CNNs) have proven to be very efficient when it comes to image recognition [Krizhevsky et al., 2012]. They use a variation of multilayer perceptrons designed to require minimal preprocessing, and are capable of detecting complex patterns in the image. In this paper, we are dealing with graphs representing maneuvers or off-road navigation. Instead of CNNs, the paper focuses on graph convolutional neural networks (GCNNs), a recent variant for learning complex patterns in graph data. We show that GCNNs are capable of making decisions to solve path-related problems. In this work we combine this type of machine learning algorithms with constraint solving methods for planning.

The paper is organized as follows. The first section (§ 2) describes AUGV mission, environment and applications. The following section (§ 3) presents the CP approach, problem formalization and resolution. Section (§ 4) describes the graph-based learning algorithm and section (§ 5) the data generation schema for training. Last sections (§ 6) and (§ 7) discuss results, highlight further work and conclude. Related works are provided along the different sections.

1. Context and problem presentation

In modern AUGV architectures, path planning is performed on the fly, responding to an operator demand (mission update), a terrain obstacle, or free space discovery. In logistics, such operator demands correspond to movement requests for pick-up and delivery, while in area surveillance or disaster relief, the platform must reccon some specific areas.