# Speed Optimization for Incremental Updating of Grid-Based Distance Maps
## 4 The Methodology
### Algorithm Intuition
#### 4.1.3 DM-Based Subgoal Graph  
In order to introduce the concept of maximal clearance provided by DMs into the precomputing algorithms of subgoal graphs, we extend the formal definitions of the traditional subgoal graph as follows:  
**Definition 1**.: _For two cells \(s\) and \(s^{\prime}\), let \(dx\) and \(dy\) be the respective distances between \(s\) and \(s^{\prime}\) along the \(x\) and \(y\) axes. The shortest trajectory between \(s\) and \(s^{\prime}\) is a permutation of exactly min(\(dx\),\(dy\)) diagonal and \(|dx\)-\(dx|\) cardinal moves, for a total of max(\(dx\),\(dy\)) moves._  
**Definition 2**.: _Given a safety radius \(R\), a collision-free path between two cells \(s\) and \(s^{\prime}\) is the shortest trajectory in which each cell \(s^{\prime}\) is collision-free, i.e., \(C(R,s^{\prime})\)=0._  
**Definition 3**.: _Given a safety radius \(R\), an unblocked cell \(s\) is a collision-free subgoal if there are two perpendicular cardinal directions \(c_{1}\) and \(c_{2}\) such that \(C(R,s+c_{1}+c_{2})\)=1, \(C(R,s+c_{1})\)=0 and \(C(R,s+c_{2})\)=0._  
**Definition 4**.: _Given a safety radius \(R\), two cells \(s\) and \(s^{\prime}\) are h-reachable if there is a collision-free path of octile length \(h\)(\(s\),\(s^{\prime}\)) between them. Two \(h\)-reachable cells are safe-\(h\)-reachable if all shortest trajectories between them are also paths. Two safe-\(h\)-reachable cell \(s\) and \(s^{\prime}\) are direct-\(h\)-reachable if none of the shortest paths between them contains a subgoal \(s^{\prime\prime}\) \(\
otin\) {\(s\),\(s^{\prime}\)}._  
**Definition 5**.: _Given a safety radius \(R\), an DM-based subgoal graph, \(G\)s =(\(R,Vs,Es\)), on its corresponded grids, is a high-level, undirected graph, where \(Vs\) is the set of collision-free subgoals and \(Es\) is the set of edges connecting direct-\(h\)-reachable subgoals, and the length of the edges is the octile distances between the subgoals they connect._  
The process of constructing an DM-based subgoal graph can be intuitively divided into two steps: (1) placing collision-free subgoals at the corners of the expanded obstacle boundary to circumnavigate  
Figure 6: Canonical Ordering in wavefront propagation. (**a**) The possible paths to propagate a wavefront from cell S on left-top to cell G on bottom-right. Among these paths, only the gray one is tested when following the preference rule of Canonical Ordering; (**b**) By following the preference rule of Canonical Ordering, the expansion of a wavefront denoted as red arrows is launched from the center yellow cell and visits each affected cell only once.  
the collision regions (e.g., the orange circles shown in Figure 7a); (2) adding edges between those subgoals which are mutually direct-h-reachable (e.g., the green edges shown in Figure 7b). Given a start and a goal cell (e.g., the blue and red discs shown in Figure 7b), we first connect them to their respective direct-h-reachable subgoals and then plan a high-level shortest path by executing A* on the updated subgoal graph (e.g., the white trajectory shown in Figure 7b). We can refine each segment of the high-level path by arbitrarily selecting an h-reachable path between two connecting subgoals, and then orderly appending these refined paths together. Moreover, as shown in Figure 7c,d, for agents with different safety radius, their corresponding DM-based subgoal graph, according to Definition 5, can set aside adequate clearance; therefore, the paths found from the resulting graphs can be collision-free.