\section{INTRODUCTION}

Path and motion planning for autonomous systems has long been an area of research within the robotics and artificial intelligence communities.
This has led to the development of a number of frameworks which formulate planning tasks in terms of mathematical optimization problems, which can then be solved by utilizing approaches from optimization and optimal control \cite{Bertsekas2012,Sutton2016}. 
However, planning in complex domains can be a challenging problem, and requires the agents to spend time and computational resources in order to find solutions, giving rise to an intrinsic need for agents to balance computational complexity with optimality of the resulting plan \cite{Dean1988,Kambhampati1986,Tsiotras2012,Behnke2004,Lu2012}.




Consequently, a number of approaches within the path-planning community have been developed that aim to explicitly capture the interplay between complexity and optimality.
For example, in \cite{Tsiotras2007,Tsiotras2012,Cowlagi2008,Cowlagi2010,Cowlagi2011,Cowlagi2012,Cowlagi2012a}, the authors utilize wavelets to obtain multi-resolution representations of two-dimensional environments for path-planning.
The use of abstractions, or aggregations, of the planning space to form multi-resolution environment depictions allows these works to leverage the computational benefits of executing graph-search algorithms, such as A\(^*\), on reduced graphs of the environment that contain fewer vertices as compared to the original, full-resolution, representation.




In a similar spirit, other works, such as \cite{Kambhampati1986,Hauer2015,Hauer2016}, consider abstractions for planning, but instead utilize hierarchical representations of the world in the form of multi-resolution quadtrees and octrees.
Interestingly, the use of tree structures enables these works to incorporate environment uncertainty \cite{Kraetzschmar2004}.
With this added flexibility, these approaches can be used in an on-line manner, allowing autonomous agents to plan based on occupancy grid (OG) representations of the world that are dynamically updated as the agent interacts with the environment. 
To strike a balance between the complexity of the search and satisfactory performance, the aforementioned works recursively re-solve the planning problem as the agent traverses the world.




It should be noted that the interplay between complexity and optimality is not unique to the path-planning community.
Recent work related to bounded-rational decision making has illustrated a growing need to develop decision-making frameworks for agents that are resource limited \cite{Tishby2010,Ortega2011,Genewein2015,Larsson2017,Rubin2012}.
This area of research considers limitations in the traditional assumptions of artificial intelligence, and approaches problems by viewing agents as resource-limited entities that are constrained in terms of their information-processing capabilities. 
To model such agents, the authors in \cite{Genewein2015} utilize concepts from information theory, arguing that bounded-rational decision making can be modeled by considering Kullback-Leibler (KL) divergence constraints added to traditional maximum expected utility problems. 
Extensions of this work to sequential decision-making problems in stochastic domains is considered in \cite{Tishby2010,Rubin2012}, whereby Markov Decision Processes (MDPs) are utilized with information-theoretic constraints to formulate information-limited MDPs (IL-MDPs). 
These frameworks include a trade-off parameter that balances the optimality of the decision policy and the effort required to obtain it, as measured by a KL-divergence measure between the resulting posterior policy and a default prior policy.
These approaches offer one perspective of bounded-rational decision making and provide for interesting connections with information-theoretic frameworks for compression, such as rate-distortion theory \cite{Tishby2010,Genewein2015}.





In this paper, we consider complexity reduction in path-planning problems by means of graph abstractions for resource-limited agents.
Our approach combines aspects from both the planning and bounded-rational decision-making communities.
The contribution of this paper is two-fold.
Firstly, we employ an information-theoretic approach for the generation of multi-resolution abstractions that are a function of a single trade-off parameter and are not provided a priori for the purposes of path-planning and secondly, our framework couples the environment resolution to the resulting path quality.
To the best of our knowledge, there are no existing approaches that utilize information-theoretic abstractions for complexity reduction in path-planning that also guarantee the monotonic improvement of the path-cost as a function of environment resolution. 
The ability to couple path-cost with environment resolution allows us to facilitate connections between the path quality, the complexity of executing graph-search algorithms to obtain resolution-optimal paths and the information-processing capabilities of the agent as determined by the information-theoretically generated abstractions.
In summary, our framework (i) captures the cost of abstraction by defining an abstract cost-function, (ii) utilizes concepts from information theory to obtain reduced environment representations as a function of agent information-processing capabilities, and (iii) provides provable guarantees on the monotonic improvement of the path cost as a function of environment resolution.
The paper is organized as follows.
We begin in Section \ref{sec:prelims} by introducing necessary background material prior to formalizing our problem in Section \ref{sec:problemFormul}.
Then, in Section \ref{sec:ITIB_Abstractions}, we describe the information-theoretic framework for multi-resolution environment abstractions before discussing planning on abstractions in Section \ref{sec:planningOnAbstractions}.
We then present a numerical example in Section \ref{sec:numericalExample} with accompanying discussion in Section \ref{sec:discussion} and provide our concluding remarks in Section \ref{sec:conclusion}.
Proofs for the papers theoretical results can be found in the appendices.



\section{PRELIMINARIES} \label{sec:prelims}

Denote the set of real and non-negative real numbers by \(\Re\), \(\Re_{+}\), respectively, and, for any positive integer \(d\), let \(\Re^d\) denote the \(d\)-dimensional Euclidean space.
Assume that the environment \(\mathcal W \subset \Re^d\) is given by a \(d\)-dimensional occupancy grid and that there exists an integer \(\ell > 0\) such that the environment is contained within a hypercube of side length \(2^\ell\). 
The environment is represented as a tree \(\mathcal T = \left( \mathcal N(\mathcal T), \mathcal E(\mathcal T) \right)\), where the edge set \(\mathcal E (\mathcal T)\) describes the relationship between the nodes in \(\mathcal N(\mathcal T)\).
In this paper, we restrict our attention to the case where the tree representation is that of a quadtree, however the contributions of this paper are valid for any tree structure.
We let \(\mathcal T^{\mathcal Q}\) be the space of all feasible  quadtree representations of \(\mathcal W\), where each \(\mathcal T \in \mathcal T^{\mathcal Q}\) encodes a multi-resolution, hierarchical, representation of the world.
Take \(\mathcal T_{\mathcal W} \in \mathcal T^{\mathcal Q}\) be the quadtree corresponding to the original environment \(\mathcal W\); that is, \(\mathcal T_{\mathcal W}\) encodes the finest resolution depiction of \(\mathcal W\).




Consider any node \(n \in \mathcal N(\mathcal T_{\mathcal W})\) at depth \(k \in \left\{0,\ldots,\ell \right\}\), then \(n' \in \mathcal N(\mathcal T_{\mathcal W})\) is a child of \(n\) if the following hold:
\begin{enumerate}
		\item 
		Node \(n'\) is at depth \(k+1\) in \(\mathcal T_{\mathcal W}\),
		
		\item
		Nodes \(n\) and \(n'\) are incident to a common edge, i.e., \(\left(n,n'\right) \in \mathcal E \left( \mathcal T_{\mathcal W} \right)\).
\end{enumerate}
In the sequel, we let the set of child nodes for any \(n \in \mathcal N(\mathcal T_{\mathcal W})\) be denoted by \(\mathcal C(n)\) and \(\mathcal N_k(\mathcal T_{\mathcal W})\) to be the set of nodes at depth \(k\).
For any \(\mathcal T \in \mathcal T^{\mathcal Q}\) we take \(\mathcal N_{\text{leaf}}\left( \mathcal T \right) = \left\{n' \in \mathcal N(\mathcal T) :  \mathcal C(n') \cap \mathcal N(\mathcal T) = \emptyset \right\}\) to denote the set of leaf nodes and \(\mathcal N_{\text{int}}(\mathcal T) = \mathcal N(\mathcal T) \setminus \mathcal N_{\text{leaf}}(\mathcal T)\) to be the set of interior nodes of the tree \(\mathcal T\).



While useful for describing the relationship between nodes in a given tree, the aforementioned sets do not describe how the nodes in the tree \( \mathcal T \in \mathcal T^{\mathcal Q}\) are related to the spatial region described by the environment \(\mathcal W\).
In order to make these connections precise, we have the following definition.
\begin{definition}[\hspace{-0.5pt}\cite{Hauer2015}] \label{def:nodeHyperCube}
	Let \(k \in \{0,\ldots,\ell\}\) and \(n \in \mathcal N_{k}(\mathcal T_{\mathcal W})\).  
	Then the node \(n\):
	\begin{enumerate}
		\item
		Is at depth \(k\) and has an \(r\)-value given by the function \(r:\mathcal N(\mathcal T_\mathcal W) \to \{0,\ldots,\ell\}\) defined by the rule \(r (n) = \ell - k\). 
		The inverse image of the function \(r\) is the set \(r^{-1}(L) = \{n \in \mathcal N(\mathcal T_\mathcal W) : r(n) \in L\}\) for any \(L \subseteq \{0,\ldots,\ell\}\). 
		
		
		\item 
		Represents a hypercube \(H(n) \subseteq \mathcal W\) with side length \(2^{r(n)}\) and volume \(2^{d r(n)}\) centered at the point \(\mathbf p(n) \in \Re^d\).
			
		\item 
		The hypercubes corresponding to the nodes that are the children of \(n\) form a partition of \(H(n)\).  
		That is,
		\begin{equation*}
			H(n) = \bigcup_{n' \in \mathcal C(n)} H(n').
		\end{equation*}
	\end{enumerate}
\end{definition}

