Neural weighted A* : learning graph costs and heuristics with differentiable anytime A*

Recently, the trend of incorporating differentiable algorithms into deep learning architectures arose in machine learning research. The fusion of neural layers and algorithmic layers has been beneficial for handling combinatorial data, enabling the learning procedure to converge faster with fewer data samples. However, these algorithms comprise discrete operations and, therefore, require the definition of a smooth derivative in order to be compatible with backpropagation. By relying on automatic differentiation and gradient smoothing techniques, many differentiable algorithmic layers have been developed, leading to the birth of hybrid architectures, trainable end-to-end on combinatorial data. We refer to this research trend as structured learning. Among all the application domains that benefit from structured learning, we find shortest-path planning on graphs. Many studies aim at labeling graphs in the form of cost functions by supervised, end-to-end learning on shortest-path examples. The advantage of this approach is to enable planning on raw, unlabeled images without exploiting any domain knowledge whatsoever other than planning examples. However, none of these studies aims at learning heuristic functions too. Hence, we propose Neural Weighted A*, the first differentiable anytime planner able to learn cost functions and heuristic functions in a principled way. Learning occurs end-to-end on path examples thanks to a differentiable A* module included in the system. The second contribution of Neural Weighted A* is that our method offers the user the ability to smoothly control the balance between planning accuracy and efficiency using a single, real-valued parameter. In this way, the user can choose, even at runtime, to evaluate either the shortest path or a close approximation, drastically accelerating the planning procedure. In the latter case, since our method sets its roots into the Weighted A* algorithm, the solution suboptimality is constrained within a linear bound proportional to the tradeoff parameter. We experimentally show the validity of our claims by testing Neural Weighted A* against several baselines from the state of the art, outperforming all of them in planning accuracy and efficiency. The experiments are conducted on two datasets comprising planar navigation examples from videogame maps. The first dataset is an adaptation of a standard benchmark used for testing differentiable planning systems, while the second is novel. Both datasets are publicly available.

Un recente filone di ricerca orientata al deep learning punta alla fusione di moduli neurali e moduli algoritmici all’interno della stessa architettura di apprendimento. I promotori di questo connubio promettono una migliore gestione di dati dalla complessità combinatoria da parte delle reti neurali, garantendo allo stesso tempo la convergenza dell’apprendimento con una minore quantità di dati. Tuttavia, questi algoritmi richiedono una derivata continua, ottenuta spesso tramite approssimazione del gradiente, al fine di essere compatibili con la procedura di apprendimento delle reti neurali, chiamata backpropagation. Identifichiamo con “apprendimento strutturato” l’insieme di tecniche che prevedono l’inclusione di algoritmi differenziabili, composti da operazioni discrete, all’interno di architetture neurali. Uno degli ambiti che beneficiano dell’apprendimento strutturato è la ricerca di percorsi minimi su grafi. Infatti, molti studi recenti puntano ad apprendere funzioni di costo su grafi attraverso il deep learning. L’apprendimento strutturato abilita la supervisione diretta su esempi di percorsi su immagini non etichettate, alleggerendo considerevolmente il costo della collezione di dati. Tuttavia, nessuno di questi studi punta ad apprendere anche funzioni euristiche. Pertanto, proponiamo Neural Weighted A*, un pianificatore di percorsi differenziabile capace di apprendere funzioni di costo e funzioni euristiche coerenti fra di loro. L’apprendimento avviene con supervisione end-to-end su coppie immagine-percorso, grazie a un solver differenziabile basato sull’algoritmo A*. Inoltre, Neural Weighted A* è la prima architettura che permette di controllare precisamente, attraverso un singolo parametro, il rapporto fra accuratezza ed efficienza della procedura di planning. In questo modo, l’utente può scegliere in qualsiasi momento se ottenere il percorso ottimo oppure una sua approssimazione, riducendo drasticamente il tempo di computazione. Il controllo sul bilancio fra accuratezza ed efficienza può avvenire anche a runtime e la soluzione, nel caso non corrisponda a quella ottima, risiede comunque, per costruzione, entro un margine proporzionale al parametro di controllo. Verifichiamo sperimentalmente la validità del nostro metodo contro diverse architetture dallo stato dell’arte, superandole sia in accuratezza che in efficienza. Gli esperimenti condotti vertono su due dataset composti da problemi di navigazione bidimensionale all'interno di mappe di videogiochi. Il primo dei due dataset è un benchmark comunemente utilizzato da architetture di planning data-driven, mentre il secondo è interamente nuovo. Entrambi i dataset sono disponibili pubblicamente.