Path Planning using Neural A* Search

To reformulate A* search in a differentiable fashion, we represent the variables in Algorithm 1 as matrices of the map size so that each line can be executed via matrix operations. Specifically, let $O,C,V_{\rm nbr}\in\mathcal{\{}0,1\}^{\mathcal{V}}$ be binary matrices indicating the nodes contained in $\mathcal{O},\mathcal{C},\mathcal{V}_{\rm nbr}$, respectively (we omit an index $i$ here for simplicity.) We represent the start node $v_{\rm s}$, goal node $v_{\rm g}$, and selected node $v^{*}$ as one-hot indicator matrices $V_{\rm s},V_{\rm g},V^{*}\in\{0,1\}^{\mathcal{V}}$, respectively, where $\langle V_{\rm s},\mathds{1}\rangle=\langle V_{\rm g},\mathds{1}\rangle=\langle V^{*},\mathds{1}\rangle=1$ (i.e., one-hot), $\langle A,B\rangle$ is the inner product of two matrices $A$ and $B$, and $\mathds{1}$ is the all-ones matrix of the map size. In addition, let $G,H,\Phi\in\mathbb{R}_{+}^{\mathcal{V}}$ be a matrix version of $g(v)$, $h(v)$, and $\phi(v)$, respectively.

Performing Eq. (1) in a differentiable manner is non-trivial as it involves a discrete operation. Here, we leverage a discretized activation inspired by Hubara et al. (2016) and reformulate the equation as follows:

where $A\odot B$ denotes the element-wise product, and $\tau$ is a temperature parameter that will be defined empirically. $\mathcal{I}_{\text{max}}(A)$ is the function that gives the argmax index of $A$ as a binary one-hot matrix during a forward pass, while acting as the identity function for back-propagation. The open-list matrix $O$ is used here to mask the exponential term so that the selection is done from the nodes in the current open list.

Expanding the neighboring nodes of $v^{*}$ in Eq. (2) involves multiple conditions, i.e., $v^{\prime}\in\mathcal{N}(v^{*})$, $v^{\prime}\notin\mathcal{O}$, and $v^{\prime}\notin\mathcal{C}$. Inspired by Tamar et al. (2016), we implement $\mathcal{N}$ as a convolution between $V^{*}$ and the fixed kernel $K=[[1,1,1]^{\top},[1,0,1]^{\top},[1,1,1]^{\top}]$. When $X$ is given as a binary cost map indicating the passable/impassable nodes, $V_{\rm nbr}$ is obtained by the following matrix operations:

where $A*B$ is the 2D convolution of $A$ and $B$. The multiplication by $X\odot(\mathds{1}-O)\odot(\mathds{1}-C)$ acts as a mask to extract the nodes that are passable and not contained in the open nor close lists. Masking with $X$ preserves the original obstacle structures and thus the graph topology, keeping the differentiable A* complete (i.e., guaranteed to always find a solution if one exists in the graph $\mathcal{G}$, as in standard A*). We also introduce $\bar{V}_{\rm nbr}=(V^{*}*K)\odot X\odot O\odot(\mathds{1}-C)$ indicating the neighboring nodes already in the open list, which we will use to update $G$ below. When $X$ is otherwise a raw image that does not explicitly indicate the passable nodes, we use $V_{\rm nbr}=(V^{*}*K)\odot(\mathds{1}-O)\odot(\mathds{1}-C)$ and $\bar{V}_{\rm nbr}=(V^{*}*K)\odot O\odot(\mathds{1}-C)$.

As explained earlier, $g(v)$ here represents the total guidance cost paid for the actual path from $v_{\rm s}$ to $v$, instead of accumulating the original movement cost $c(v^{\prime})$ that is not always available explicitly. To update this total cost at each iteration, we partially update $G$ with new costs $G^{\prime}$ for the neighbor nodes as follows:

In Eq. (5), the neighbors $V_{\rm nbr}$ that are opened for the first time are assigned $G^{\prime}$, and the neighbors $\bar{V}_{\rm nbr}$ that have already been opened are assigned the lower of the new costs $G^{\prime}$ and previously computed costs $G$. The new costs $G^{\prime}$ for the neighbors are computed in Eq. (6) as the sum of the current cost of the selected node, $g(v^{*})$, expressed using $g(v^{*})=\langle G,V^{*}\rangle$, and the one-step guidance cost to the neighbors represented by $\Phi$.