\begin{figure}[t]
		\centering
		\begin{adjustbox}{max size={\textwidth}}
			\begin{tikzpicture}[level distance=2.25cm,
			level 1/.style={sibling distance=22cm},
			level 2/.style={sibling distance=5.5cm},
			level 3/.style={sibling distance=1.3cm},
			level 4/.style={sibling distance=0.3cm}]
			
		
			
			\node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
		
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {} }
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {} }
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {} }
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {} }
					}
					child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}	
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}	
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}	
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}	
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}	
				}
			} 
	
	
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child[color=black!30!] {node[color=black!30!,shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}	
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}	
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
			}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
			}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
				child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
					child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
						child[color=black!30!] {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
					}
				}
			};
			\end{tikzpicture}
		\end{adjustbox}
		\\
		\vspace{0.8cm}
	
		\centering
		\begin{adjustbox}{max size={\textwidth}}
			\begin{tikzpicture}[scale=.9,every node/.style={minimum size=1cm}]
				
				
				
				
					
					\draw[step=0.5cm, black] (0.99,0) grid (2,1); 
					\draw[step=0.5cm, black] (1.99,2.99) grid (2.5,3.5); 
					\draw[step=0.5cm, black] (0,1.99) grid (0.5,3); 
					\draw[step=0.5cm, black] (2.99,1.99) grid (4,2.5); 
					\draw[step=0.5cm, black] (2.49,0.99) grid (3,1.5); 
					\draw[step=0.5cm, black] (2.99,0.499) grid (3.5,1);
					\draw[step=0.5cm, black] (0.49,1.49) grid (1,2.5);	
					\draw[step=0.5cm, black] (3.5,0) grid (4,0.5);	
								
				
				
					\draw[step=1cm, black] (0,3) grid (1,4);
					\draw[step=1cm, black] (1,3) grid (2,4);
					\draw[step=1cm, black] (1,2) grid (2,3);
					\draw[step=1cm, black] (3,3) grid (4,4);
					\draw[step=1cm, black] (3,1) grid (4,2);
						
				
				
					\draw[step=0.25cm, black] (0,0) grid (0.5,1.99);
					\draw[step=0.25cm, black] (0.5,0) grid (1,1.49);
					\draw[step=0.25cm, black] (1,0.99) grid (2.5,2);
					\draw[step=0.25cm, black] (2,1.99) grid (3,3);
					\draw[step=0.25cm, black] (2,3.49) grid (3,4);
					\draw[step=0.25cm, black] (2,0) grid (3,1);
					\draw[step=0.25cm, black] (3,2.5) grid (4,3);
					\draw[step=0.25cm, black] (3,0) grid (3.5,0.5);
					\draw[step=0.25cm, black] (3.5,0.49) grid (4,1);
			\end{tikzpicture}
		
			\hspace{2cm}
		
			\begin{tikzpicture}[scale=.9,every node/.style={minimum size=1cm}]
				
			
				
				
				
				
				
					
					\draw[step=0.5cm, black!10!] (0.99,0) grid (2,1); 
					\draw[step=0.5cm, black!10!] (1.99,2.99) grid (2.5,3.5); 
					\draw[step=0.5cm, black!10!] (0,1.99) grid (0.5,3); 
					\draw[step=0.5cm, black!10!] (2.99,1.99) grid (4,2.5); 
					\draw[step=0.5cm, black!10!] (2.49,0.99) grid (3,1.5); 
					\draw[step=0.5cm, black!10!] (2.99,0.499) grid (3.5,1);
					\draw[step=0.5cm, black!10!] (0.49,1.49) grid (1,2.5);	
					\draw[step=0.5cm, black!10!] (3.5,0) grid (4,0.5);	
					
				
				
					\draw[step=1cm, black!10!] (0,3) grid (1,4);
					\draw[step=1cm, black!10!] (1,3) grid (2,4);
					\draw[step=1cm, black!10!] (1,2) grid (2,3);
					\draw[step=1cm, black!10!] (3,3) grid (4,4);
					\draw[step=1cm, black!10!] (3,1) grid (4,2);
					
				
				
					\draw[step=0.25cm, black!10!] (0,0) grid (0.5,1.99);
					\draw[step=0.25cm, black!10!] (0.5,0) grid (1,1.49);
					\draw[step=0.25cm, black!10!] (1,0.99) grid (2.5,2);
					\draw[step=0.25cm, black!10!] (2,1.99) grid (3,3);
					\draw[step=0.25cm, black!10!] (2,3.49) grid (3,4);
					\draw[step=0.25cm, black!10!] (2,0) grid (3,1);
					\draw[step=0.25cm, black!10!] (3,2.5) grid (4,3);
					\draw[step=0.25cm, black!10!] (3,0) grid (3.5,0.5);
					\draw[step=0.25cm, black!10!] (3.5,0.49) grid (4,1);
				
				
				
				
				
				
				
				
				
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (11) at (0.125, 0.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (21) at (0.125, 0.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (31) at (0.125, 0.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (41) at (0.125, 0.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (51) at (0.125, 1.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (61) at (0.125, 1.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (71) at (0.125, 1.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (81) at (0.125, 1.875) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (12) at (0.375, 0.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (22) at (0.375, 0.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (32) at (0.375, 0.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (42) at (0.375, 0.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (52) at (0.375, 1.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (62) at (0.375, 1.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (72) at (0.375, 1.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (82) at (0.375, 1.875) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (13) at (0.625, 0.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (23) at (0.625, 0.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (33) at (0.625, 0.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (43) at (0.625, 0.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (53) at (0.625, 1.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (63) at (0.625, 1.375) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (14) at (0.875, 0.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (24) at (0.875, 0.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (34) at (0.875, 0.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (44) at (0.875, 0.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (54) at (0.875, 1.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (64) at (0.875, 1.375) {};
					
				
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (l11) at (0.25, 2.25) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (l21) at (0.25, 2.75) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (l12) at (0.75, 1.75) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (l22) at (0.75, 2.25) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (l32) at (0.75, 2.75) {};		
					
				
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (L11) at (0.5, 3.5) {};
					
				
				
				
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (15) at (1.125, 1.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (25) at (1.125, 1.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (35) at (1.125, 1.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (45) at (1.125, 1.875) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (16) at (1.375, 1.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (26) at (1.375, 1.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (36) at (1.375, 1.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (46) at (1.375, 1.875) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (17) at (1.625, 1.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (27) at (1.625, 1.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (37) at (1.625, 1.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (47) at (1.625, 1.875) {};
		
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (18) at (1.875, 1.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (28) at (1.875, 1.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (38) at (1.875, 1.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (48) at (1.875, 1.875) {};			
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (19) at (2.125, 0.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (29) at (2.125, 0.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (39) at (2.125, 0.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (49) at (2.125, 0.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (59) at (2.125, 1.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (69) at (2.125, 1.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (79) at (2.125, 1.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (89) at (2.125, 1.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (99) at (2.125, 2.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (109) at (2.125, 2.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (119) at (2.125, 2.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (129) at (2.125, 2.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (139) at (2.125, 3.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (149) at (2.125, 3.875) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (110) at (2.375, 0.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (210) at (2.375, 0.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (310) at (2.375, 0.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (410) at (2.375, 0.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (510) at (2.375, 1.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (610) at (2.375, 1.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (710) at (2.375, 1.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (810) at (2.375, 1.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (910) at (2.375, 2.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (1010) at (2.375, 2.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (1110) at (2.375, 2.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (1210) at (2.375, 2.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (1310) at (2.375, 3.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (1410) at (2.375, 3.875) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (111) at (2.625, 0.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (211) at (2.625, 0.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (311) at (2.625, 0.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (411) at (2.625, 0.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (511) at (2.625, 2.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (611) at (2.625, 2.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (711) at (2.625, 2.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (811) at (2.625, 2.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (911) at (2.625, 3.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (1011) at (2.625, 3.875) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (112) at (2.875, 0.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (212) at (2.875, 0.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (312) at (2.875, 0.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (412) at (2.875, 0.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (512) at (2.875, 2.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (612) at (2.875, 2.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (712) at (2.875, 2.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (812) at (2.875, 2.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (912) at (2.875, 3.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (1012) at (2.875, 3.875) {};
					
				
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (c11) at (1.25, 0.25) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (c21) at (1.25, 0.75) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (c12) at (1.75, 0.25) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (c22) at (1.75, 0.75) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (c13) at (2.25, 3.25) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (c14) at (2.75, 1.25) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (c24) at (2.75, 1.75) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (c34) at (2.75, 3.25) {};
						
				
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (C11) at (1.5, 3.5) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (C12) at (1.5, 2.5) {};
					
				
				
				
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (113) at (3.125, 0.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (213) at (3.125, 0.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (313) at (3.125, 2.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (413) at (3.125, 2.875) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (114) at (3.375, 0.125) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (214) at (3.375, 0.375) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (314) at (3.375, 2.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (414) at (3.375, 2.875) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (115) at (3.625, 0.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (215) at (3.625, 0.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (315) at (3.625, 2.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (415) at (3.625, 2.875) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (116) at (3.875, 0.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (216) at (3.875, 0.875) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (316) at (3.875, 2.625) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (416) at (3.875, 2.875) {};
					
				
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (r11) at (3.25, 0.75) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (r21) at (3.25, 2.25) {};
					
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (r12) at (3.75, 0.25) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (r22) at (3.75, 2.25) {};
					
				
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (R11) at (3.5, 3.5) {};
					\node[circle,draw=black,fill=white,very thin,inner sep=0pt, minimum size=0.0625cm] (R21) at (3.5, 1.5) {};
					
				
				
				
					
				
				
				
					
				
					\draw[-] (11.north) -- (21.south);
					\draw[-] (11.east) -- (12.west);	
				
					\draw[-] (21.north) -- (31.south);
					\draw[-] (21.east) -- (22.west);	
				
					\draw[-] (31.north) -- (41.south);
					\draw[-] (31.east) -- (32.west);		
				
					\draw[-] (41.north) -- (51.south);
					\draw[-] (41.east) -- (42.west);		
				
					\draw[-] (51.north) -- (61.south);
					\draw[-] (51.east) -- (52.west);		
				
					\draw[-] (61.north) -- (71.south);
					\draw[-] (61.east) -- (62.west);		
				
					\draw[-] (71.north) -- (81.south);
					\draw[-] (71.east) -- (72.west);	
				
					\draw[-] (81.north) -- (l11.south);
					\draw[-] (81.east) -- (82.west);	
				
					\draw[-] (l11.north) -- (l21.south);
					\draw[-] (l11.east) -- (l22.west);
				
					\draw[-] (l21.north) -- (L11.south);
					\draw[-] (l21.east) -- (l32.west);	
				
					\draw[-] (L11.south) -- (l32.north);
					\draw[-] (L11.east) -- (C11.west);	
						
				
					\draw[-] (12.north) -- (22.south);
					\draw[-] (12.east) -- (13.west);		
				
					\draw[-] (22.north) -- (32.south);
					\draw[-] (22.east) -- (23.west);		
				
					\draw[-] (32.north) -- (42.south);
					\draw[-] (32.east) -- (33.west);
				
					\draw[-] (42.north) -- (52.south);
					\draw[-] (42.east) -- (43.west);	
				
					\draw[-] (52.north) -- (62.south);
					\draw[-] (52.east) -- (53.west);			
				
					\draw[-] (62.north) -- (72.south);
					\draw[-] (62.east) -- (63.west);		
				
					\draw[-] (72.north) -- (82.south);
					\draw[-] (72.east) -- (l12.west);	
				
					\draw[-] (82.north) -- (l11.south);
					\draw[-] (82.east) -- (l12.west);	
					
				
					\draw[-] (13.north) -- (23.south);
					\draw[-] (13.east) -- (14.west);	
				
					\draw[-] (23.north) -- (33.south);
					\draw[-] (23.east) -- (24.west);	
				
					\draw[-] (33.north) -- (43.south);
					\draw[-] (33.east) -- (34.west);	
				
					\draw[-] (43.north) -- (53.south);
					\draw[-] (43.east) -- (44.west);	
				
					\draw[-] (53.north) -- (63.south);
					\draw[-] (53.east) -- (54.west);	
				
					\draw[-] (63.north) -- (l12.south);
					\draw[-] (63.east) -- (64.west);	
				
					\draw[-] (l12.north) -- (l22.south);
					\draw[-] (l12.south) -- (64.north);
					\draw[-] (l12.east) -- (35.west);
					\draw[-] (l12.east) -- (45.west);
				
					\draw[-] (l22.north) -- (l32.south);
					\draw[-] (l22.east) -- (C12.west);
				
					\draw[-] (l32.east) -- (C12.west);
					
				
					\draw[-] (14.north) -- (24.south);
					\draw[-] (14.east) -- (c11.west);
				
					\draw[-] (24.north) -- (34.south);
					\draw[-] (24.east) -- (c11.west);
				
					\draw[-] (34.north) -- (44.south);
					\draw[-] (34.east) -- (c21.west);
				
					\draw[-] (44.north) -- (54.south);
					\draw[-] (44.east) -- (c21.west);
				
					\draw[-] (54.north) -- (64.south);
					\draw[-] (54.east) -- (15.west);
				
					\draw[-] (64.east) -- (25.west);
					
				
				
				
					\draw[-] (c11.north) -- (c21.south);
					\draw[-] (c11.east) -- (c12.west);
				
					\draw[-] (c21.north) -- (15.south);
					\draw[-] (c21.north) -- (16.south);
					\draw[-] (c21.east) -- (c22.west);
				
					\draw[-] (15.north) -- (25.south);
					\draw[-] (15.east) -- (16.west);
				
					\draw[-] (25.north) -- (35.south);
					\draw[-] (25.east) -- (26.west);
				
					\draw[-] (35.north) -- (45.south);
					\draw[-] (35.east) -- (36.west);
				
					\draw[-] (45.north) -- (C12.south);
					\draw[-] (45.east) -- (46.west);
				
					\draw[-] (C12.north) -- (C11.south);
					\draw[-] (C12.south) -- (46.north);
					\draw[-] (C12.south) -- (47.north);
					\draw[-] (C12.south) -- (48.north);
					\draw[-] (C12.east) -- (99.west);
					\draw[-] (C12.east) -- (109.west);
					\draw[-] (C12.east) -- (119.west);
					\draw[-] (C12.east) -- (129.west);
					
				
					\draw[-] (c12.north) -- (c22.south);
					\draw[-] (c12.east) -- (19.west);
					\draw[-] (c12.east) -- (29.west);
				
					\draw[-] (c22.east) -- (39.west);
					\draw[-] (c22.east) -- (49.west);
					\draw[-] (c22.north) -- (17.south);
					\draw[-] (c22.north) -- (18.south);
				
					\draw[-] (16.north) -- (26.south);
					\draw[-] (16.east) -- (17.west);
				
					\draw[-] (26.north) -- (36.south);
					\draw[-] (26.east) -- (27.west);
				
					\draw[-] (36.north) -- (46.south);
					\draw[-] (36.east) -- (37.west);
				
					\draw[-] (46.east) -- (47.west);
					
				
					\draw[-] (17.north) -- (27.south);
					\draw[-] (17.east) -- (18.west);
				
					\draw[-] (27.north) -- (37.south);
					\draw[-] (27.east) -- (28.west);
				
					\draw[-] (37.north) -- (47.south);
					\draw[-] (37.east) -- (38.west);
				
					\draw[-] (47.east) -- (48.west);
					
				
					\draw[-] (18.north) -- (28.south);
					\draw[-] (18.east) -- (59.west);
				
					\draw[-] (28.north) -- (38.south);
					\draw[-] (28.east) -- (69.west);
				
					\draw[-] (38.north) -- (48.south);
					\draw[-] (38.east) -- (79.west);
				
					\draw[-] (48.east) -- (89.west);
				
					\draw[-] (C11.east) -- (c13.west); 
					\draw[-] (C11.east) -- (139.west); 
					\draw[-] (C11.east) -- (149.west); 
					
				
					\draw[-] (19.north) -- (29.south);
					\draw[-] (19.east) -- (110.west);
				
					\draw[-] (29.north) -- (39.south);
					\draw[-] (29.east) -- (210.west);
				
					\draw[-] (39.north) -- (49.south);
					\draw[-] (39.east) -- (310.west);
				
					\draw[-] (49.north) -- (59.south);
					\draw[-] (49.east) -- (410.west);
				
					\draw[-] (59.north) -- (69.south);
					\draw[-] (59.east) -- (510.west);
				
					\draw[-] (69.north) -- (79.south);
					\draw[-] (69.east) -- (610.west);
				
					\draw[-] (79.north) -- (89.south);
					\draw[-] (79.east) -- (710.west);
				
					\draw[-] (89.north) -- (99.south);
					\draw[-] (89.east) -- (810.west);
				
					\draw[-] (99.north) -- (109.south);
					\draw[-] (99.east) -- (910.west);
				
					\draw[-] (109.north) -- (119.south);
					\draw[-] (109.east) -- (1010.west);
				
					\draw[-] (119.north) -- (129.south);
					\draw[-] (119.east) -- (1110.west);
				
					\draw[-] (129.north) -- (c13.south);
					\draw[-] (129.east) -- (1210.west);
				
					\draw[-] (c13.south) -- (1210.north);
					\draw[-] (c13.north) -- (1310.south);
					\draw[-] (c13.north) -- (139.south);
					\draw[-] (c13.east) -- (c34.west);
				
					\draw[-] (139.east) -- (1310.west);
					\draw[-] (139.north) -- (149.south);
				
					\draw[-] (149.east) -- (1410.west);
					
				
					\draw[-] (110.north) -- (210.south);
					\draw[-] (110.east) -- (111.west);
				
					\draw[-] (210.north) -- (310.south);
					\draw[-] (210.east) -- (211.west);
				
					\draw[-] (310.north) -- (410.south);
					\draw[-] (310.east) -- (311.west);
				
					\draw[-] (410.north) -- (510.south);
					\draw[-] (410.east) -- (411.west);
				
					\draw[-] (510.east) -- (c14.west);
					\draw[-] (510.north) -- (610.south);
				
					\draw[-] (610.east) -- (c14.west);
					\draw[-] (610.north) -- (710.south);
				
					\draw[-] (710.east) -- (c24.west);
					\draw[-] (710.north) -- (810.south);
				
					\draw[-] (810.east) -- (c24.west);
					\draw[-] (810.north) -- (910.south);
				
					\draw[-] (910.east) -- (511.west);
					\draw[-] (910.north) -- (1010.south);
				
					\draw[-] (1010.east) -- (611.west);
					\draw[-] (1010.north) -- (1110.south);
				
					\draw[-] (1110.east) -- (711.west);
					\draw[-] (1110.north) -- (1210.south);
				
					\draw[-] (1210.east) -- (811.west);
				
					\draw[-] (1310.east) -- (911.west);
					\draw[-] (1310.north) -- (1410.south);
				
					\draw[-] (1410.east) -- (1011.west);
					
				
					\draw[-] (111.north) -- (211.south);
					\draw[-] (111.east) -- (112.west);
				
					\draw[-] (211.north) -- (311.south);
					\draw[-] (211.east) -- (212.west);
				
					\draw[-] (311.north) -- (411.south);
					\draw[-] (311.east) -- (312.west);
				  	
					\draw[-] (411.east) -- (412.west);
					\draw[-] (411.north) -- (c14.south);
				
					\draw[-] (c14.north) -- (c24.south);
					\draw[-] (c14.south) -- (412.north);
					\draw[-] (c14.east) -- (R21.west);
				
					\draw[-] (c24.north) -- (511.south);
					\draw[-] (c24.north) -- (512.south);
					\draw[-] (c24.east) -- (R21.west);
					
					\draw[-] (511.east) -- (512.west);
					\draw[-] (511.north) -- (611.south);
				
					\draw[-] (611.east) -- (612.west);
					\draw[-] (611.north) -- (711.south);
				
					\draw[-] (711.east) -- (712.west);
					\draw[-] (711.north) -- (811.south);
				
					\draw[-] (811.east) -- (812.west);
					\draw[-] (811.north) -- (c34.south);
				
					\draw[-] (c34.south) -- (812.north);
					\draw[-] (c34.north) -- (911.south);
					\draw[-] (c34.north) -- (912.south);
					\draw[-] (c34.east) -- (R11.west);
				
					\draw[-] (911.east) -- (912.west);
					\draw[-] (911.north) -- (1011.south);
				
					\draw[-] (1011.east) -- (1012.west);
					
				
					\draw[-] (112.north) -- (212.south);
					\draw[-] (112.east) -- (113.west);
				
					\draw[-] (212.north) -- (312.south);
					\draw[-] (212.east) -- (213.west);
				
					\draw[-] (312.north) -- (412.south);
					\draw[-] (312.east) -- (r11.west);
				
					\draw[-] (412.east) -- (r11.west);
				
					\draw[-] (512.east) -- (r21.west);
					\draw[-] (512.north) -- (612.south);
				
					\draw[-] (612.east) -- (r21.west);
					\draw[-] (612.north) -- (712.south);
				
					\draw[-] (712.east) -- (313.west);
					\draw[-] (712.north) -- (812.south);
				
					\draw[-] (812.east) -- (413.west);
				
					\draw[-] (912.east) -- (R11.west);
					\draw[-] (912.north) -- (1012.south);
				
					\draw[-] (1012.east) -- (R11.west);
					
				
					\draw[-] (113.north) -- (213.south);
					\draw[-] (113.east) -- (114.west);
				
					\draw[-] (213.east) -- (214.west);
					\draw[-] (213.north) -- (r11.south);
				
					\draw[-] (r11.south) -- (214.north);
					\draw[-] (r11.north) -- (R21.south);
					\draw[-] (r11.east) -- (115.west);
					\draw[-] (r11.east) -- (215.west);
				
					\draw[-] (R21.north) -- (r21.south);
					\draw[-] (R21.north) -- (r22.south);
					\draw[-] (R21.south) -- (215.north);
					\draw[-] (R21.south) -- (216.north);	
				
					\draw[-] (r21.east) -- (r22.west);
					\draw[-] (r21.north) -- (313.south);
					\draw[-] (r21.north) -- (314.south);
				
					\draw[-] (313.north) -- (413.south);
					\draw[-] (313.east) -- (314.west);			
				
					\draw[-] (413.east) -- (414.west);		
					\draw[-] (413.north) -- (R11.south);		
				
					\draw[-] (R11.south) -- (414.north);
					\draw[-] (R11.south) -- (415.north);
					\draw[-] (R11.south) -- (416.north);
					
				
					\draw[-] (114.north) -- (214.south);
					\draw[-] (114.east) -- (r12.west);
				
					\draw[-] (214.east) -- (r12.west);
				
					\draw[-] (314.north) -- (414.south);
					\draw[-] (314.east) -- (315.west);
				
					\draw[-] (414.east) -- (415.west);
					
				
					\draw[-] (r12.north) -- (115.south);
					\draw[-] (r12.north) -- (116.south);
				
					\draw[-] (115.east) -- (116.west);
					\draw[-] (115.north) -- (215.south);
				
					\draw[-] (215.east) -- (216.west);
				
					\draw[-] (r22.north) -- (315.south);
					\draw[-] (r22.north) -- (316.south);		
				
					\draw[-] (315.east) -- (316.west);	
					\draw[-] (315.north) -- (415.south);	
				
					\draw[-] (415.east) -- (416.west);	
					
				
					\draw[-] (116.north) -- (216.south);	
				
					\draw[-] (316.north) -- (416.south);	
			\end{tikzpicture}
	\end{adjustbox}
		\caption{Tree representation (top) of some \(\mathcal T \in \mathcal T^{\mathcal Q}\), corresponding grid depiction (left) and associated graph (right) for a \(2^{\ell} \times 2^{\ell}\) with \(\ell = 4\) environment.  The connectivity of the graph is consistent with the definition of nodal neighbor.  The nodes in \(\mathcal T_{\mathcal W}\) that are not in \(\mathcal T\) are shown in grey.}
		\label{fig:gridAndQtreeAbstraction}
\end{figure}

In order to utilize the tree \(\mathcal T \in \mathcal T^{\mathcal Q}\) for planning, we must specify how the nodes in the tree \(\mathcal T\) are connected.
To this end, we consider the nodes \(n,\hat n \in \mathcal N\left( \mathcal T_{\mathcal W} \right)\) as \emph{nodal neighbors} if the following statements hold:
	\begin{enumerate}
		\item 
		\(\lVert \mathbf{p}(n) - \mathbf{p}(\hat n) \rVert_{\infty} = 2^{r(n) - 1} + 2^{r(\hat n)  - 1}\),
		
		\item 
		There exists a unique \(i \in \left\{1,\ldots,d \right\}\) such that \(\lvert \left[\mathbf{p}(n) - \mathbf{p}(\hat n)\right]_i\rvert = 2^{r(n) - 1} + 2^{r(\hat n)  - 1}\),
	\end{enumerate}
	where \(\left[ \mathbf{p}(n) - \mathbf{p}(\hat n) \right]_i\) denotes the \(i^{\text{th}}\) entry of the vector \(\mathbf{p}(n) - \mathbf{p}(\hat n)\) and \(|\cdot|\) denotes the absolute value.
Then, for each tree \(\mathcal T \in \mathcal T^{\mathcal Q}\) there exists an associated graph \(\mathcal G(\mathcal T) = \left(\mathcal V(\mathcal T), E(\mathcal T) \right)\), constructed from the leaf nodes of \(\mathcal T\), consisting of a set of vertices \(\mathcal V(\mathcal T)\) and edges \(E(\mathcal T)\), where the set \(E(\mathcal T)\) describes the connectivity of the vertices in \(\mathcal V (\mathcal T)\).
To describe the relation between \(\mathcal V(\mathcal T)\) and \(\mathcal N_{\text{leaf}}\left(\mathcal T\right)\), we define the mapping \(\texttt{Node}_{\mathcal G(\mathcal T)}:\mathcal V(\mathcal T) \to \mathcal N(\mathcal T_{\mathcal W})\) such that if \(n_v \triangleq \texttt{Node}_{\mathcal G(\mathcal T)}(v)\), then the vertex \(v \in \mathcal V(\mathcal T)\) corresponds to the node \(n_v \in \mathcal N(\mathcal T_{\mathcal W})\)\footnote{The mapping \(\texttt{Node}_{\mathcal G(\mathcal T)}\) has co-domain \(\mathcal N(\mathcal T_{\mathcal W})\) since the set \(\mathcal N(\mathcal T_{\mathcal W})\) contains all nodes of any tree \(\mathcal T \in \mathcal T^{\mathcal Q}\).}.
Thus, for any two vertices \(v,\hat v \in \mathcal V(\mathcal T)\), \((v,\hat v) \in E(\mathcal T)\) if and only if the nodes \(n_v,n_{\hat v} \in \mathcal N_{\text{leaf}}(\mathcal T) \subseteq \mathcal N(\mathcal T_{\mathcal W})\) are nodal neighbors.
A visual depiction of this relation is provided in Figure \ref{fig:gridAndQtreeAbstraction}. 
Note that the above process describes how a graph \(\mathcal G(\mathcal T)\) can be constructed when given any tree \(\mathcal T \in \mathcal T^{\mathcal Q}\).





Before discussing the application to path-planning, we require the formalism of a probability space and its relation to the tree \(\mathcal T_{\mathcal W}\).
The need for this stems from the information-theoretic framework utilized for compression and the technical considerations pertaining to the probibalistic encoding of obstacles by the OG.
To this end, let \(\left( \Omega, \mathcal F, \mathbb P\right)\) be a probability space with finite sample space \(\Omega\), \(\sigma\)-algebra \(\mathcal F\), and probability measure \(\mathbb P:\mathcal F \to [0,1]\).
Define random variables \(X:\Omega \to \mathcal N_{\text{leaf}}\left( \mathcal T_{\mathcal W} \right)\) and \(Y:\Omega \to \{0,1\}\), with associated distributions \(p(x) = \mathbb{P}\left( \left\{\omega \in \Omega: X(\omega) = x \right\} \right)\) and \(p(y) = \mathbb{P}\left( \left\{\omega \in \Omega: Y(\omega) = y \right\} \right)\).
The random variables \(X\) and \(Y\) can then be viewed as representing each of the unit hypercubes of \(\mathcal W\) and the total cell occupancy, respectively, where for \(y \in \Omega_Y = \{0,1\}\), we let \(y = 1\) represent the outcome of ``occupied'' and \(y = 0\) correspond to the outcome of ``empty''.
The OG representation of \(\mathcal W\) then provides us with the conditional distribution \(p(y=1 | x)\) for all \(x \in \Omega_X\), where \(p(y=1 | x)\) is the probability that the cell \(x \in \Omega_X\) is occupied.

\vspace{0.4cm}

\section{PROBLEM FORMULATION} \label{sec:problemFormul}
The problem we are interested in is defined as follows.

\begin{problem} \label{prob:frp_approx}
Given the tree \(\mathcal T_{\mathcal W}\), a scalar \(\varepsilon \in [0,1]\), constants \(\lambda_1 \in (0,1], \lambda_2 \in [0,1]\) with \(\lambda = (\lambda_1,\lambda_2)\), a start node \(s_0 \in \mathcal N_{\text{leaf}}(\mathcal T_{\mathcal W})\) and a goal node \(s_g \in \mathcal N_{\text{leaf}}(\mathcal T_{\mathcal W})\), we consider the problem of obtaining a \emph{finest-resolution path} (FRP) \(\pi = \left\{x_0,\ldots,x_K \right\} \subseteq \mathcal N_{\text{leaf}}(\mathcal T_{\mathcal W})\) where \(x_0 = s_0\), \(x_K = s_g\), each \(x \in \pi\) is distinct, and \(x_i,x_{i+1} \in \pi\) are nodal neighbors for all \(i \in \{0,\ldots,K-1\}\), so as to satisfy 
\begin{equation} \label{eq:FRPpathProblem}
\pi^* \in \argmin_{\pi \in \Pi} J^{\lambda}_{\varepsilon}(\pi),
\end{equation}
where 
\begin{equation}\label{eq:FRPpathCost}
J^{\lambda}_{\varepsilon}(\pi) = \sum_{x \in \pi} c^{\lambda}_{\varepsilon}(x),
\end{equation}
and 
\begin{equation}\label{eq:FRPcost}
c^{\lambda}_{\varepsilon}(x) = \begin{cases}
\lambda_1 + \lambda_2 p(y = 1 |x), & \text{if} ~ x \in \mathcal P_{\varepsilon},\\
M_{\varepsilon}^{\lambda}, & \text{if} ~ x \in \mathcal{N}_{\text{leaf}}(\mathcal T_{\mathcal W}) \setminus \mathcal P_{\varepsilon},
\end{cases}
\end{equation}
with \(M_{\varepsilon}^{\lambda} = 2^{d\ell}(\lambda_1 + \varepsilon \lambda_2) + \gamma\) for any \(\gamma > 0\),\footnote{Strictly speaking, \(\gamma > 0\) may be any positive number.  However, we let \(\gamma = 2\) in this paper.} \(\mathcal P_{\varepsilon} = \left\{ x \in \Omega_X: p( y= 1 | x)\leq \varepsilon \right\}\) and where \(\Pi\) denotes the set of FRPs leading from the start node \(s_0\) to the goal \(s_g\) in the tree \(\mathcal T_{\mathcal W}\).
We aim to approximate \eqref{eq:FRPpathProblem} to various degrees of fidelity by leveraging environment abstractions that can be tailored to agent resource constraints so as to reduce the computational complexity of the planning problem.
\hfill \(\triangle\) 
\end{problem}

We call an FRP \(\pi\) for which \(\pi \subseteq \mathcal P_{\varepsilon}\) an \emph{\(\varepsilon\)-feasible} FRP.
The role of \(\varepsilon\) is to define a feasible cell when the obstacle information is encoded probibalistically, and \(M^{\lambda}_{\varepsilon}\) is a factor that penalizes nodes that are considered to be obstacles so as to ensure search algorithms do not include them as part of an FRP unless no feasible paths exist. 
This is important, since nodes \(x \in \mathcal P_{\varepsilon}^{c}\) are \emph{not} removed from the search, ensuring that the right hand side of \eqref{eq:FRPpathProblem} is non-empty.
The choice of cost function \eqref{eq:FRPcost} is inspired by previous works within the robotics community that have considered planning on multi-scale abstractions \cite{Hauer2015}.
The work in this paper is distinct from existing works in that we (i) utilize a principled, information theoretic, framework to generate abstractions not provided a priori as a function of a single trade-off parameter, and (ii) provide theoretical results that couple environment resolution and path cost.
   

The resulting search problem on the graph \(\mathcal G(\mathcal T_{\mathcal W})\) may be computationally expensive.
However, notice that by changing the leaf nodes of the tree \(\mathcal T \in \mathcal T^{\mathcal Q}\), we alter the graph representation \(\mathcal G(\mathcal T)\) and thereby influence the number of nodes and the complexity of the resulting graph-search.
Thus, instead of solving \eqref{eq:FRPpathProblem} directly on \(\mathcal G(\mathcal T_{\mathcal W})\), we propose to approximate \eqref{eq:FRPpathProblem} by a computationally easier-to-solve problem on a graph \(\mathcal G(\mathcal T)\) for some \(\mathcal T \in \mathcal T^{\mathcal Q}\).
The challenge is then to determine how to select the tree \(\mathcal T \in \mathcal T^{\mathcal Q}\) as a function of agent resource constraints.


\section{SOLUTION APPROACH}
In this section, we review an information-theoretic framework from \cite{Larsson2020} that is utilized to generate environment abstractions.
It should be noted that while \cite{Larsson2020} presents a method for the generation of abstractions utilized in this paper, that work does not address the use of abstractions for the purposes of path-planning. 
After a brief review of the abstraction-generating process, we discuss path-planning on the resulting abstractions and show how these solutions can be used as approximations to Problem \ref{prob:frp_approx}.



\subsection{Information-Theoretic Tree Selection} \label{sec:ITIB_Abstractions}
Information theory provides a number of frameworks to construct encoders that compress arbitrary signals \cite{Cover2006,Tishby1999,Slonim2000}.
It is well known that the mutual information between a compressed representation \(Z\) of \(X\), given by 
\begin{equation}
	I(Z;X) \triangleq \sum_{z,x} p(z,x) \log\frac{p(z,x)}{p(z)p(x)},
\end{equation}
measures the amount of compression between the random variables \(X\) and \(Z\) \cite{Cover2006}.
Smaller values of the non-negative quantity \(I(Z;X)\) imply that \(Z\) is a more compressed representation of the original signal \(X\) as compared to those with larger values of \(I(Z;X)\).
However, maximizing compression via the minimization of \(I(Z;X)\) is not a well-posed problem since \(I(Z;X) = 0\) is always attainable.
Instead, one must constrain the problem by a measure that captures how good of a compressed representation \(Z\) is of \(X\).




One particular method of interest is the \emph{information bottleneck} (IB), which defines a good abstraction by the amount of information retained in the compressed representation regarding a third, relevant, random variable \cite{Tishby1999}.
More precisely, the IB method considers the problem
\begin{equation} \label{eq:IBproblemGeneral}
	p^*(z|x) = \argmax_{p(z|x)} I(Z;Y) - \frac{1}{\beta} I(Z;X),
\end{equation}
where \(X\), \(Y\), \(Z\) are random variables corresponding to the original signal, relevant variable and compressed signal, respectively, \(I(Z;Y)\) is the amount of relevant information retained in the compressed representation and \(p(z|x)\) is an encoder, mapping outcomes of \(X\) to outcomes of \(Z\).
The trade-off parameter \(\beta > 0\) balances the amount of relevant information retained in the compressed representation vs. the amount of compression of the original signal.
For discrete random variables and assuming: (i) the Markov chain \(Z \leftrightarrow X \leftrightarrow Y\), encoding the fact that \(Z\) cannot be more informative regarding \(Y\) than \(X\), and (ii) the joint distribution \(p(x,y)\) is provided, a local solution to \eqref{eq:IBproblemGeneral} can be obtained by an algorithm that likens the Blahut-Arimoto algorithm from rate-distortion theory \cite{Tishby1999}.  




However, the resulting encoder \(p^*(z|x)\) is generally stochastic (i.e., \(x\) may have partial membership to multiple \(z\)), and is not guaranteed to represent a tree representation of the environment.
Consequently, direct application of traditional algorithms to solve the problem \eqref{eq:IBproblemGeneral} is not possible.
Constraining the IB problem to the space of multi-resolution tree representations of \(\mathcal W\) presents a significant challenge, and has only recently been investigated \cite{Larsson2020}.

\begin{figure}[t]
	\centering
	\begin{adjustbox}{max size={0.4\textwidth}}
		\begin{tikzpicture}[level distance=1.2cm,
		level 1/.style={sibling distance=3cm},
		level 2/.style={sibling distance=0.7cm}]
		
	
		\node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] at (0,0) {};        
		\node at (7,0) {\Large \(\mathcal T_1\) \normalsize};
		
	
		\node (A) at (0, -0.5) {};
		\node (B) at (0, -1.5) {};
		
		\node (A2) at (7, -0.5) {};
		\node (B2) at (7, -1.5) {};
		
	
		\draw [->, line width=0.5mm, black] (A) -- (B);
		\draw [->, line width=0.5mm, black] (A2) -- (B2);
		
	
		\node at (7,-2) {\Large \(\mathcal T_2\) \normalsize};
		
		\node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] at (0,-2) {}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
		}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
		}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
		}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
		};
		
	
		\node (C) at (0, -2.5) {};
		\node (D) at (0, -3.5) {};
		
		\node (C2) at (7, -2.5) {};
		\node (D2) at (7, -3.5) {};
		
	
		\draw [->, line width=0.5mm, black] (C) -- (D);
		\draw [->, line width=0.5mm, black] (C2) -- (D2);
		
	
		\node at (7,-4) {\Large \(\mathcal T_3\) \normalsize};
		
		\node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] at (0,-4) {}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
		}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
		}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
		}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
		};
		
	
		\node (E) at (0, -4.5) {};
		\node (F) at (0, -5.5) {};
		
		\node (E2) at (7, -4.5) {};
		\node (F2) at (7, -5.5) {};
		
	
		\draw [->, line width=0.5mm, black] (E) -- (F);
		\draw [->, line width=0.5mm, black] (E2) -- (F2);
		
	
		\node at (7,-6) {\Large \(\mathcal T_4\) \normalsize};
		
		\node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] at (0, -6){}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
		}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
		}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
		}
		child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
			child {node[shape = circle, draw, line width = 1pt, minimum size = 2.5mm, inner sep = 0mm] {}}
		};
		
		\end{tikzpicture}
	\end{adjustbox}
	\caption{Sequence of trees \(\left\{ \mathcal T_i \right\}_{i=1}^{4} \subseteq \mathcal T^{\mathcal Q}\) leading from \(\mathcal T_1 = \texttt{Root}(\mathcal T_{\mathcal W})\) to \(\mathcal T_4\).
		Note that \(\mathcal T_1 = \texttt{Root}\left( \mathcal T_{\mathcal W}\right)\) is the root node of \(\mathcal T_{\mathcal W}\) and \(\mathcal N\left( \mathcal T_{i+1}\right) \setminus \mathcal N\left( \mathcal T_{i}\right) = \mathcal C(n)\) for some \(n \in \mathcal N_{\text{leaf}}\left( \mathcal T_i \right)\) holds all \(i \in \{1,2,3\}\).}
	\label{fig:sequenceOfTrees}
\end{figure}


A key observation in formulating the problem \eqref{eq:IBproblemGeneral} over the space of multi-resolution trees is that each tree \(\mathcal T_q \in \mathcal T^{\mathcal Q}\) can be represented by a corresponding encoder of the form \(p^q(z|x)\), where \(p^q(z|x)\) specifies how the leaf nodes \(x \in \mathcal N_{\text{leaf}}\left(\mathcal T_{\mathcal W} \right)\) are mapped to nodes \(z \in \mathcal N_{\text{leaf}}\left( \mathcal T_q \right)\) to create the tree \( \mathcal T_q\) \cite{Larsson2020}. 
Thus, one may define the IB problem over the space of trees as 
\begin{equation}\label{eq:IBtreeProblem}
\mathcal T_{q^*} \in \argmax_{\mathcal T_q \in \mathcal T^{\mathcal Q}} L_Y(\mathcal T_q;\beta),
\end{equation}
where 
\begin{equation}
L_Y(\mathcal T_q;\beta) = K_Y(p^q(z|x);\beta),
\end{equation}
and 
\begin{equation} \label{eq:IBlagrangian}
K_Y(p(z|x);\beta) = I(Z;Y) - \frac{1}{\beta}I(Z;X).
\end{equation}
The problem \eqref{eq:IBtreeProblem} is difficult to solve for large world environments since the space of feasible multi-resolution trees can be large, making grid-search methods that exhaustively enumerate candidate solutions computationally intractable.



However, note that any tree \(\mathcal T_q \in \mathcal T^{\mathcal Q}\) can be obtained by starting at the tree \(\texttt{Root}(\mathcal T_\mathcal W) \in \mathcal T^{\mathcal Q}\) and performing a sequence of nodal expansions, as illustrated in Figure \ref{fig:sequenceOfTrees} \cite{Larsson2020}.
To capture this incremental change in \eqref{eq:IBlagrangian}, we define
\begin{equation}
\Delta L_Y(\mathcal T_i,\mathcal T_{i+1};\beta) = K_Y(p^{i+1}(z|x);\beta) - K_Y(p^i(z|x);\beta),
\end{equation}
which can be shown to only be a function of those nodes in \(\mathcal T_{i+1}\) that are merged to create the tree \(\mathcal T_i\) \cite{Larsson2020}.



Consequently, one can write the IB problem over the space of trees as 
\begin{equation} \label{eq:sequenicalIBLagragian}
\max_{m} \max_{\left\{\mathcal T_1,\ldots,\mathcal T_m \right\}} L_Y(\mathcal T_0;\beta) + \sum_{i=0}^{m-1} \Delta L_Y(\mathcal T_{i},\mathcal T_{i+1};\beta),
\end{equation}
where \(\mathcal T_0 \in \mathcal T^{\mathcal Q}\) is a given tree at which we start the nodal expansion process.
The tree \(\mathcal T_0\) is generally selected to be the tree \(\texttt{Root}(\mathcal T_{\mathcal W})\) so as to ensure that all trees in the space \(\mathcal T^{\mathcal Q}\) are obtainable via nodal expansion.
By changing the value of \(\beta > 0\), we alter the tree \(\mathcal T \in \mathcal T^{\mathcal Q}\), and thereby the corresponding multi-resolution representation of \(\mathcal W\), that emerges as a solution to \eqref{eq:sequenicalIBLagragian}.
Specifically, as \(\beta \to \infty\) we recover a tree \(\mathcal T \in \mathcal T^{\mathcal Q}\) that retains all the relevant information in \(\mathcal T_\mathcal W\) and as \(\beta \to 0\), we obtain the tree that maximizes compression (the root node), with a spectrum of solutions obtained for intermediate values of \(\beta > 0\).



Since the incremental change \(\Delta L_Y(\mathcal T_{i},\mathcal T_{i+1};\beta)\) does not depend on the entire configuration of the tree, one can compute the change in cost of expanding the node \(n \in \mathcal N_{\text{int}}(\mathcal T_\mathcal W)\), thereby removing \(n\) as a leaf node of the tree \(\mathcal T_i\) and adding \(\mathcal C(n)\) as leafs to create the tree \(\mathcal T_{i+1}\), according to 
\begin{equation} \label{eq:node-wiseDeltaL}
\Delta \tilde L_Y(n;\beta) = \Delta I_Y(n) - \frac{1}{\beta}\Delta I_X(n).
\end{equation}
In this relation, \(\Delta I_Y(\cdot)\) and \(\Delta I_X(\cdot)\) are non-negative functions that capture \(I(Z_{i+1};Y) - I(Z_i;Y)\) and \(I(Z_{i+1};X) - I(Z_i;X)\), respectively, where \(Z_{i}\) represents the compressed random variable encoded by the tree \(\mathcal T_{i}\), with \(Z_{i+1}\) defined analogously.
Through direct calculation, the functions \(\Delta I_Y(\cdot)\) and \(\Delta I_X(\cdot)\) can be shown to be dependent on the joint distribution \(p(x,y)\) through the Jensen-Shannon divergence measure and Shannon entropy, respectively \cite{Larsson2020,Slonim2000}.



The node-wise property in \eqref{eq:node-wiseDeltaL} is utilized by algorithms to solve the problem \eqref{eq:sequenicalIBLagragian}.
For example, a greedy approach inspects \(\Delta \tilde L_Y(n;\beta)\) in the set \(n \in \mathcal N_{\text{leaf}}(\mathcal T_i)\), and terminates if \(\Delta \tilde L_Y(n;\beta) \leq 0\) for all \(n \in \mathcal N_{\text{leaf}}(\mathcal T_{i})\) \cite{Larsson2020}.
While simple, such an approach does not generally find optimal solutions.
To overcome this, the authors of \cite{Larsson2020} define a function such that if \(n \in \mathcal N_{\text{int}}(\mathcal T_\mathcal W) \), then
\begin{equation}\label{eq:nodeWiseQfunction1}
\tilde Q_Y(n;\beta) = \max \{ \Delta \tilde L_Y(n;\beta) +  \sum_{n' \in \mathcal C(n)} \tilde Q_Y(n';\beta), ~ 0 \},
\end{equation}
and otherwise, if \(n \notin \mathcal N_{\text{int}}(\mathcal T_\mathcal W)\), then
\begin{equation}\label{eq:nodeWiseQfunction2}
\tilde Q_Y(n;\beta) = 0.
\end{equation}
The \(\tilde Q_Y\)-function incorporates reward of future expansions, analogously to Q-functions in reinforcement learning, and forms the basis for the so-called Q-tree search algorithm \cite{Larsson2020}.
Q-tree search then expands those nodes \(n \in \mathcal N_{\text{leaf}}(\mathcal T_i)\) of the current tree \(\mathcal T_i\) for which \(\tilde Q_Y(n;\beta) > 0\), continuing this process until it reaches a tree \(\mathcal T_{q^*}\) for which all nodes \(n \in \mathcal N_{\text{leaf}}(\mathcal T_{q^*})\) are such that \(\tilde Q_Y(n;\beta) \leq 0\).
We will make use of the Q-tree search algorithm to generate abstractions for the purpose of path planning, which we discuss next.






\subsection{Path-Planning on Abstractions} \label{sec:planningOnAbstractions}
Given a sequence of strictly increasing \(\beta > 0\), denoted by \(\left\{ \beta_i \right\}_{i=1}^N\), we generate a corresponding sequence of trees \(\left\{ \mathcal T_{\beta_i} \right\}_{i=1}^N\) by solving the information-theoretic problem in Section \ref{sec:ITIB_Abstractions} by employing the Q-tree search algorithm. 
A corresponding sequence of graphs \(\left\{ \mathcal G(\mathcal T_{\beta_i} ) \right\}_{i=1}^{N}\) can then be constructed, where each \(\mathcal G(\mathcal T_{\beta_i})\) for \(i\in \{1,\ldots,N\}\) represents a multi-resolution depiction of the environment \(\mathcal W\) with fewer vertices than \(\mathcal G(\mathcal T_{\mathcal W})\).
We will now use these reduced graphs to form approximations to Problem \ref{prob:frp_approx}, which brings us to the following definitions.
\begin{definition}[\hspace{-0.5pt}\cite{Larsson2020}] \label{def:treeLeaf} 
	Let \(n \in \mathcal N(\mathcal T)\) be a node in the tree \(\mathcal T\in \mathcal T^{\mathcal Q}\).  
	\emph{The subtree of} \(\mathcal T \in \mathcal T^{\mathcal Q}\) \emph{rooted at node} \(n\) is denoted by \(\mathcal T_{(n)}\) and has node set
		\begin{equation*}
		\mathcal N\left(\mathcal T_{(n)} \right) = \Big\{ n' \in \mathcal N(\mathcal T): n' \in  \bigcup_{i} \mathcal D_i \Big\},
		\end{equation*}
		where \(\mathcal D_1 = \left\{ n \right\}\), \(\mathcal D_{i+1} = \mathcal A \left( \mathcal D_i \right)\), and 
		\begin{equation*}
		\mathcal A\left( \mathcal D_i \right) = \Big\{ n' \in \mathcal N(\mathcal T_{\mathcal W}): n' \in \bigcup_{\hat n \in \mathcal{D}_i}\mathcal C\left( \hat n \right) \Big\}.
		\end{equation*}
\end{definition}

\begin{definition}
	An \emph{abstract path} (AP) is a sequence of nodes \(\hat{\pi} = \left\{z_0,\ldots, z_R \right\} \subseteq \mathcal N_{\text{leaf}}\left( \mathcal T \right)\) for some \(\mathcal T\in \mathcal T^{\mathcal Q}\), \(\mathcal T \neq \mathcal T_{\mathcal W}\), such that  each \(z \in \hat\pi\) is distinct, the nodes \(z_0\) and \(z_R\) satisfy \(s_0 \in \mathcal N_{\text{leaf}}(\mathcal T_{\mathcal W(z_0)})\) and \(s_g \in \mathcal N_{\text{leaf}}(\mathcal T_{\mathcal W(z_R)})\), respectively, and if \(R > 0\) then \(z_i\), \(z_{i+1}\) are nodal neighbors for all \(i \in \{0,\ldots,R-1\}\).
	An \emph{\(\varepsilon\)-feasible abstract path} (\(\varepsilon\)-AP) is an AP \(\hat \pi\) such that \(\underset{z \in \hat \pi}{\bigcup}\mathcal N_{\text{leaf}}(\mathcal T_{\mathcal W(z)}) \subseteq \mathcal P_{\varepsilon}\).
\end{definition}

To obtain an AP requires the definition of a cost-function for abstracted representations.
This is challenging since the cost must: (i) be consistent with an FRP on the finest resolution; (ii) account for the cost of traversing aggregated nodes; and (iii) monotonically decrease with increased resolution, or equivalently, with increased \(\beta\).
The criterion (iii) above is to ensure that the paths \(\left\{ \hat{ \pi}_{\beta_i} \right\}_{i=1}^N\) represent approximations to an FRP \(\pi\) in the sense that the cost of a path \(\hat \pi_{\beta_i}\) should reduce to, and approach that of, an FRP \(\pi\) as \(\beta_i \to \infty\).



\begin{figure}[!t]
	\centering
	\begin{adjustbox}{max size={0.6\textwidth}}
		\begin{tikzpicture}[scale=.8,every node/.style={minimum size=1cm}]
		
		\begin{scope}[
		local bounding box=scope1,yshift=0,every node/.append style={
			yslant=0.5,xslant=-1},yslant=0.5,xslant=-1
		]
	
	
	
	
	
	
		
		\draw[step=0.5cm, black!10!] (0.99,0) grid (2,1); 
		\draw[step=0.5cm, black!10!] (1.99,2.99) grid (2.5,3.5); 
		\draw[step=0.5cm, black!10!] (0,1.99) grid (0.5,3); 
		\draw[step=0.5cm, black!10!] (2.99,1.99) grid (4,2.5); 
		\draw[step=0.5cm, black!10!] (2.49,0.99) grid (3,1.5); 
		\draw[step=0.5cm, black!10!] (2.99,0.499) grid (3.5,1);
		\draw[step=0.5cm, black!10!] (0.49,1.49) grid (1,2.5);	
		\draw[step=0.5cm, black!10!] (3.5,0) grid (4,0.5);	
		
	
	
		\draw[step=1cm, black!10!] (0,3) grid (1,4);
		\draw[step=1cm, black!10!] (1,3) grid (2,4);
		\draw[step=1cm, black!10!] (1,2) grid (2,3);
		\draw[step=1cm, black!10!] (3,3) grid (4,4);
		\draw[step=1cm, black!10!] (3,1) grid (4,2);
		
	
	
		\draw[step=0.25cm, black!10!] (0,0) grid (0.5,1.99);
		\draw[step=0.25cm, black!10!] (0.5,0) grid (1,1.49);
		\draw[step=0.25cm, black!10!] (1,0.99) grid (2.5,2);
		\draw[step=0.25cm, black!10!] (2,1.99) grid (3,3);
		\draw[step=0.25cm, black!10!] (2,3.49) grid (3,4);
		\draw[step=0.25cm, black!10!] (2,0) grid (3,1);
		\draw[step=0.25cm, black!10!] (3,2.5) grid (4,3);
		\draw[step=0.25cm, black!10!] (3,0) grid (3.5,0.5);
		\draw[step=0.25cm, black!10!] (3.5,0.49) grid (4,1);
	
	
	
		\filldraw[color= black!10!,fill=red!70!,very thin] (0,3) rectangle (1,4);
		\filldraw[color= black!10!,fill=red!40!,very thin] (1,3) rectangle (2,4);	
		\filldraw[color= black!10!,fill=red!10!,very thin] (1,2) rectangle (2,3);	
		\filldraw[color= black!10!,fill=red!45!,very thin] (3,3) rectangle (4,4);	
		\filldraw[color= black!10!,fill=red!80!,very thin] (3,1) rectangle (4,2);	
		
	
		\filldraw[color= black!10!,fill=red!45!,very thin] (1,0) rectangle (1.5,0.5);
		\filldraw[color= black!10!,fill=red!70!,very thin] (1.5,0.5) rectangle (2,1);	
		\filldraw[color= black!10!,fill=red!30!,very thin] (2,3) rectangle (2.5,3.5);
		\filldraw[color= black!10!,fill=red!30!,very thin] (2.5,3) rectangle (3,3.5);
		\filldraw[color= black!10!,fill=red!10!,very thin] (2.5,1.5) rectangle (3,2);					
		
	
		\filldraw[color= black!10!,fill=red!15!,very thin] (1.5,1.25) rectangle (1.75,1.5);
		\filldraw[color= black!10!,fill=red!63!,very thin] (1.5,1.5) rectangle (1.75,1.75);
		
		\filldraw[color= black!10!,fill=red!30!,very thin] (2,1.5) rectangle (2.25,1.75);
	
	
	
	
	
	
	
	
		
	
		\fill[cyan!30!] (0,0) rectangle (0.25,0.25);
		\node[circle,draw=cyan,fill=cyan,very thin,inner sep=0pt, minimum size=0.0625cm] (11) at (0.125, 0.125) {};
	
		
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (21) at (0.125, 0.375) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (31) at (0.125, 0.625) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (41) at (0.125, 0.875) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (51) at (0.125, 1.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (61) at (0.125, 1.375) {};
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (12) at (0.375, 0.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (62) at (0.375, 1.375) {};
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (13) at (0.625, 0.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (63) at (0.625, 1.375) {};
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (14) at (0.875, 0.125) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (24) at (0.875, 0.375) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (34) at (0.875, 0.625) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (44) at (0.875, 0.875) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (54) at (0.875, 1.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (64) at (0.875, 1.375) {};
		
	
	
	
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (15) at (1.125, 1.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (25) at (1.125, 1.375) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (35) at (1.125, 1.625) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (45) at (1.125, 1.875) {};
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (16) at (1.375, 1.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (46) at (1.375, 1.875) {};
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (17) at (1.625, 1.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (47) at (1.625, 1.875) {};
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (18) at (1.875, 1.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (48) at (1.875, 1.875) {};			
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (59) at (2.125, 1.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (89) at (2.125, 1.875) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (99) at (2.125, 2.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (109) at (2.125, 2.375) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (119) at (2.125, 2.625) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (129) at (2.125, 2.875) {};
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (510) at (2.375, 1.125) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (610) at (2.375, 1.375) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (710) at (2.375, 1.625) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (810) at (2.375, 1.875) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (910) at (2.375, 2.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (1310) at (2.375, 3.625) {};
		
	
		\fill[green!30!] (2.25,3.75) rectangle (2.5,4);
		\node[circle,draw=green,fill=green,very thin,inner sep=0pt, minimum size=0.0625cm] (1410) at (2.375, 3.875) {};
	
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (511) at (2.625, 2.125) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (611) at (2.625, 2.375) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (711) at (2.625, 2.625) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (811) at (2.625, 2.875) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (911) at (2.625, 3.625) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (1011) at (2.625, 3.875) {};
		
		
	
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (c13) at (2.25, 3.25) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (c34) at (2.75, 3.25) {};
		
		
	
	
		
	
	
	
		
	
	
	
		
	
		\draw[-,blue] (11.north) -- (21.south);
		\draw[-,black] (11.east) -- (12.west);	
	
		\draw[-,blue] (21.north) -- (31.south);
	
		\draw[-,blue] (31.north) -- (41.south);
	
		\draw[-,blue] (41.north) -- (51.south);
	
		\draw[-,blue] (51.north) -- (61.south);
	
		\draw[-,blue] (61.east) -- (62.west);		
		
	
		\draw[-,black] (12.east) -- (13.west);		
	
		\draw[-,blue] (62.east) -- (63.west);		
		
	
		\draw[-,black] (13.east) -- (14.west);	
	
		\draw[-,blue] (63.east) -- (64.west);	
		
	
		\draw[-,black] (14.north) -- (24.south);
	
		\draw[-,black] (24.north) -- (34.south);
	
		\draw[-,black] (34.north) -- (44.south);
	
		\draw[-,black] (44.north) -- (54.south);
	
		\draw[-,black] (54.east) -- (15.west);
	
		\draw[-,blue] (64.east) -- (25.west);
		
	
	
	
		\draw[-,black] (15.east) -- (16.west);
	
		\draw[-,blue] (25.north) -- (35.south);
	
		\draw[-,blue] (35.north) -- (45.south);
	
		\draw[-,blue] (45.east) -- (46.west);
		
	
		\draw[-,black] (16.east) -- (17.west);
	
		\draw[-,blue] (46.east) -- (47.west);
		
	
		\draw[-,black] (17.east) -- (18.west);
	
		\draw[-,blue] (47.east) -- (48.west);
		
	
		\draw[-,black] (18.east) -- (59.west);
	
		\draw[-,blue] (48.east) -- (89.west);
		
	
		\draw[-,black] (59.east) -- (510.west);
	
		\draw[-,blue] (89.north) -- (99.south);
	
		\draw[-,blue] (99.north) -- (109.south);
	
		\draw[-,blue] (109.north) -- (119.south);
	
		\draw[-,blue] (119.north) -- (129.south);
	
		\draw[-,blue] (129.north) -- (c13.south);
	
		\draw[-,blue] (c13.north) -- (1310.south);
		
	
		\draw[-,black] (510.north) -- (610.south);
	
		\draw[-,black] (610.north) -- (710.south);
	
		\draw[-,black] (710.north) -- (810.south);
	
		\draw[-,black] (810.north) -- (910.south);
	
		\draw[-,black] (910.east) -- (511.west);
	
		\draw[-,blue] (1310.north) -- (1410.south);
	
		\draw[-,black] (1410.east) -- (1011.west);
		
	
		\draw[-,black] (511.north) -- (611.south);
	
		\draw[-,black] (611.north) -- (711.south);
	
		\draw[-,black] (711.north) -- (811.south);
	
		\draw[-,black] (811.north) -- (c34.south);
	
		\draw[-,black] (c34.north) -- (911.south);
	
		\draw[-,black] (911.north) -- (1011.south);
		
	
	
		\draw[draw=magenta,very thick] (2,2.5) rectangle (3,4);
		
	
		\coordinate (LR) at (3,2.5); 
		\coordinate (UR) at (3,4); 
		\coordinate (LL) at (2,2.5); 
		\coordinate (UL) at (2,4);
		
		\end{scope}
	
	
		\begin{scope}[
		local bounding box=scope2,shift={($(scope1.north)+(0cm,0.0cm)$)},scale=0.7,every node/.append style={
			yslant=0.5,xslant=-1},yslant=0.5,xslant=-1
		]
		
	
		
	
	
	
	
		\draw[step=0.5cm, black!10!] (0,0.99) grid (0.5,1.5); 
		
	
	
		\draw[step=0.25cm, black!10!] (0,0.49) grid (1,1);
		\draw[step=0.25cm, black!10!] (0,1.49) grid (1,2);
		
	
		\filldraw[color=black!10!,fill=red!30!] (0,1) rectangle (0.5,1.5);
		\filldraw[color=black!10!,fill=red!30!] (0.5,1) rectangle (1,1.5);
		
	
	
	
	
	
	
	
	
	
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (119) at (0.125, 0.625) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (129) at (0.125, 0.875) {};
		
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (1310) at (0.375, 1.625) {};
		
	
		\fill[green!30!] (0.25,1.75) rectangle (0.5,2);
		\node[circle,draw=green,fill=green,very thin,inner sep=0pt, minimum size=0.0625cm] (1410) at (0.375, 1.875) {};
	
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (711) at (0.625, 0.625) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (811) at (0.625, 0.875) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (911) at (0.625, 1.625) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (1011) at (0.625, 1.875) {};
		
	
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (c13) at (0.25, 1.25) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (c34) at (0.75, 1.25) {};
		
	
	
	
		
	
	
		
	
		\draw[-,blue] (119.north) -- (129.south);
	
		\draw[-,blue] (129.north) -- (c13.south);
	
		\draw[-,blue] (c13.north) -- (1310.south);
		
	
		\draw[-,blue] (1310.north) -- (1410.south);
	
		\draw[-,black] (1410.east) -- (1011.west);
		
	
		\draw[-,black] (711.north) -- (811.south);
	
		\draw[-,black] (811.north) -- (c34.south);
	
		\draw[-,black] (c34.north) -- (911.south);
	
		\draw[-,black] (911.north) -- (1011.south);
		
	
	
		\draw[draw=magenta] (0,0.5) rectangle (1,2);
		
	
		\coordinate (LR2) at (1,0.49); 
		\coordinate (UR2) at (1,2); 
		\coordinate (LL2) at (0,0.49); 
		\coordinate (UL2) at (0,2);
	
		\end{scope}
		
	
	
		\draw[-,magenta,thick,opacity=0.2] (LR) -- (LR2);
		\draw[-,magenta,thick,opacity=0.2] (UR) -- (UR2);
		\draw[-,magenta,thick,opacity=0.2] (LL) -- (LL2);
		\draw[-,magenta,thick,opacity=0.2] (UL) -- (UL2);
	
		
	
	
	
		\begin{scope}[
		local bounding box=scope3,shift={($(scope1.east)+(8cm,0cm)$)},scale=2.2,every node/.append style={
			yslant=0.5,xslant=-1.2},yslant=0.5,xslant=-1.2
		]
		
	
		
	
	
	
	
	
		\draw[step=0.5cm, black!10!] (0,0.99) grid (0.5,1.5); 
		
	
	
		\draw[step=0.25cm, black!10!] (0,0.49) grid (1,1);
		\draw[step=0.25cm, black!10!] (0,1.49) grid (1,2);
		
	
	
		\filldraw[color=black!10!,fill=red!30!] (0,1) rectangle (0.5,1.5);
		\filldraw[color=black!10!,fill=red!30!] (0.5,1) rectangle (1,1.5);
		
	
	
	
	
	
	
	
	
	
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (119) at (0.125, 0.625) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (129) at (0.125, 0.875) {};
		
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (1310) at (0.375, 1.625) {};
		
	
		\fill[green!30!] (0.25,1.75) rectangle (0.5,2);
		\node[circle,draw=green,fill=green,very thin,inner sep=0pt, minimum size=0.0625cm] (1410) at (0.375, 1.875) {};
	
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (711) at (0.625, 0.625) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (811) at (0.625, 0.875) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (911) at (0.625, 1.625) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (1011) at (0.625, 1.875) {};
		
	
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (c13) at (0.25, 1.25) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (c34) at (0.75, 1.25) {};
		
	
	
	
		
	
	
		
	
		\draw[-,blue] (119.north) -- (129.south);
	
		\draw[-,blue] (129.north) -- (c13.south);
	
		\draw[-,blue] (c13.north) -- (1310.south);
		
	
		\draw[-,blue] (1310.north) -- (1410.south);
	
		\draw[-,black] (1410.east) -- (1011.west);
		
	
		\draw[-,black] (711.north) -- (811.south);
	
		\draw[-,black] (811.north) -- (c34.south);
	
		\draw[-,black] (c34.north) -- (911.south);
	
		\draw[-,black] (911.north) -- (1011.south);
		
	
	
		\draw[draw=magenta] (0,0.5) rectangle (1,2);
		
	
	
		\coordinate (BC1) at (0.25, 1.25); 
		\coordinate (BC2) at (0.75, 1.25); 
		
	
		\coordinate (LR3) at (1,0.49); 
		\coordinate (UR3) at (1,2); 
		\coordinate (LL3) at (0,0.49); 
		\coordinate (UL3) at (0,2);
		
	
		\end{scope}
		
	
		
	
	
		\draw[-,magenta,opacity=0.5] (LR2) -- (UR3);
		\draw[-,magenta,opacity=0.5] (LL2) -- (UL3);
	
		
	
	
	
		\begin{scope}[
		local bounding box=scope4,shift={($(scope3.center)+(2.4cm,-5cm)$)},scale=2.8,every node/.append style={
			yslant=0.5,xslant=-1.2},yslant=0.5,xslant=-1.2
		]
		
	
	
	
	
	
		\draw[step=0.25cm, black!10!] (0,0.49) grid (1,2);
		
	
		\filldraw[color=black!10!,fill=red!15!] (0,1.25) rectangle (0.25,1.5);
		\filldraw[color=black!10!,fill=red!15!] (0.25,1.25) rectangle (0.5,1.5);
		
		\filldraw[color=black!10!,fill=red!15!] (0.75,1) rectangle (1,1.25);
		\filldraw[color=black!10!,fill=red!15!] (0.75,1.25) rectangle (1,1.5);
		
		
	
	
	
	
	
	
	
	
	
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (119) at (0.125, 0.625) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (129) at (0.125, 0.875) {};
		
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (1310) at (0.375, 1.625) {};
		
	
		\fill[green!30!] (0.25,1.75) rectangle (0.5,2);
		\node[circle,draw=green,fill=green,very thin,inner sep=0pt, minimum size=0.0625cm] (1410) at (0.375, 1.875) {};
		
	
		
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (711) at (0.625, 0.625) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (811) at (0.625, 0.875) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (911) at (0.625, 1.625) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (1011) at (0.625, 1.875) {};
		
	
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (c133) at (0.375, 1.375) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (c132) at (0.375, 1.125) {};
		\node[circle,draw=blue,fill=blue,very thin,inner sep=0pt, minimum size=0.0625cm] (c131) at (0.125, 1.125) {};
		
	
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (c341) at (0.625, 1.125) {};
		\node[circle,draw=black,fill=black,very thin,inner sep=0pt, minimum size=0.0625cm] (c342) at (0.625, 1.375) {}; 
		
	
	
	
	
	
		
	
		\draw[-,blue] (119.north) -- (129.south);
	
		\draw[-,blue] (129.north) -- (c131.south);
	
		\draw[-,blue] (c133.north) -- (1310.south);
		
	
		\draw[-,blue] (1310.north) -- (1410.south);
		
	
		\draw[-,blue] (c131.east) -- (c132.west);
		
	
		\draw[-,blue] (c132.north) -- (c133.south);
		
	
		\draw[-,black] (1410.east) -- (1011.west);
		
	
		\draw[-,black] (711.north) -- (811.south);
	
		\draw[-,black] (811.north) -- (c341.south);
	
		\draw[-,black] (c341.north) -- (c342.south);
	
		\draw[-,black] (c342.north) -- (911.south);
	
		\draw[-,black] (911.north) -- (1011.south);
		
	
	
		\draw[draw=magenta] (0,0.5) rectangle (1,2);
		
	
	
		\coordinate (BC11) at (0.375, 1.375); 
		\coordinate (BC12) at (0.125, 1.375); 
		\coordinate (BC13) at  (0.125, 1.125); 
		\coordinate (BC14) at (0.375, 1.125) ; 
		
		\coordinate (BC21) at (0.875,1.375); 
		\coordinate (BC22) at (0.625, 1.375); 
		\coordinate (BC23) at (0.625, 1.125); 
		\coordinate (BC24) at (0.875,1.125); 
		
	
	
		\coordinate (LR4) at (1,0.49); 
		\coordinate (UR4) at (1,2); 
		\coordinate (LL4) at (0,0.49); 
		\coordinate (UL4) at (0,2);
	
		\end{scope}
		
	
	
		\draw[-,black,opacity=0.35] (BC1) -- (BC11);
		\draw[-,black,opacity=0.35] (BC1) -- (BC12);
		\draw[-,black,opacity=0.35] (BC1) -- (BC13);
		\draw[-,black,opacity=0.35] (BC1) -- (BC14);
		
		\draw[-,black,opacity=0.35] (BC2) -- (BC21);
		\draw[-,black,opacity=0.35] (BC2) -- (BC22);
		\draw[-,black,opacity=0.35] (BC2) -- (BC23);
		\draw[-,black,opacity=0.35] (BC2) -- (BC24);
	
		
	
	
		\draw[-,black,opacity=0.1] (LR3) -- (LR4);
		\draw[-,black,opacity=0.1] (UR3) -- (UR4);
		\draw[-,black,opacity=0.1] (UL3) -- (UL4);
	
		\end{tikzpicture}
	\end{adjustbox}
	\caption{Example OG of an environment \(\mathcal W\) with two AP \(\hat \pi_1\) (blue) and \(\hat \pi_2\) (black) leading from a given start location (cyan) to goal location (green).  For probabilistic obstacles (red), shading scales with the probability of occupancy.  Notice that both \(\hat \pi_1\) and \(\hat \pi_2\) pass through identical (adjacent) abstracted cells with non-zero probability of occupancy.  To determine the feasibility of these paths requires refinement, shown to the right.  Observe that, upon refinement, the path \(\hat \pi_1\) (blue) will be deemed infeasible, as it is not possible to traverse the left abstracted cell in the direction stipulated by \(\hat \pi_1\).  In contrast, the path \(\hat \pi_2\) (black) is feasible, since the right abstracted cell can be traversed in the direction required by \(\hat \pi_1\).  This shows the difficulty in guaranteeing path feasibility when planning on abstractions.  Our framework and definition of feasibility precludes this situation from occurring.}
	\label{fig:epsilonObsEx}
\end{figure}



To this end, we define \(V^{\lambda}_{\varepsilon}: \mathcal N\left( \mathcal T_{\mathcal W}\right) \to \Re_{+}\) as
\begin{equation} \label{eq:defOfAbstractV}
V^{\lambda}_{\varepsilon}(n) = \begin{cases}
c^{\lambda}_{\varepsilon}(n), & n \in \mathcal N_{\text{leaf}}\left( \mathcal T_{\mathcal W}\right), \\
\frac{1}{2^d}\sum_{n'\in\mathcal C(n)} V^{\lambda}_{\varepsilon}(n'), & \text{otherwise},
\end{cases}
\end{equation}
and consider the objective
\begin{equation} \label{eq:abstractObjectiveFunction}
\hat J^{\lambda}_{\varepsilon}(\hat \pi ; \beta) = \sum_{z \in \hat \pi} 2^{d r(z)}V^{\lambda}_{\varepsilon}(z).
\end{equation}   
Note that \(\hat J^{\lambda}_{\varepsilon}(\hat \pi ; \beta)\) depends on the trade-off parameter \(\beta > 0\), as \(\beta\) determines the tree \(\mathcal T_{\beta} \in \mathcal T^{\mathcal Q}\) on which the AP \(\hat \pi\) is planned.
Given \(\beta > 0\), we consider the problem
\begin{equation} \label{eq:abstractPathProblem}
\hat \pi_{\beta}^* \in \argmin_{\hat \pi \in \hat \Pi_{\beta}} \hat J^{\lambda}_{\varepsilon}(\hat \pi;\beta),
\end{equation} 
where \(\hat \Pi_\beta\) is the set of AP in \(\mathcal T_{\beta} \in \mathcal T^{\mathcal Q}\).

What remains to show is that the objective function value of \eqref{eq:abstractObjectiveFunction} monotonically decreases with increased \(\beta > 0\).
The following theorem establishes this result.
\begin{theorem} \label{thm:monotonicCost} 
	Let \(\varepsilon \in [0,1]\) and assume that there exists \(\beta_2 > \beta_1 > 0\) such that the corresponding trees \(\mathcal T_{\beta_1},\mathcal T_{\beta_2} \in \mathcal T^{\mathcal Q}\) satisfy \(\mathcal N \left(\mathcal T_{\beta_2}\right) \setminus \mathcal N \left(\mathcal T_{\beta_1}\right) = \mathcal C(n)\) for some \(n \in \mathcal N_{\text{leaf}}\left(\mathcal T_{\beta_1} \right)\).
	Furthermore, let \(\hat \pi^*_{\beta_1} \subseteq \mathcal N_{\text{leaf}}\left(\mathcal T_{\beta_1}\right)\) denote an abstract path in the tree \(\mathcal T_{\beta_1} \in \mathcal T^{\mathcal Q}\) satisfying \(\hat \pi^*_{\beta_1} \in \argmin_{\hat \pi_{\beta_1} \in \hat \Pi_{\beta_1}}\hat J^{\lambda}_{\varepsilon}(\hat \pi_{\beta_1};\beta_1)\).
	Then there exists an abstract path \(\hat \pi_{\beta_2} \subseteq \mathcal N_{\text{leaf}}\left(\mathcal T_{\beta_2}\right)\) such that \(\hat J^{\lambda}_{\varepsilon}(\hat \pi^*_{\beta_1};\beta_1) \geq \hat J^{\lambda}_{\varepsilon}(\hat \pi_{\beta_2};\beta_2)\).
\end{theorem}
\begin{proof}
The proof is presented in Appendix \ref{app:thmMonotoneCost}.
\end{proof}


By definition, \(\hat J^{\lambda}_{\varepsilon}(\hat \pi_{\beta_2};\beta_2) \geq \hat J^{\lambda}_{\varepsilon}(\hat \pi^*_{\beta_2};\beta_2)\) for all \(\hat \pi_{\beta_2} \in \hat \Pi_{\beta_2}\), and hence Theorem \ref{thm:monotonicCost} establishes that \(\hat J^{\lambda}_{\varepsilon}(\hat \pi^*_{\beta_1};\beta_1) \geq \hat J^{\lambda}_{\varepsilon}(\hat \pi^*_{\beta_2};\beta_2)\).
It should be noted that the same result holds even though two consecutive trees in the sequence \(\left\{\mathcal T_{\beta_i} \right\}_{i=1}^{N}\) do not necessarily satisfy \(\mathcal N \left(\mathcal T_{\beta_{i+1}}\right) \setminus \mathcal N \left(\mathcal T_{\beta_i}\right) = \mathcal C(n)\) for some \(n \in \mathcal N_{\text{leaf}}\left(\mathcal T_{\beta_i} \right)\).
This follows from the observation that any tree \(\mathcal T_m \in \mathcal T^{\mathcal Q}\) can be obtained from another sequence of trees, and so moving from \(\mathcal T_{\beta_{i}}\) to \(\mathcal T_{\beta_{i+1}}\) can be done by considering a sequence \(\left\{ \mathcal T_{k} \right\}_{k=0}^m\) where \(\mathcal T_{0} = \mathcal T_{\beta_i}\) and \(\mathcal T_{m} = \mathcal T_{\beta_{i+1}}\) for some \(m > 0\) where  \(\mathcal N \left(\mathcal T_{k+1}\right) \setminus \mathcal N \left(\mathcal T_{k}\right) = \mathcal C(n)\) for some \(n \in \mathcal N_{\text{leaf}}\left(\mathcal T_k \right)\) holds for all \(k \in \{0,\ldots,m-1\}\).


Theorem \ref{thm:monotonicCost} guarantees the monotonic improvement of the cost as a function of resolution.
It does not, however, guarantee that the cost of an AP converges to that of an FRP as \(\beta\to\infty\).
To address this, we require the following proposition.
\begin{proposition} \label{thm:convQtreeSearch}
Let \( \Delta I_Y: \mathcal N_{\text{int}}(\mathcal T_\mathcal W) \to [0,\infty) \) be the change in relevant information by expanding the node \(n \in \mathcal N_{\text{int}}(\mathcal T_\mathcal W)\).\footnote{See \cite{Larsson2020} for more information.}
Then the Q-tree search algorithm returns the tree \(\mathcal T_\mathcal W\) as \(\beta \to \infty\) if and only if \(\Delta I_Y(n) > 0\) for all \(n \in \mathcal N_{\ell-1}(\mathcal T_\mathcal W)\).
\end{proposition}
\begin{proof}
The proof is presented in Appendix \ref{app:proofThmConvQtreeSearch}.
\end{proof}
Theorem \ref{thm:monotonicCost} in conjunction with Proposition \ref{thm:convQtreeSearch} guarantee that the path cost sequence \(\{ \hat J^{\lambda}_{\varepsilon}(\hat \pi^*_{\beta_i};\beta_i)\}_{i=1}^N\) monotonically decreases and converges to \(J^{\lambda}_{\varepsilon}(\pi^*)\) as \(\beta_{N} \to \infty\).
We will now present a number of other properties of our problem, for which the following fact is useful.
\begin{fact} \label{fact:vLeafsRelation}
	Let \(u \in \{0,\ldots,\ell \}\), \(\varepsilon \in [0,1]\) and \(n \in r^{-1}(\{u\})\).
	Then \(V^{\lambda}_{\varepsilon}(n) = \frac{1}{2^{d r(n)}}\sum_{n'\in \mathcal N_{\text{leaf}}\left( \mathcal T_{\mathcal W(n)} \right)}V^{\lambda}_{\varepsilon}(n')\).
\end{fact}
\begin{proof}
The proof is presented in Appendix \ref{app:proofFctVleafsRelation}.
\end{proof}
\begin{proposition} \label{prop:epsFeasibleAbsPath}
	Let \(\varepsilon \in [0,1]\) and \(\beta > 0\).
	Then \(\hat J^{\lambda}_{\varepsilon}(\hat \pi;\beta) < M^{\lambda}_{\varepsilon}\) if and only if \(\hat \pi\) is a \(\varepsilon\)-feasible abstract path.
\end{proposition}
\begin{proof}
The proof is presented in Appendix \ref{app:ProofEpsFeasibleAbsPath}.
\end{proof}
\begin{corollary} \label{cor:epsFeasibleFRP}
	Let \(\varepsilon \in [0,1]\).
	Then \(J^{\lambda}_{\varepsilon}(\pi) < M_{\varepsilon}^{\lambda}\) if and only if \(\pi\) is a \(\varepsilon\)-feasible finest resolution path.
\end{corollary}
\begin{proof}
The proof is presented in Appendix \ref{app:ProofcorEpsFeasibleAbsPath}.
\end{proof}
The utility of Proposition \ref{prop:epsFeasibleAbsPath} and Corollary \ref{cor:epsFeasibleFRP} is that they provide conditions for quickly determining the feasibility of a path from knowledge of only the objective function value \(\hat J^{\lambda}_{\varepsilon}(\hat \pi;\beta)\) (or \(J^{\lambda}_{\varepsilon}(\pi)\)).
If the search terminates before an \(\varepsilon\)-feasible path has been found, the agent is provided with the most recent solution, which is guaranteed to be the least infeasible path available in the current tree.
Furthermore, as a result of Theorem \ref{thm:monotonicCost} and Proposition \ref{prop:epsFeasibleAbsPath}, if an AP \(\hat \pi^*_{\beta_{j}}\) is \(\varepsilon\)-feasible for some \(j \in \{1,\ldots, N\}\), then all AP in the sequence \(\{\hat \pi^*_{\beta_i} \}_{i=j}^{N}\) are also \(\varepsilon\)-feasible.
This ensures that the autonomous agent can never discover that a feasible path becomes infeasible with further refinement of the environment. 
An illustration is provided in Figure \ref{fig:epsilonObsEx}.
To conclude this section, we present the following proposition.
\begin{proposition} \label{prop:vEpsAndObs}
	Let \(\varepsilon \in [0,1]\) and \(n \in \mathcal N_{\text{int}}\left( \mathcal T_{\mathcal W} \right)\).
	Then \(V^{\lambda}_{\varepsilon}(n) > \lambda_1 + \varepsilon \lambda_2\) if and only if \(\mathcal N_{\text{leaf}}\left( \mathcal T_{\mathcal W(n)} \right) \cap \mathcal P^{c}_{\varepsilon} \neq \emptyset\).
\end{proposition}
\begin{proof}
The proof is presented in Appendix \ref{app:proofPropVepsAndObs}.
\end{proof}
Proposition \ref{prop:vEpsAndObs} allows an autonomous agent to quickly identify which leaf nodes in the tree \(\mathcal T \in \mathcal T^{\mathcal Q}\) are considered to be \(\varepsilon\)-obstacles and, consequently, which vertices in \(\mathcal G(\mathcal T)\) to avoid, if possible.
Next, we present a numerical example to demonstrate the utility of our approach.


\section{NUMERICAL EXAMPLE} \label{sec:numericalExample}

\begin{figure}[!t]
\centering
\subfloat[]{\includegraphics[width=0.24\textwidth]{environment_occupancy.png}
\label{fig:originalW}}
\subfloat[]{\includegraphics[width=0.24\textwidth]{FRP_ENV_w_graph.png}
\label{fig:originalWwithOPTFRP}}
\subfloat[]{\includegraphics[width=0.24\textwidth]{env_128_eps05_data1_figure_7.png}
\label{fig:pathGraph1}}
\subfloat[]{\includegraphics[width=0.24\textwidth]{env_128_eps05_data1_figure_28.png}
\label{fig:pathGraph2}}
\caption{128\(\times\)128 environment \(\left( \lvert \Omega_X\rvert = 16384 \right)\) with graph abstraction and path examples for \(\varepsilon = 0.5\). Cost parameters are \(\lambda_1 = 0.001\) and \(\lambda_2 = 1\). Shading of grey scales with probability of occupancy. Red vertices are considered \(\varepsilon\)-obstacles as determined by Proposition \ref{prop:vEpsAndObs}. (a) original environment, (b) example FRP, (c) example AP and graph for \(\beta = 55 ~ \left( \%\lvert \Omega_X \rvert = 8.3\% \right)\), (d) example AP and graph for \(\beta = 1\times10^6 ~\left(\%\lvert \Omega_X \rvert = 83.4\% \right)\).}
\end{figure}

We consider the world \(\mathcal W\) to be given by the \(128 \times 128\) occupancy grid shown in Figure \ref{fig:originalW}.
The OG representation provides information regarding the conditional distribution \(p(y|x)\), whereby we then define the joint distribution \(p(y,x) = p(y|x)p(x)\) with \(p(x) = \nicefrac{1}{\lvert \mathcal N_{\text{leaf}}\left(\mathcal T_{\mathcal W}\right) \rvert}\) for all \(x \in \mathcal N_{\text{leaf}}\left(\mathcal T_{\mathcal W}\right)\).
By utilizing the uniform distribution \(p(x)\), we encode that the autonomous agent is equally likely to occupy any cell \(x \in \mathcal N_{\text{leaf}}\left(\mathcal T_{\mathcal W}\right)\) and will result in the IB method refining the environment in a region-agnostic manner \cite{Larsson2020}.
The joint distribution \(p(x,y)\), along with a sequence of strictly increasing positive values of \(\left\{ \beta_i \right\}_{i=1}^N\) are provided to the IB abstraction framework of Section \ref{sec:ITIB_Abstractions} to obtain the sequence of trees \(\left\{ \mathcal T_{\beta_i} \right\}_{i=1}^{N}\) along with the corresponding \(\left\{ \mathcal G\left( \mathcal T_{\beta_i} \right) \right\}_{i=1}^N\).
Given a start and goal location, the path planning problem \eqref{eq:abstractPathProblem} is then solved on each of the trees in the sequence \(\left\{ \mathcal T_{\beta_i} \right\}_{i=1}^{N}\) to obtain \(\{\hat \pi^*_{\beta_i} \}_{i=1}^N\).
Examples of abstract paths in the sequence \(\{\hat \pi^*_{\beta_i} \}_{i=1}^N\) are shown in Figures \ref{fig:pathGraph1} -- \ref{fig:pathGraph2} with a corresponding FRP shown in Figure \ref{fig:originalWwithOPTFRP}.



Figure \ref{fig:aveCostVsCompression} shows the average path cost ratio as a function of compression when averaging over 200 randomly sampled start and goal locations in the environment shown in Figure \ref{fig:originalW}.
For the averaging results, we ensure that the conditions of Proposition \ref{thm:convQtreeSearch} are satisfied to guarantee the path cost ratio converges to one as \(\beta \to \infty\).



From Figure \ref{fig:aveCostVsCompression}, we see that, on average, roughly \(15\%\) to \(18\%\) of the vertices of \(\mathcal G(\mathcal T_\mathcal W)\) are required in order to obtain a feasible path in the environment.
A reduced graph with only \(15\%\) to \(18\%\) of the vertices of \(\mathcal G(\mathcal T_\mathcal W)\) substantially reduces the computational effort required to find feasible solutions.
Figure \ref{fig:aveCostVsCompression} also shows that the path cost monotonically decreases with increased resolution.
The decreasing nature of the cost in Figure \ref{fig:aveCostVsCompression} is expected, since Theorem \ref{thm:monotonicCost} guarantees that the path cost between \emph{any} two points monotonically decreases as a function of resolution (or, equivalently, increased \(\beta > 0\)).
We also observe that the average path cost ratio converges to 1, corroborating the conditions for convergence set forth by Proposition \ref{thm:convQtreeSearch}.
Lastly, note that by utilizing a representation with approximately \(70\%\) of the nodes in \(\mathcal T_\mathcal W\) results, on average, in an abstract path \(\hat\pi^{*}_{\beta_i}\) for which \(\hat J_{\varepsilon}^{\lambda}(\hat \pi^*_{\beta_i};\beta_{i}) \) is within \(30\%\) of \(J^{\lambda}_{\varepsilon}(\pi^*)\).
We now provide some discussion of how our framework relates to bounded-rational decision making and anytime algorithms.
\begin{figure}[!t]
	\centering
	\includegraphics[width=0.5\textwidth]{ave_CostVsComp_dataset3.png}
	\caption{Logarithmic (base 10) value of average \(\nicefrac{\hat{J}^{\lambda}_{\varepsilon}(\hat \pi^*_{\beta_i};\beta_i)}{J_{\varepsilon}^{\lambda}(\pi^*)}\) versus compression for \(\varepsilon = 0.5\), \(\lambda_1 = 0.001\) and \(\lambda_2 = 1\). Note that \(\lvert \Omega_X \rvert = 16384\). Average values computed over 200 randomly sampled start and goal locations. Moving along the curve to the right is done by increasing \(\beta\). Average first feasible path line represents average compression at which first guaranteed feasible path in the abstracted environment is found.}
	\label{fig:aveCostVsCompression}
\end{figure}



\section{DISCUSSION} \label{sec:discussion}
The role of \(\beta > 0\) in our framework can be interpreted similarly to its role in other approaches for resource-constrained and bounded-rational decision making.
In fact, previous works, such as \cite{Larsson2017,Genewein2015,Tishby2010}, that study information-limited decision-making in stochastic domains have viewed the trade-off parameter \(\beta\) as a rationality parameter.
More specifically, these works formulate information-constrained MDPs by adding KL-divergence constraints to traditional MDP problems to constrain by what amount an optimal policy is permitted to differ from a policy provided to the agent beforehand.
In this view, the a priori policy is considered a default policy for which the agent resorts to in case it has no time or ability to discover a possibly better policy.
These studies argue that the resulting optimal policies for rational agents are recovered as \(\beta \to \infty\) and that policies for fully resource-limited agents are found as \(\beta \to 0\), with a spectrum of solutions for intermediate values of \(\beta > 0\).
Similarly, we see that \(\beta\) implicitly trades off the complexity of the search by influencing the number of vertices in the graph \(\mathcal G(\mathcal T_{\beta})\).
Furthermore, \(\beta\) not only trades the complexity of the search, but also changes the value of the resulting optimal path, since larger values of \(\beta\) lead to lower path costs, at the penalty of increased complexity.
In this way, we argue that our framework represents a bridge between bounded rationality and planning, providing a method for which one can trade path-optimality and complexity of the search directly, through a single parameter \(\beta\) and without the need to specify the abstractions a priori.



\begin{figure}[tbh]
	\centering
	\includegraphics[width=0.5\textwidth]{ave_timing_vs_abstraction.png}
	\caption{Average computation time \(\text{vs.}\) environment compression for two-dimensional grid sizes of \(128 \times 128\), \(256 \times 256\) and \(512 \times 512\). By increasing \(\beta\) one moves along the curves to the right. Timing results are obtained by averaging over 100 randomly selected start and goal locations. The y-axis represents average (normalized) time obtained by averaging the time for (i) information computation (population of \(\Delta I_Y(\cdot)\) and \(\Delta I_X (\cdot)\) values), (ii) computing Q-values (for each \(\beta\) according to \eqref{eq:nodeWiseQfunction1}-\eqref{eq:nodeWiseQfunction2}), (iii) running Q-tree search and (iv) employing Dijkstra graph-search to obtain an abstract path and normalizing by the average time to run Dijkstra on the finest-resolution map. Timing results assume the worst-case scenario that abstractions are generated from scratch for each value of \(\beta\) (or compression level) on a computer with a \(2.9\) GHz Intel \(\text{i}5\) CPU with \(8\) GB of RAM running MATLAB.}
	\label{fig:aveTimeVsCompression}
\end{figure}



As discussed, a number of other approaches exist that attempt to decrease the planning complexity of the problem by leveraging environment abstraction \cite{Cowlagi2008,Cowlagi2010,Cowlagi2011,Cowlagi2012,Cowlagi2012a,Tsiotras2007,Tsiotras2012,Kambhampati1986,Hauer2015,Hauer2016}.
While these approaches do provide a means to simplify the path-planning problem, they do not guarantee that the solution improves with increased deliberation, or planning, time.
We argue that our framework can provide a bridge between the planning time, the plan complexity and the plan cost by viewing the trade-off parameter \(\beta > 0\) as having a one-to-one correspondence with time \(t > 0\) by, for example, considering a strictly increasing mapping \(\Gamma(t) = \beta\), where \(\Gamma (\cdot)\) maps time \(t > 0\) to trade-off parameter values.
In this way, the IB as well as the planning problem \eqref{eq:abstractPathProblem} become time-dependent, and the improvement of the solution objective value with time is established by Theorem \ref{thm:monotonicCost}.
By viewing the problem in this way, we facilitate connections between planning complexity, optimality, and time, as suggested by anytime algorithms \cite{Dean1988}.



In regards to complexity and planning time, we note that the \(128 \times 128\) two-dimensional grid presented in Section \ref{sec:numericalExample} serves as an example to corroborate the theoretical results developed in this manuscript in a non-trivial setting.
In some real-world cases, it may happen that the computational benefits of leveraging abstractions for the purposes of planning are unlikely to outweigh the cost of executing Dijkstra directly on the finest resolution graph. 
It is known \cite{Larsson2020} that the complexity of the Q-tree search algorithm is \(\mathcal O(\lvert \mathcal N_{\text{leaf}}(\mathcal T_\mathcal W) \rvert )\) and so the worst-case complexity of executing Q-tree search and planning on the resulting compressed representation is \(\mathcal O(\lvert \mathcal N_{\text{leaf}}(\mathcal T_\mathcal W) \rvert) + \mathcal O(\lvert E(\mathcal T)\rvert + \lvert \mathcal{V}(\mathcal T) \rvert \log \lvert \mathcal{V}(\mathcal T) \rvert )\) for any \(\mathcal T\in\mathcal T^\mathcal Q\), as compared to \(\mathcal O(\lvert E(\mathcal T_\mathcal W)\rvert + \lvert \mathcal{V}(\mathcal T_\mathcal W) \rvert \log \lvert \mathcal{V}(\mathcal T_\mathcal W) \rvert )\) when solving the problem on the finest resolution representation.
While this theoretical result is useful, we also provide timing results obtained by executing our algorithm for various two-dimensional grid sizes in Figure \ref{fig:aveTimeVsCompression}.
Figure \ref{fig:aveTimeVsCompression} shows that, for all the two-dimensional grid sizes shown, there is a range for which our approach provides a computational benefit as compared to running Dijkstra on the finest resolution graph.
Moreover, comparing Figures \ref{fig:aveCostVsCompression} and \ref{fig:aveTimeVsCompression}, we see that for the \(128 \times 128\) grid example considered in Section \ref{sec:numericalExample}, a feasible path can be found (which requires approximately \(15\%\) of the nodes of \(\mathcal N_{\text{leaf}}(\mathcal T_\mathcal W)\) on average) at a lower computational cost than executing a search on the finest resolution.
While this path may not be optimal with respect to an FRP, it is computationally cheaper to obtain, and thus an agent requires, on average, less planning time to have a feasible plan as compared to executing a search on the finest resolution graph.
Additionally, for the \(512 \times 512\) two-dimensional grid, we see a computational cost savings by utilizing abstraction and planning up to a compression level of approximately \(65\%\) when comparing against the time required to obtain a finest resolution path, and that, as the number of vertices in \(\mathcal G(\mathcal T_\mathcal W)\) increases, the range over which there is a computational benefit to employing our approach grows, as evidenced in Figure \ref{fig:aveTimeVsCompression}.
Consequently, we hypothesize that the computational benefits of our approach will only increase as the dimension of the search space grows.
The computational savings come at the cost of a diminished performance as measured by the abstract cost, although this due to the intrinsic need to trade computational complexity and path optimality that we discuss throughout this paper.
Lastly, it is important to view Figure \ref{fig:aveTimeVsCompression} keeping in mind: (i) the results assume the worst-case scenario that the abstractions are not re-used and must be generated from scratch (Q-tree search is initialized at the root node of \(\mathcal T_\mathcal W\)) and are used to produce a single abstract path (\(\text{i.e.,}\) the abstractions are not re-used for multiple plans on the same abstraction) and (ii) the environment is two-dimensional.



Finally, recall that for a given value of \(\beta > 0\), the abstraction returned by Q-tree search will be a tree that retains the maximum amount of information regarding the relevant variable \(Y\) for a given level of compression.
This process is subject to the choice of the relevant variable, which in this paper was taken to be the cell occupancy.
Importantly, our framework holds for other choices of the relevant variable, albeit the average compression level to find the first feasible solution and the compression level for the average path cost to reach \(30\%\) of the FRP cost, as shown in Figure \ref{fig:aveCostVsCompression}, may change.
Investigating the selection of the relevant random variable and its implications is therefore of interest, and is a topic we leave for future work.  


\section{CONCLUSIONS} \label{sec:conclusion}
In this paper, we have shown how a path-planning problem can be systematically simplified through the use of multi-resolution tree abstractions generated by an information-theoretic framework that can be tailored to agent resource limitations.
A number of theoretical results are presented that establish formal connections between the path quality, the graph-search complexity, and the information contained in the reduced graphs.
Our framework provides a principled way to generate abstractions tailored to agent resource constraints, while simultaneously providing guarantees on the monotonic improvement of the path cost as a function of environment resolution.
A non-trivial numerical example is presented to corroborate the theoretical findings and showcase the utility of the approach.
Lastly, we provided a discussion analyzing the interpretation of our framework within the real of bounded-rational decision making and anytime algorithms. 



\bibliographystyle{IEEEtran}