The differentiable A* module connects its guidance-map input $\Phi$ and search output so that a loss for the output is back-propagated to $\Phi$ and, consequently, to the encoder. Here, the output is the closed list $C$, which is a binary matrix accumulating all the searched nodes $V^{*}$ from Eq. (3) in a search (see Eq. (8) for details). We evaluate the mean $L_{1}$ loss between $C$ and the ground-truth path map $\bar{P}$:

This loss supervises the node selections by penalizing both (1) the false-negative selections of nodes that should have been taken into $C$ to find $\bar{P}$ and (2) the false-positive selections of nodes that were excessive in $C$ to match with $\bar{P}$. In other words, this loss encourages Neural A* to (1) search for a path that is close to the ground-truth path (2) with fewer node explorations.

In practice, we disable the gradients of $\mathcal{O}$ in Eq. (3), $V_{\rm nbr},\bar{V}_{\rm nbr}$ in Eq. (5), and $G$ in Eq. (6) by detaching them from back-propagation chains. Doing so effectively informs the encoder of the importance of the guidance cost $\Phi$ in Eq. (6) for the node selection in Eq. (3), while simplifying recurrent back-propagation chains to stabilize the training process and reduce large memory consumption²²2We found in our experiments that fully enabling the gradients caused training failures due to an out-of-memory problem with 16GB GPU RAM..

The loss shown above is back-propagated through every search step in the differentiable A* module to the encoder. Here, we expect the encoder to learn visual cues in the given problem instances for enabling accurate and efficient search-based planning. These cues include, for instance, the shapes of dead ends and bypasses in binary cost maps or colors and textural patterns of passable roads in raw natural images. For this purpose, we utilize a fully-convolutional network architecture such as U-Net (Ronneberger et al., 2015) used for semantic segmentation, which can learn local visual representations at the original resolution useful for the downstream task³³3As the nature of convolutional neural networks, guidance cost outputs are only sensitive to the input map within their limited receptive fields. Thus, when the map size is intractably large, we could partially sweep the input map with the encoder incrementally during a search without changing search results.. The input to the encoder is given as the concatenation of $X$ and $V_{\rm s}+V_{\rm g}$. In this way, the extraction of those visual cues is properly conditioned by the start and goal positions.

The complete algorithm of Neural A* is summarized in Algorithm 2. To accelerate the training, it is critical to process multiple problem instances at once in a mini batch. However, this is not straightforward because those intra-batch samples may be solved within different numbers of search steps. We address this issue by introducing a binary goal verification flag $\eta^{(i)}=1-\langle V^{(i)}_{\rm g},V^{*(i)}\rangle$ and updating $O^{(i)},C^{(i)}$ as follows:

Intuitively, these operations keep $O^{(i)}$ and $C^{(i)}$ unchanged once the goal is found. We repeat Lines 9–15 until we obtain $\eta^{(i)}=0$ for all the samples in the batch.

As the encoder, we adopted U-Net (Ronneberger et al., 2015) with the VGG-16 backbone (Simonyan & Zisserman, 2015) implemented by Yakubovskiy (2020), where the final layer was activated by the sigmoid function to constrain guidance maps to be $\Phi\in[0,1]^{\mathcal{V}}$. For the differentiable A* module, we used the Chebyshev distance as the heuristic function $H$ suitable for the eight-neighbor grid-world (Patel, 1997). The Euclidean distance multiplied by a small constant ($0.001$) was further added to $H$ for tie-breaking. The temperature $\tau$ in Eq. (3) was empirically set to the square root of the map width.

For assessing the significance of Neural A* in search-based planning, we adopted the following data-driven search-based planners as baseline competitors that have the planning success guarantee, like ours, by design. We extended the authors’ implementations available online.

• •

  SAIL (Choudhury et al., 2018): A data-driven best-first search method that achieved high search efficiency by learning a heuristic function from demonstrations. Unlike Neural A*, SAIL employs hand-engineered features such as the straight-line distances from each node to the goal and the closest obstacles. We evaluated two variants of SAIL where training samples were rolled out using the learned heuristic function (SAIL) or the oracle planner (SAIL-SL).

• •

  Blackbox Differentiation (Vlastelica et al., 2020): A general-purpose approach to data-driven combinatorial solvers including search-based path planning. It consists of an encoder module that transforms environmental maps into node-cost maps and a solver module that performs a combinatorial algorithm as a piece-wise constant black-box function taking the cost maps as input. We implemented a Blackbox-Differentiation version of A* search (BB-A*) by treating our differentiable A* module as a black-box function and training the encoder via black-box optimization, while keeping other setups, such as the encoder architecture and loss function, the same as those of Neural A*.

We also evaluated best-first search (BF) and weighted A* search (WA*) (Pohl, 1970) as baseline classical planners, which used the same heuristic function as that of Neural A*. Finally, we implemented a degraded version of Neural A* named Neural BF, which always used $G=\Phi$ in Eq. (3) instead of $G$ incrementally updated by Eq. (5). By doing so, Neural BF ignored the accumulation of guidance costs from the start node, much like best-first search.

Table 1 summarizes quantitative results. Overall, Neural A* outperformed baseline methods in terms of both Opt and Hmean and improved the path optimality and search efficiency trade-off. SAIL and SAIL-SL sometimes performed more efficiently, which however came with low optimality ratios especially for larger and more complex maps of the Tiled MP and CSM datasets. BB-A* showed higher Hmean scores than those of SAIL/SAIL-SL but was consistently outperformed by Neural A*. Since the only difference between Neural A* and BB-A* is whether making the A* search differentiable or treating it as a black-box in updating an identically-configured encoder, the comparison between them highlights the effectiveness of our approach. With the differentiable A* module, Neural A* has access to richer information of internal steps, which is necessary to effectively analyze causal relationships between individual node selections by Eq. (3) and results. This information is however black-boxed in BB-A*. Also, we found that classical heuristic planners (BF and WA*) performed comparably to or sometimes better than other data-driven baselines. This result could be explained by our challenging experimental setup adopting randomized start and goal locations instead of pre-defined ones by the original work (Choudhury et al., 2018; Vlastelica et al., 2020). Finally, Neural BF achieved the highest Exp scores in the Tiled MP and CSM datasets but often ended up with sub-optimal paths since it ignored the actual cost accumulation. For more evaluations including analysis on the complexity and runtime of Neural A*, see Appendix B.

Figure 3 visualizes example search results with guidance maps produced by the encoder of Neural A*. We confirmed that the encoder successfully captured visual cues in problem instances. Specifically, higher guidance costs (shown in green) were assigned to the whole obstacle regions creating dead ends, while lower costs (shown in white) were given to bypasses and shortcuts that guided the search to the goal. Figure 4 depicts how Neural A* performed a search adaptively for different start and goal locations in the same map. Notice the entrance to the U-shaped dead end is (a) blocked with high guidance costs when the dead end is placed between the start and goal and (b) open when the goal is inside the dead end.

We further assessed the effects of the encoder by comparing several different configurations for its architecture. In the configuration w/o start and goal, we fed only an environmental map $X_{i}$ to the encoder as input. In w/ ResNet-18 backbone, a residual network architecture (He et al., 2016) was used instead of VGG-16. Table 2 shows the degraded performances with these configurations especially in terms of the optimality ratio. Additionally, we tried the following variants of the proposed approach, which we found not effective. Adopting the straight-through Gumbel-softmax (Jang et al., 2017) for Eq. (3) caused complete planning failures (with Opt, Exp, Hmean all $0$) as it biases the planner to avoid the most promising nodes. Using the mean squared loss for Eq. (7) produces the same gradients as the mean $L_{1}$ loss up to a constant factor for binary variables (i.e., $C$ and $\bar{P}$), and indeed led to a comparable performance.

Although Neural A* worked well in various environments, its current implementation assumes the grid world environments with unit node costs. One interesting direction is to extend Neural A* to work on a high-dimensional or continuous state space. This will require the encoder to be tailored to such a space, as done in Qureshi et al. (2019); Chen et al. (2020); Ichter & Pavone (2019). We leave this extension for future work.