text:
\section{Introduction}
\label{sec:introduction}
Learning-driven approaches to control, like imitation learning and reinforcement learning, have been quite successful in both training agents to act from raw, high-dimensional input~\citep{mnih2015human} as well as to reach multiple goals by conditioning on them~\citep{andrychowicz2017hindsight, nair2018visual}. However, this success has been limited to short horizon scenarios, and scaling these methods to distant goals remains extremely challenging. On the other hand, classical planning algorithms have enjoyed great success in long-horizon tasks with distant goals by reduction to graph search~\citep{hart1968formal,lavalle1998rapidly}. For instance, A* was successfully used to control \textit{Shakey the robot} for real-world navigation over five decades ago~\citep{doran1966experiments}. Unfortunately, the graph nodes on which these search algorithms operate is abstracted away from raw sensory data via domain-specific priors, and planning over these nodes assumes access to well-defined edges as well as a perfect controller to move between nodes. Hence, these planning methods struggle when applied to agents operating directly from high-dimensional, raw-sensory images~\citep{mishkin2019benchmarking}.

\begin{figure}[t]
    \centering
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[width=1.0\linewidth]{figs/figure_1_a_v4.pdf}
        \caption{Node merging example}
        \label{fig:teaser-a}
    \end{subfigure}\hfill
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[width=1.0\linewidth]{figs/figure_1_b_v4.pdf}
        \caption{Node creation example}
        \label{fig:teaser-b}
    \end{subfigure}
\vspace{-.05in}
\caption{Examples where two-way consistency (TWC) merges nodes (left) and creates a new node (right). Consider a directed graph with three nodes connected as $A \leftrightarrow B \rightarrow C$. Given a new image in the dashed yellow box, should it be merged into an existing node or a new node be created? (a) On the left, we can merge the new image with node A safely. (b) On the right, the new image D contains a bottle which is about to fall off the table edge. While B is perceptually similar to the new image, the agent cannot move the bottle from D to A, but it can move from B to A. As we cannot transition to neighbors in the same manner, our TWC criterion is not satisfied and a new node is created.}
\label{fig:teaser}
\vspace{-0.1in}
\end{figure}

How can we have best of both worlds, \ie{}, combine the long-horizon ability of classic graph-based planning with the flexibility of modern, parametric, learning-driven control? One way is to build a graph out of an agent's experience in the environment by constructing a node for every state and use a learning-based controller (whether RL or imitation) to move between those nodes. Some recent work has investigated this combination in the context of navigation~\citep{savinov_semi-parametric_2018,eysenbach_search_2019}; however, these graphs grow quadratically in terms of edges and quickly become unscalable beyond small mazes~\citep{eysenbach_search_2019}. This strategy either leads to extremely brittle plans because such large graphs contain many errors (infeasible transitions represented by edges), or relies on human demonstrations for bootstrapping~\citep{savinov_semi-parametric_2018}.

In this work, we propose to address challenges in combining the classical and modern paradigms by dynamically sparsifying the graph as the agent collects more experience in the environment to build what we call \textit{Sparse Graphical Memory} (SGM), illustrated in Figure~\ref{fig:overview}. In fact, building a sparse memory of key events has long been argued by neuroscientists to be fundamental to animal cognition. The idea of building cognitive topological maps was first demonstrated in rats by seminal work of~\citep{tolman1948cognitive}. The key aspect that makes building and reasoning over these maps feasible in the ever-changing, dynamic real world is the sparse structure enforced by landmark-based embedding~\citep{foo2005humans,wang2002human,gillner1998navigation}. Yet, in artificial agents, automatic discovery of sparse landmark nodes remains a key challenge.

One way to discover a sparse graph structure is to dynamically merge similar nodes. But how does one obtain a similarity measure? This is a subtle but central piece of the puzzle. States that look similar in the observation space may be far apart in the action space, and vice-versa. Consider the example in Figure~\ref{fig:teaser}, where the graph already contains 3 nodes $\{A,B,C\}$. In~\ref{fig:teaser-a}, similar looking nodes can be merged safely. While in~\ref{fig:teaser-b}, although the new node $D$ is visually similar to $B$, but merging with $B$ would imply that the bottle can be saved from breaking. Therefore, a purely visual comparison of the scenes cannot serve as a viable metric. We propose to use an asymmetric distance function between nodes and employ \textit{two-way consistency} (TWC) as the similarity measure for merging nodes dynamically. The basic idea is that two nodes are similar if they both can be reached with a similar number of steps from all their neighbors as well as if all their neighbors can be reached from both of them with similar effort. For our conceptual example, it is not possible to go back from the falling-bottle to the standing-bottle, and hence the two-way consistency does not align for scene $B$ and the new state. Despite similar visual appearance, they will not be merged. We derive two-way consistency as an extension of prior Q-function based aggregation criteria to goal-conditioned tasks, and we prove that the sparse graphs that result from TWC preserve (up to an error factor that scales linearly with the merging threshold) the quality of the original dense graphs.

We evaluate the success of our method, SGM, in a variety of navigation environments. First, we observe in Table \ref{table:main_result} that SGM has a significantly higher success rate than previous methods, \textit{on average increasing the success rate by 2.1x} across the environments tested. As our ablation experiments demonstrate, SGM's success is due in large part to its sparse structure that enables efficient correction of distance metric errors. In addition, we see that the performance gains of SGM hold across a range of environment difficulties from a simple point maze to complex visual environments like ViZDoom and SafetyGym. Finally, compared to prior methods, planning with our proposed sparse memory can lead to nearly an order of magnitude increase in speed (see Appendix \ref{sec:sgm_speed}).

\section{Related work}
Planning is a classic problem in artificial intelligence. In the context of robotics, RRTs~\citep{lavalle1998rapidly} use sampling to construct a tree for path planning in configuration space, and SLAM jointly localizes the agent and learns a map of the environment for navigation~\citep{durrant2006simultaneous,bailey2006simultaneous}. Given an abstract, graphical representation of an environment, Dijkstra's Algorithm~\citep{dijkstra1959note} generalizes breadth-first search to efficiently find shortest paths in weighted graphs, and the use of a heuristic function to estimate distances, as done in A*~\citep{hart1968formal}, can improve computational efficiency.

Beyond graph-based planning, there are various parametric approaches to planning. Perhaps the most popular planning framework is model predictive control (MPC)~\citep{garcia1989model}. In MPC, a dynamics model, either learned or known, is used to search for paths over future time steps.
To search for paths, planners solve an optimization problem that aims to minimize cost or, equivalently, maximize reward. Many such optimization methods exist, including forward shooting, cross-entropy, collocation, and policy methods~\citep{rubinstein1999cross,hargraves1987direct}.
The resulting agent can either be open-loop and just follow its initial plan,
or it can be closed-loop and replan at each step.

Aside from MPC, a variety of reinforcement learning algorithms, such as policy optimization and Q-learning, learn a policy without an explicit dynamics model~\citep{mnih2013playing,lillicrap2015continuous,schulman2015trust,schulman2017proximal}. In addition to learning a single policy for a fixed goal, some methods aim to learn hierarchical policies to decompose complex tasks~\citep{kaelbling1993learning,pong2018temporal,Schaul:2015:UVF:3045118.3045258}, and other methods aim to learn goal-conditioned policies able to reaching arbitrary goals. Parametric in nature, these model-free approaches are highly flexible, but, as does MPC with a learned dynamics model, they struggle to plan over long time horizons due to accumulation of error.

Recent work combines these graph-based and parametric planning approaches by using past observations for graph nodes and a learned distance metric for graph edges. Variations of this approach include Search on the Replay Buffer~\citep{eysenbach_search_2019}, which makes no attempt to sparsify graph nodes; Semi-Parametric Topological Memory~\citep{savinov_semi-parametric_2018}, which assumes a demonstration to bootstrap the graph; Mapping State Space Using Landmarks for Universal Goal Reaching~\citep{huang2019mapping}, which subsamples the policy's past training observations to choose graph nodes; and Composable Planning with Attributes~\citep{zhang2018composable}, which stores abstracted attributes on each node in the graph. Hallucinative Topological Memory (HTM) \citep{liu2020hallucinative} uses a contrastive energy model to construct more accurate edges, and \citep{shang2019learning} use dynamic programming for planning with a learned graph.

In contrast to the methods listed above, the defining feature of our work is a two-way consistency check to induce sparsity. Previous work either stores the entire replay buffer in a graph, limiting scalability as the graph grows quadratically in the number of nodes, or it subsamples the replay buffer without considering graph structure. Moreover, Neural Topological SLAM \citep{chaplot2020neural} assumes access to a 360\degree camera and a pose sensor whereas we do not. In \citep{chen2019behavioral}, the nodes in the graph are manually specified by humans whereas we automatically abstract nodes from the data. In contrast to our method, the work in \citep{meng2020scaling} has no theoretical guarantees, requires trajectories rather than unordered observations, and uses human demonstrations.

Prior work has proposed MDP state aggregation criteria such as bisimulation metrics that compare the dynamics at pairs of states~\cite{givan2003equivalence, ferns2004metrics} and Utile distiction~\cite{mccallum1993overcoming} that compares value functions. Because bisimulation is a strict criterion \cite{li2006towards} that would not result in meaningful sparsity in the memory, our proposed two-way consistency criteria adapts approximate value function irrelevance \cite{jiang2018notes} to goal-conditioned settings and high-dimensional observations.

\begin{figure}[t]
\begin{center}
\centerline{\includegraphics[width=0.85\textwidth]{figs/figure_3.png}}
\vspace{.05in}
\caption{Execution using a graphical memory. In localization, the agent finds the closest node using discrepancies in the asymmetric distance function. In planning, the agent uses Dijkstra's algorithm to find the shortest path. (For simplicity, this illustration omits the direction of edges.) In path following, the agent may divergence from the waypoints or experience a transition failure. The agent then needs to correct the memory, relocalize, and replan.}
\label{fig:gm_execution}
\vspace{-.3in}
\end{center}
\end{figure}

\section{Preliminaries}
\label{sec:preliminaries}
We consider long-horizon, goal-conditioned tasks. At test time, an agent is provided with its starting state $s_\text{start}$ and a goal state $s_\text{goal}$, and the agent seeks to reach the goal state via a sequential decision making process. Many visual tasks can be defined by a goal state such as an image of a goal location for navigation. Our task is an instance of undiscounted finite-horizon goal-conditioned RL in which the agent receives a -1 living reward until it reaches a given goal.

To reach distant goals, we use a semi-parametric, hierarchical agent that models feasible transitions with a nonparametric graph (\ie{} graphical memory) to guide a parametric low-level controller.

Nodes in the graphical memory are prior states encountered by the agent, connected through a learned distance metric. Once the graphical memory is constructed, the agent can plan using a graph search method such as Dijkstra's algorithm \cite{dijkstra1959note} and execute plans with a low-level controller learned with reinforcement learning or imitation learning \cite{eysenbach_search_2019, savinov_semi-parametric_2018}; see Figure \ref{fig:gm_execution}. Therefore, given a final goal, the high-level planner acts as a policy that provides waypoints, nodes along the shortest path, to the low-level controller, and updates the plan as the low-level agent moves between waypoints:
\begin{align*}
\pi^{hl} \text{ uses } Q^{hl}(s, a=\omega | g) \text{ to select a graph waypoint $\omega$ to reach the final goal $g$}\\
\pi^{ll} \text{ uses } Q^{ll}(s, a | \omega) \text{ to take an environment step $a$ to reach the waypoint $\omega$}.
\end{align*}
As the agent receives an undiscounted -1 living reward, the optimal low-level value function measures the number of steps to reach a waypoint, \ie{} the distance $d(s, \omega) = -\max_a Q^{ll}(s, a | \omega)$.

The main challenge with the above semi-parametric formalism is the detrimental effect of errors in the graphical memory. Since nodes are connected by an approximate metric, the number of errors in the graph grows as $O(\lvert \mathcal{V} \rvert^2)$ where $\lvert \mathcal{V} \rvert$ is the number of graph nodes. Moreover, in order for graphical memory methods to scale to larger environments, it is infeasible to store every state encountered in the graph as done in prior work \cite{eysenbach_search_2019,savinov_semi-parametric_2018}. For the above reasons, node sparsity is a desirable feature for any graphical memory method.  In this work, we seek to answer the following research question: \textit{given a dense graphical memory, what is the optimal algorithm for transforming it into a sparse one?}

\section{Sparse Graphical Memory}
The number of errors in graphical memory can be minimized by removing redundant states, as each state in the memory can introduce several infeasible transitions through its incident edges. Any aggregation algorithm must answer a key question: \textit{when can we aggregate states?}

Sparse Graphical Memory is constructed from a buffer of exploration trajectories by retaining the minimal set of states that fail our \textit{two-way consistency} aggregation criterion. In Sec.~\ref{sec:twc}, we introduce this two-way consistency criterion, which extends prior work to the goal-conditioned RL setting. We then prove that as long as a sparsified graph satisfies two-way consistency, plans in the sparsified graph are close to the optimal plan in the original graph. In Sec.~\ref{sec:alg}, we design an online algorithm for checking two-way consistency by selecting the approximate minimal set from the replay buffer. Finally, in Sec.~\ref{sec:cleanup}, we outline a cleanup procedure for removing remaining infeasible transitions.

\subsection{State aggregation via two-way consistency}
\label{sec:twc}

\begin{wrapfigure}{r}{0.42\textwidth}
\vspace{-.2in}
  \begin{center}
    \includegraphics[width=.42\textwidth]{figs/consistency_twc.pdf}
    \caption{SGM uses a two-way consistency criterion to find redundant pairs of states in the replay buffer.}
    \label{fig:consistency_metrics}
  \end{center}
  %
  \vspace{-.2in}

\end{wrapfigure}

As a state aggregation criterion, prior work argues for value irrelevance by aggregating states with similar Q-functions \cite{mccallum1993overcoming, li2006towards, jiang2018notes}. If the optimal Q-functions are the same at two states, the optimal policy will select the same action at either state.

However, in the goal-conditioned setting, we face a challenge: the states in the memory define the action space of the high-level policy, \ie{} the waypoints selected by the graph planner. Aggregating states changes the action space by removing possible waypoints.

In order to extend value irrelevance to the goal-conditioned setting, we propose two-way consistency (TWC). Under two-way consistency, two states are redundant if they are both interchangeable as goals and interchangeable as starting states according to the goal-conditioned value function.

The graph planner acts as a nonparametric high-level policy, selecting a waypoint $\omega$ for the low-level controller as an intermediate goal. Then, the action space is given by candidate waypoints. Formally, using the optimal value function of the high-level policy, states $s_1$ and $s_2$ are interchangeable as starting states if \begin{equation}
\max_\omega \left|Q^{hl}(s_1, a=\omega | g) - Q^{hl}(s_2, a=\omega | g)\right| \leq \tau_a.
\label{eq:twc:outgoing}
\end{equation}
Then, as $\tau_a \rightarrow 0$, the high-level policy will behave the same in both states. Equation \eqref{eq:twc:outgoing} can be seen as verifying that the sparsification is a $\tau_a$-approximate $Q$-irrelevant abstraction \citep{jiang2018notes} given a fixed set of waypoints as actions. Further, we say that states $s_1$ and $s_2$ are interchangeable as waypoints for the purposes of planning if
\begin{equation}
\max_{s_0} \left|Q^{hl}(s_0, a=s_1 | g) - Q^{hl}(s_0, a=s_2 | g)\right| \leq \tau_a.
\label{eq:twc:incoming}
\end{equation}
As a consequence, eliminating $s_2$ from the memory and thus from the action space will not incur a loss in value at any starting state as the policy can select $s_1$ instead. Together, \eqref{eq:twc:outgoing} and \eqref{eq:twc:incoming} form the two directions of our two-way consistency criterion in the high-level value space.

While we have motivated two-way consistency in terms of $Q^{hl}$ as $\tau_a \rightarrow 0$, it furthermore holds that two-way consistency gives a meaningful error bound for \textit{any asymmetric distance function} $d(\cdot, \cdot)$ satisfying $C_{out}(s_1, s_2) \leq \tau_a$ and $C_{in}(s_1, s_2) \leq \tau_a$ for any finite $\tau_a$ where
\begin{equation}
C_{out}(s_1, s_2) \defeq \max_\omega \left|d(s_1, \omega) - d(s_2, \omega)\right| \text{ and }
C_{in}(s_1, s_2) \defeq \max_{s_0} \left|d(s_0, s_1) - d(s_0, s_2)\right|.
\label{eq:twc:d}
\end{equation}
The following theorem shows that aggregating states according to two-way consistency of $d(\cdot, \cdot)$ incurs a bounded increase in path length that scales linearly with $\tau_a$. Furthermore, given an error bound on the distance function $d(\cdot, \cdot)$, it provides an error bound on distances in the sparsified graph.

\begin{manualtheorem}{1} \label{thm:gap}
Let $\mathcal{G}_\mathcal{B}$ be a graph with all states from a replay buffer $\mathcal{B}$ and weights from a distance function $d(\cdot, \cdot)$. Suppose $\mathcal{G}_{TWC}$ is a graph formed by aggregating nodes in $\mathcal{G}_\mathcal{B}$ according to two-way consistency $C_{out}$ and $C_{in} \leq \tau_\alpha$. For any shortest path $P_{TWC}$ in $G_{TWC}$, consider the corresponding shortest path $P_\mathcal{B}$ in $G_\mathcal{B}$ that connects the same start and goal nodes. Suppose $\mathcal{P}_\mathcal{B}$ has $k$ edges. Then:
\begin{enumerate}[(i)]
    \item The weighted path length of $P_{TWC}$ minus the weighted path length of $P_\mathcal{B}$ is no more than $2k\tau_\alpha$.
    \item Furthermore, if $d(\cdot, \cdot)$ has error at most $\epsilon$, the weighted path length of $P_{TWC}$ is within $k\epsilon + 2k\tau_\alpha$ the true weighted distance along $\mathcal{P}_\mathcal{B}$.
\end{enumerate}
\end{manualtheorem}

Theorem~\ref{thm:gap} is proved in Appendix~\ref{sec:gapproof}.
We emphasize that it makes no assumptions on the distance function, but relies on both directions of our criterion. This distance can be derived from the value function by negation or learned in a supervised manner, depending on the application. According to Theorem~\ref{thm:gap}, we can aggregate pairs of states that satisfy two-way consistency without leading to significantly longer plans (only a constant increase). Since two-way consistency is approximate, at the same time, it also leads to more sparsity than restrictive criteria like bisimilarity.

In contrast to two-way consistency, a na\"ive strategy like random subsampling of the replay buffer does not provide a guarantee without further assumptions on the exploration data such as an even coverage of the state space. For example, when randomly subsampling the buffer, a rarely visited bottleneck state will be dropped with the same probability as states in frequently visited regions. As multiple states can be covered by the same state, two-way consistency is a prioritized sparsification of the replay buffer that seeks to cover the environment regardless of sampling density.

\subsection{Constructing the graph from a replay buffer}
\label{sec:alg}
State aggregation can be seen as an instance of set cover, a classic subset selection problem. In our instantiation, we select a subset of the states in the replay buffer to store in the agent's memory so that all states in the replay buffer are ``covered''. Coverage is determined according to the state aggregation criterion, two-way consistency (\ref{eq:twc:d}). Unfortunately, set cover is a combinatorial optimization problem that is NP-hard to solve exactly, or even to approximate to a constant factor \cite{lund1994hardness,feige1998threshold,raz1997sub}. %

Motivated by the difficulty of the set cover problem, we propose an online, greedy algorithm for replay buffer subset selection. The graphical memory is built via a single pass through a replay buffer of experience according to Algorithm~\ref{alg:build_graph}, which requires quadratically many evaluations of the TWC criterion. In particular, a state is only recorded if it is novel according to the two-way consistency criterion. Once a state is added to the graph, we create incoming and outgoing edges, and set the edge weight to the distance.

\begin{algorithm}[t]
  \caption{\texttt{BuildSparseGraph}}
  \label{alg:build_graph}
\begin{algorithmic}[1]
   \STATE {\bfseries Input:} replay buffer $\mathcal{B}$, distance function $d$
   \STATE {\bfseries Output:} sparse graph $\mathcal{G} = (\mathcal{V}, \mathcal{E}, \mathcal{W})$
   \STATE Initialize empty vertex set $\mathcal{V} = \emptyset$
   \FOR{$\hat{s} \in \mathcal{B}$, each state in the replay buffer,}
   \IF{state is novel according to TWC, \ie{} $C_{in}(s, \hat{s}) \leq \tau_a, C_{out}(s, \hat{s}) \leq \tau_a ~\forall s \in \mathcal{V}$}
   \STATE add the state $\hat{s}$ to the graph $\mathcal{G}$:
  \STATE $\mathcal{V} = \mathcal{V} \cup \{\hat{s}\}$
  \STATE $\mathcal{E} = \mathcal{E} \cup \{(s, \hat{s}) : s \in \mathcal{V}, d(s, \hat{s}) \leq \textsc{\small MaxDist}\} \cup \{(\hat{s}, s) : s \in \mathcal{V}, d(\hat{s}, s) \leq \textsc{\small MaxDist}\}$
   \ENDIF
   \ENDFOR
   \STATE assign weights $\mathcal{W}(s_i, s_j) = d(s_i, s_j) ~~\forall (s_i, s_j) \in \mathcal{E}$
   \STATE filter transition set $\mathcal{E}$ to $k$ nearest neighbors
   \STATE {\bfseries return} $\mathcal{G} = (\mathcal{V}, \mathcal{E}, \mathcal{W})$
\end{algorithmic}
\end{algorithm}

\subsection{Graphical memory cleanup}
\label{sec:cleanup}
Although TWC produces a compact graph with substantially fewer errors than the original graphical memory, faulty edges may still remain. If even one infeasible transition between distant states remains as an edge in the graph, the planner will exploit it, and the agent will not be able to carry out the plan~\cite{eysenbach_search_2019}. Therefore, eliminating faulty edges is key for robustness.

We bound the number of errors in the memory by filtering edges, limiting nodes to their $k$ nearest successors.
After filtration, the worst-case number of untraversable edges grows only \textit{linearly} in the sparsified node count, not quadratically. This is a simple, inexpensive procedure that we experimentally found removes many of the infeasible transitions.

Finally, we propose a novel self-supervised error removal technique -- \textit{cleanup}. During test-time execution, a random goal $g$ is sampled and the planner provides a set of waypoints $w$ for the low-level agent. When the low-level agent is unable to reach a consecutive waypoint $w_i \rightarrow w_{i+1}$, it removes the edge between $(w_i,w_{i+1})$ and re-plans its trajectory. This procedure is efficient for a TWC sparsified graph since $|\mathcal{G_{TWC}}| \ll |\mathcal{G}_{\mathcal B}|$.

\section{Experimental Setup}
\label{sec:implementation}

We evaluate SGM under two high-level learning frameworks: reinforcement learning (RL), and self-supervised learning (SSL). As a general data structure, SGM can be paired with any learned image features, asymmetric distance metric, or low-level controller. Below, we describe our training procedure in detail.

\begin{figure}[t]
\vspace{-.1in}
\begin{center}
\centerline{\includegraphics[width=\textwidth]{figs/horizontal_sgm_envs.png}}
\vspace{-.2in}
\caption{The three environments used for testing SGM. PointEnv is a small maze with coordinate observations. We increase its difficulty by thinning the walls. ViZDoom is a large environment, which can take up to 5 minutes and 5k steps to traverse entirely. ViZDoom actions are discrete and observations are first-person camera views. SafetyGym is another large environment with first-person view observations, and supports continuous actions.}
\label{fig:envs}
\vspace{-.2in}
\end{center}
\end{figure}

We benchmark against the two available environments used by the SoRB and SPTM baselines, and an additional visual navigation environment. These range in complexity and are shown in Figure~\ref{fig:envs}. The environment descriptions are as follows: \textbf{PointEnv}\cite{eysenbach_search_2019} continuous control of a point-mass in a maze used in SoRB. Observations and goals are positional $(x,y)$ coordinates. \textbf{ViZDoom}\cite{wydmuch2018vizdoom} discrete control of an agent in a visual maze environment used in SPTM. Observations and goals are images. \textbf{SafetyGym}\cite{safetygym} continuous control of an agent in a visual maze environment. Observations and goals are images, though odometry data is available for observations but not for goals.

We utilize the PointEnv maze for RL experiments, where SGM is constructed using undiscounted Q-functions with a sparse reward of $0$ (goal-reached) and $-1$ (goal not reached). We increase the difficulty of this environment by thinning the walls in the maze, which exposes errors in the distance metric since two nearby coordinates may be on either side of a maze wall. SoRB also ran visual experiments on the SUNCG houses data set \citep{song2017semantic}, but these environments are no longer public.

\begin{table}[t]
\begin{center}
\begin{small}
\begin{sc}
\begin{tabular}{lcccc}
\toprule
Technique              & Success Rate & Cleanup Steps & Observation &  Env  \\ \midrule
SoRB         & 28.0 $\pm$ 6.3\%   & 400k   & Proprio & PointEnv      \\
SoRB + SGM      &\textbf{100.0 $\pm$ .1}\% & 400k   & Proprio   & PointEnv      \\ \midrule
SPTM              & 39.3 $\pm$ 4.0\% & -  & Visual    & ViZDoom      \\
SPTM + SGM            & \textbf{60.7 $\pm$ 4.0\%}   & 114k & Visual & ViZDoom      \\ \midrule
ConSPTM     & 68.2 $\pm$ 4.1\%   &1M   & Visual &  SafetyGym      \\
ConSPTM + SGM    &  \textbf{ 92.9 $\pm$ 1.4}\%  &1M    & Visual &SafetyGym      \\ \bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\caption{SGM boosts performance of all existing state-of-the-art semi-parametric graphical methods.}
\vspace{-0.2in}
\label{table:main_result}
\end{table}

To evaluate SGM in image-based environments, we use the ViZDoom navigation environment and pretrained networks from SPTM. In addition, we evaluate navigation in the OpenAI SafetyGym \citep{Ray2019}. In both environments, the graph is constructed over \textit{visual first-person view observations} in a large space with obstacles, reused textures, and walls. Such observations pose a real challenge for learning distance metrics, since they are both high-dimensional and perceptually aliased: there are many visually similar images that are temporally far apart. We also implemented state-of-the-art RL algorithms without the graphical planner, such as DDPG \cite{lillicrap2015continuous} and SAC \cite{haarnoja2018soft} with Hindsight Experience Replay \cite{andrychowicz2017hindsight}, but found that these methods achieved near-zero percent success rates on all three environments, and were only able to reach nearby goals. For this reason, we did not include these baselines in our figures.

\section{Results}
\label{sec:experiments}
\paragraph{SGM increases robustness of plans:} We compare how SGM performs relative to prior neural topological methods in Table \ref{table:main_result}. \textbf{SGM sets a new state-of-the-art in terms of success rate} on all three environments tested and, on average, \textbf{outperforms prior methods by 2.1x}. In fact, thinning the walls in the PointEnv maze \textit{breaks the policy from the SoRB baseline} because it introduces faulty edges through the walls. SoRB is not robust to these faulty edges and achieves a 28\% score even after 400k steps of self-supervised cleanup. SGM, on the other hand, is able to remove faulty edges by merging according to two-way consistency and performing cleanup, robustly achieving a 100\% success rate. Similarly, in visual environments, the sparse graph induced by SGM produces significantly more robust plans than the SPTM baselines. While SGM solves the SafetyGym environment with a 96.6\% success rate, it navigates to only 60.7\% of goals in ViZDoom. Note that this VizDoom success rate is lower than in \cite{savinov_semi-parametric_2018} because \cite{savinov_semi-parametric_2018} uses human demonstrations whereas we do not. We found that the primary source of error in VizDoom was due to perceptual aliasing where two perceptually similar observations are actually far apart. For further details, see Appendix \ref{appendix:perceptual_aliasing}.

\begin{table}
\begin{center}
\begin{small}
\begin{sc}
\begin{tabular}{lcccc}
\toprule
\multirow{2}{*}{Technique}  & Easy & Medium & Hard & \multirow{2}{*}{Overall} \\
                    & {\small $\leq200$ m} & {\small $\leq400$ m} & {\small $\leq600$ m} & \\ \midrule
Random actions         & 58.0\%             & 21.5\%               & 12.0\% & 30.5\%            \\
Visual controller      & 75.0\%             & 34.5\%               & 18.5\% & 42.7\%            \\
SPTM, subsampled observations       & 70.0\%          &                 34.0\%     &    14.0\%       & 39.3\%         \\
SPTM + SGM + 54\textsc{K} cleanup steps    & 88.0\%    & 52.0\%      & \textbf{26.0\%}           & 55.3\%  \\
SPTM + SGM + 114\textsc{K} cleanup steps    & \textbf{92.0\%}    & \textbf{64.0\%}      & \textbf{26.0\%}      & \textbf{60.7\%}       \\ \bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\caption{SGM improves graph-based success rates across goal difficulties in ViZDoom. More cleanup steps yield better performance because more infeasible transitions are removed from the graph.}
\label{table:vizdoom_success}
\vspace{-0.24in}
\end{table}

\begin{wrapfigure}[26]{r}{0.5\textwidth}
    \vspace{-0.1in}
    \begin{center}
        \includegraphics[width=\linewidth]{figs/cleanupplots.png}
    \vspace{-.28in}
    \caption{Success rate as a function of cleanup steps in PointEnv (FourRooms maze) and SafetyGym. SGM is rapidly corrected while SoRB, because of errors in its dense graph, is infeasible to clean. SPTM can be cleaned, but only slowly.}
    \label{fig:cleanup_plot}
    %
    \vspace{.2in}
    %
    %
    %
    \begin{sc}
    \setlength{\tabcolsep}{4pt}
    \begin{tabular}{lcc}
    \toprule
    Criterion & w/o Cleanup & w/ Cleanup  \\
    \midrule
    uniform         & 31.2 $\pm$ 3.8\% & 64.6  $\pm$ 3.4\%  \\
    perceptual      & 31.8  $\pm$ 3.6\% & 77.0  $\pm$ 2.5\% \\
    incoming        & 33.6  $\pm$ 3.1\%    & 84.1  $\pm$ 2.0\%    \\
    outgoing        & 28.7 $\pm$ 3.2\%  & 86.8  $\pm$ 2.9\%     \\
    \midrule
    two way     & \textbf{38.2  $\pm$ 3.8\%} & \textbf{92.9 $\pm$ 1.2\%}   \\
    \bottomrule
    \end{tabular}
    \end{sc}
    \end{center}
    %
    \vspace{-.1in}
    \captionof{table}{Comparing node subsampling strategies in SafetyGym. Two-way consistency improves success rate relative to other criteria.}
    \label{table:twc_ablation}
    \vspace{0.05in}
\end{wrapfigure}

We examine SGM performance with and without cleanup. Figure~\ref{fig:cleanup_plot} shows that success rapidly increases as the sparse graph is corrected. However, without sparsity, the number of errors is too large to quickly correct.
Success rates in Table~\ref{table:twc_ablation} show that \textbf{sparsity-enabled cleanup is essential for robust planning} and that \textbf{cleanup improves mean performance by 2.4x}.

We also study success as a function of goal difficulty in Table~\ref{table:vizdoom_success}, where difficulty is determined by the ground-truth distance between the initial agent's position and its goal. Even with cleanup, performance degrades with goal difficulty, which is likely the result of perceptual aliasing causing faulty edges (Appendix \ref{appendix:perceptual_aliasing}).

\paragraph{Two-way consistency is the preferred subsampling strategy:} We ablate different subsampling strategies to examine the source of our performance gains. We compare SGM with two-way consistency with variants of SGM with one-way consistency, where connectivity between two nodes is determined by only checking either incoming or outgoing distance function values, as well as a simple random subsampling strategy where a subset of nodes and edges are uniformly removed from the dense graph.
Table~\ref{table:twc_ablation} shows success rates for a SafetyGym navigation task before cleanup and after 1M steps of cleanup. Before cleanup, all plans perform poorly with a maximum 38.2\% success rate achieved by two-way SGM. After cleanup the SGM variants significantly outperform a naive uniform subsampling strategy, and subsampling with two-way consistency achieves the highest success rate before and after cleanup.

\begin{figure}[t]
    \centering
    \begin{subfigure}[t]{0.5\textwidth}
        \centering
        \includegraphics[width=1.0\linewidth]{figs/vizdoom_left_plot.png}
    \end{subfigure}
    \quad
    \begin{subfigure}[t]{0.4\textwidth}
        \centering
        \includegraphics[width=1.0\linewidth]{figs/vizdoom_right_plot.png}
    \end{subfigure}
\caption{(Left) Overlayed histograms of edge lengths for graphical memories in ViZDoom, where long edges are incorrect. Graph quality significantly improves with SGM, which reduces the frequency of long edges. (Right) SGM reaches goals using the fewest environment steps (shortest path length).}
\label{fig:vizdoom_2_plots}
\vspace{-0.1in}
\end{figure}

\paragraph{Investigation of two-way consistent graph quality:} We further investigate how individual components of two-way consistent SGM affect final graph and plan quality. In Figure~\ref{fig:vizdoom_2_plots} (left), we display the total edge count for various edge lengths in the ViZDoom graphical memory after different steps of the SGM algorithm. Since nodes should only be connected locally, long edges are most likely to be faulty, representing infeasible transitions. Although the different components of the SGM algorithm all help reduce errors, \textbf{two-way consistency removes the most incorrect edges} from the original dense graph while preserving the most correct edges.

Finally, in Figure \ref{fig:vizdoom_2_plots} (right) we display the average number of steps required for different agents to reach their goal in ViZDoom. The average is only taken over successful paths, and the dotted line shows the maximum number of steps allowed. We show that, on average, agents equipped with sparse graphical memory take the fewest steps to reach their goals compared to other methods. This suggests that shorter paths are another reason for improved success relative to other methods.

\section{Conclusion}
\label{sec:discussion}
In this work, we proposed a new data structure: an efficient, sparse graphical memory that allows an agent to consolidate many environment states, model its capability to traverse between states, and correct errors. In a range of difficult visual and coordinate-based navigation environments, we demonstrate significantly higher success rates, shorter rollouts, and faster execution over dense graph baselines and learned controllers. We showed that our novel two-way consistency aggregation criterion is critical to this success, both theoretically and empirically. We hope that this direction of combining classic search-based planning with modern learning techniques will enable efficient approaches to long-horizon sensorimotor control tasks. In particular, we see scaling sparse graphical memory to challenging manipulation tasks as a key outstanding challenge for future work.

\section*{Broader impact}
\textbf{Interpretability} ~~To build trust in deep RL systems, users would, ideally, be able to interrogate the system: ``What is the deep RL system going to do? Why?'' With state-of-the-art model-free approaches such as proximal policy optimization \citep{schulman2017proximal}, it is not possible to answer these questions -- the policy network is a black box. The explicit graphical plans produced by SGM, in contrast, can provide a partial answer to these questions. The future nodes in a plan given by SGM indicate what it is attempting to do, and errors in an overall plan can be debugged by tracing them to individual faulty edges in the graph. For this reason, we see graphical planning methods such as SGM as advantageous for the trust and interpretability of deep RL systems relative to model-free methods.

\textbf{Safety} ~~SGM assumes that the agent's only reward signal is an indication of whether or not the current state satisfies the goal. This problem formulation ignores potential damage that could be caused during the intermediate steps taken to reach the goal, which, depending on the application, could be significant. Designing an RL agent that can safely explore and reach goals in its environment is a fundamental challenge for the entire field.

\textbf{Real-world applications} ~~While methods for long-horizon RL are highly general, such as the method we present in this paper, the most immediate potential applications of our method are in robotics. Completely solving the problem formulation in this paper, long-horizon control from high-dimensional input with sparse reward, would have wide-sweeping impact across robotic applications. %

\section*{Acknowledgments}
This work was supported in part by Berkeley Deep Drive (BDD), ONR PECASE N000141612723, Open Philanthropy Foundation, NSF CISE Expeditions Award CCF-1730628, DARPA through the LwLL program, the DOE CSGF under grant number DE-SC0020347, the NSF GRFP under grant number DGE-1752814, and Komatsu. DP is supported by Google FRA.

\bibliographystyle{abbrvnat}

redpajama_set_name: RedPajamaArXiv


text:
Provider/Privacy Statement
Opening hours and prices
Today at the Museum
Schools and day care centres
Activities for families and kids
Museum & Exhibition
Gottlieb Daimler Memorial
Gottlieb Daimler Birth Place
Special exhibition: G-Class
Events & Gastronomy
Host Events
Cannstatter Hütte
Mercedes-Benz Concert Summer
To Mercedes-Benz Classic
Daimler single cylinder engine, the Grandfather Clock.
Legend 1.
Daimler single cylinder engine, the Grandfather Clock
Daimler's Grandfather Clock was the world's first small high-speed internal combustion engine to run on gasoline. It was light and yet powerful enough to drive a vehicle. The engine was given its epithet because it resembled a grandfather clock. A patent was filed for it in 1885. The unit shown here corresponds to the most powerful version from 1886.
Displacement 28 cu in
Output 1.1 PS (0.8 kW)
At engine speed 650/min
Discovery tours in the Mercedes-Benz Museum.
Discover the Mercedes-Benz Museum in just 45 minutes with our discovery tours.
The congenial problem solver.
The Mercedes-Benz Unimog rescues people, transports loads, even travels on rails and can do much more.
Special exhibition: 40 years G-Class.
From 18 October 2019 to 19 April 2020 the special exhibition "40 years G-Class" takes place.
Shmee150 exploring Mercedes-Benz.
YouTuber Shmee explores various interesting stations at Mercedes-Benz and Mercedes-AMG.
Which classic car fits to you?
Youngtimer or classic car, saloon or cabriolet? Find out which vehicle suits you best with the Mercedes-Ben...
"H" number plate in 2020.
Five Mercedes-Benz classic cars are eligible for the "H" historical number plate in 2020.
Mercedes-Benz Museum Stuttgart – 130 years of history.
The Mercedes-Benz Museum is the only museum in the world that can document in a single continuous timeline ...
Mercedes-Benz Museum: Opening hours, prices and address.
Visitor information Mercedes-Benz Museum.
Guided tours.
Discover the Mercedes-Benz Museum together with our guides.
Mercedes-Benz Classic: Classics, festivals and milestones.
Mercedes-Benz Classic: Experience milestones and enjoy emotional insights into the history of the inventor ...
Corporate history.
The name "Mercedes-Benz" is considered as embodiment of tradition and innovation all over the world.
Product may vary after press date on 26.01.2015.
Mercedes-Benz Museum.
The Mercedes-Benz Museum is the only museum in the world that can document in a single continuous timeline over 130 years of auto industry history from its very beginnings to the present day. On nine levels and covering a floor space of 16,500 square metres, the museum presents 160 vehicles and over 1,500 exhibits.
Opening hours.
Tuesdays to Sundays 9 a.m. to 6 p.m.
Box office closing time: 5.00 pm
Closed on Mondays and selected public holidays.
Visitor information.
Prices, opening hours and address
Follow the Mercedes-Benz Museum
Museum & History
Formula 1 Store
Mercedes-Benz Ex-Factory Driving Aids
To keep you in the loop of our latest news, register now for our email newsletter.
I have read the privacy policy and agree.
Follow us and use the following social media platforms to get in contact with us and to share your passion for the brand, products and services of Mercedes-Benz.
This is the International website of Mercedes-Benz AG. Visitors from the U.S., please visit our U.S. website www.mbusa.com.
Opening hours & Price
Buy your ticket online

redpajama_set_name: RedPajamaCommonCrawl


The first quarter sales started slowly in Avon with average prices declining early in the first quarter before heading back up. Inventory was also down from last year. This perfect combination made for a good first half of the year for home sales in Avon. Many homes had multiple offers in the last few months. The bank owned inventory is down and prices have leveled for the past few months with inventory remaining lower than last year.
If you would like to know what's going on in your neighborhood, let us know and we'll get right back with you.


Communication networks vary greatly from site to site and often change as technology advances. Converters and gateways provide a bridge between different protocols and standards that exist in the industrial automation field. Modbus gateways convert Ethernet Modbus TCP to/from serial Modbus RTU/ASCII.


The top 7 tips that you can use to master sales enablement in your organization.
The Definition and fundumentals of Sales Enablement.
An explanation of why Sales Enablement has become a must have buisness process in modern business.


text:
Chiefs Sign Tyreek Hill to Contract Extension
The Kansas City Chiefs announced on Friday that the team has signed wide receiver Tyreek Hill to a contract extension.
"We're pleased we were able to reach an agreement with Tyreek to keep him in a Chiefs uniform for the foreseeable future," Chiefs General Manager Brett Veach said. "He understands our expectations of him as a member of this team and community. This extension is contingent upon the conditions Tyreek agreed to adhere to upon his return to the team in July. Tyreek is an elite player in this league and has played a major role in our team's success, and we're pleased that he'll continue to make an impact for us."
"I'm grateful for the opportunity to continue my playing career here in Kansas City," Chiefs wide receiver Tyreek Hill said. "Kansas City is my home, and I appreciate the love and support from Clark Hunt, Coach Reid and Brett Veach along with my coaches and teammates. To Chiefs Kingdom, you're the best fans in the world."
Hill (5-10, 185) has played in 47 games (30 starts) in three NFL seasons with the Kansas City Chiefs (2016-18). He's tallied 223 catches for 3,255 yards (14.6 avg.) with 25 receiving TDs. Since 2016, he owns a league-best 44 receptions of 25 yards or more. Hill has rushed 63 times for 477 yards (7.6 avg.) with four touchdowns. His career returns stats include 84 punt returns for 1,009 yards (12.0 avg.) with four TDs along with 14 kickoff returns for 384 yards (27.4 avg.) and one touchdown.
The Pearson, Georgia, native, has been named to the Pro Bowl in all three of his NFL seasons. Hill originally joined the Chiefs as the first of two fifth-round draft picks (165th overall) in the 2016 NFL Draft. He played collegiately at West Alabama.


text:
HomeSword Detective HayateSword Detective Hayate – Chapter 3: Enter The Chinese Demon Hunter
Sword Detective Hayate – Chapter 3: Enter The Chinese Demon Hunter
It had been a week since then. Chiaki had learned many things from the Kanzaki family. There existed demons that preyed on humans and other living things. Demon Hunters were those who hunted down demons. There were forty-seven Demon Hunter families, each responsible for one of the forty-seven prefectures of Japan. Those belonging to much smaller families or had the ability to be Demon Hunters were treated as hired hands. The Demon Hunters as a whole are supported by an organization known as the Demon Hunter Cooperative Association, or DHCA.
The DHCA was a large secret government organization that included both those with Demon Hunter talents and those without. Its main purpose was supporting the Demon Hunter families. This covered various things: be it in the way of handling disposal of slain demons; to logistics and information handling; serving as intermediaries for Demon Hunters families to communicate to one another; and most importantly, bypassing particular laws, like the Gun and Sword Control Law.
She was told this as she had been placed under the protection of the Kanzaki family. Due to the unknown reason of why she had been attacked. Several measures of protection had been given to her and her home. On her arm, was a fashionable bracelet that doubled as a protective charm, it was designed to ward off demons. Acting similarly to like a demon repellent. Although, from what she had been told, Hayate who attended the same school now, would have already served as a prevention from attacks.
The reason for that was that Demon Hunters had a power called Spiritual Power. This power was a special power passed down through bloodlines or through special individuals. Demons often didn't approach locations with Demon Hunters due to this power. It also offered a number of benefits. One such benefit was increased physical abilities, but the kinds varied depending on individual. Another was being generally immune to common diseases. Another possible benefit was gaining some kind of ability. Like the doctor that examined her, with the ability to heal through Spiritual Power.
Chiaki had asked if Spiritual Power affected appearances, commenting on how Hayate looked. The Kanzaki family took a "No Comment," stance and didn't answer her question.
◊ ◊ ◊ ◊ ◊
For a week now, she still had not gotten over one particular fact. The girl, Hayate who was sitting next to her was really a boy. Thanks to a weird power that allowed the ability to change genders at will. But it was this same power that kept the boy trapped in a girl's body for most of the time. The power also had a weird and very random timing issue to the point it was almost convenient. From what she was told, the power would nonchalantly change Hayate back to the original gender for a short time or unexpectedly. And then change back to being a girl right after, for how long or how often couldn't be predicted. No matter how hard Hayate tried, she had no control over it. Half of Hayate's life was already spent as a girl.
It was already late afternoon as the two were spending time in Hayate's house. It was a two story house that had a direct path to their school. The two were using the time to converse as well as do homework. Mostly Hayate tutoring Chiaki on her weaker subjects. For a week, the two had spent time after school, one for Chiaki's protection, and the other was for the two of them to deepen their friendship. Although it had been a bit awkward at first.
"You know, Hayate. Every time we talk. You don't seem like a boy."
"…I know…Please do not say it."
Hayate had developed a complex about it. It wasn't sure if Hayate's gender changing power was the cause or something else. The person would act with natural subtle mannerisms of the current gender. Particularly the expressions. The girl Hayate would often express her emotions clearly for all to see. Despite trying very hard to wear a "mask" of a calm appearance.
It was easy for Chiaki to forget that the person next to her was supposed to be a boy. Often she would bring it up, and Hayate would try to shut it down quickly. It allowed her to give some payback for the bath incident from before.
Though their relationship was developing well as friends. Hayate would innocently ask about particular things that usually were taken for granted. Chiaki would ask about various things about Hayate's life, and sometimes background. This exchange often had no end of subjects as something new would be found. Sometimes the two would talk so much that they lose track of time.
"Hayate-sama."
A woman's voice was heard suddenly as if waiting for an opportunity. Hayate turned her attention to the voice.
"What is it, Fuumi?"
The woman, Fuumi Kirishima was already standing behind Hayate, giving an apologetic bow.
"It's time for Chiaki-sama to return home."
"Oh, the time is this late already…"
The clock in the living room where they had been studying showed it was half an hour away from 7 PM. Disappointed their conversation was ended abruptly, Chiaki packed her things.
"I will walk you home, Chiaki-san."
"There you go with the '-san' again. I told you not to use it, Hayate."
"B-But, it is a bit embarrassing…"
"We're both girls, it's fine. Also you're using it so naturally with Fuumi-san."
"B-But…she is my childhood friend."
"I'm your friend too, Hayate."
"Mmmm….I will….try harder."
For the past week, this was a common conversation between the two. Leaving it as is, the two plus one left Hayate's house. Although the distance between their houses was about twenty minutes by foot. Just like previous times, it was an uneventful walk. The pair plus one often just talked about unimportant things. Today though, Chiaki broached a subject she had been curious about.
"Say, Hayate. I know you're a private detective. But is it really that great? I mean the work I hear you're getting isn't anything special right?"
"I did want to have some kind of grand mystery to solve. Although I do know that is merely a whim of fiction writing. I understand the nuances of the job itself and how lackluster it could be. However, this is an occupation I chose for myself. It also allows me to help those in need more easily."
"Hmmm…so, have you had any strange cases?"
"Mmmm…..I cannot think of one currently. Nothing particularly strange from the cases so far. All the ones I have gotten were either crime scene investigation requests from the police. Or the occasional referral case. Like a cheating husband investigation or finding a missing cat."
"Those really sound ordinary."
"Hayate-sama, we've arrived."
Fuumi's voice chimed in again with perfect timing. They had reached Chiaki's house. After bidding her goodbye, and watching Chiaki enter the house safely. The two left quietly. Hayate's expression darkened as she quickened her pace.
"Call for transportation. We are going on a hunt. They are here again."
"Hayate-sama…you can't be."
"Have the others come and form the perimeter. I will hunt alone."
"Yes, Hayate-sama…"
Inside an artificial forest that was located a distance away, a lone boy moved quickly with a Demon slightly larger than him giving chase. There were many others identical to it also following. The boy clicked his tongue as he had not expected this many.
These demons set a trap?! Without my Arataka, I cannot fight as well. He thought in frustration as the odds were against him. He had not expected a trap like this. His original katana, Arataka, was being maintained again. Yesterday's hunt was similar with a large number of demons. But using Arataka had taken a toll from the constant use over the past week.
This had forced him to use his backup katana, its quality was inferior to his Arataka but it had to do. It had served him well before, but he doubted it would last against the number of demons he was facing now. And these were more intelligent than the ones he had already hunted before. These demons could coordinate and move like a large unit. If he moved carelessly or let his guard down, it wouldn't end well.
What do I do? Hit and run? But this katana might not last with this number. And I cannot leave them alone. His mind tried to think of a solution. He was honestly glad Fuumi and the rest of the men who guarded him were not here. He didn't want to think about what would happen to them if they had followed.
"Shǎnshēn!" (Dodge!)
Hearing a girl's voice from somewhere, he quickly slid behind a tree as a violent wind blew all around. The demons that had been chasing him were now blown away. Recovering quickly, the demons looked for source of the unexpected wind.
"Japan Demon Hunter. Yu Xiuying is here to offer her sword."
A girl in a cheongsam appeared before Hayate. Her long dark crimson hair was tied into a single braid. She held a jian, a double-edged straight sword, in her right hand. A Taoist style talisman had burned up in her other hand. She kept her eye on the demons.
Before he could introduce himself he drew his katana. He glared at the demons as they reformed quickly and moved towards the two. He motioned his body quietly into a ready stance. Shifting his body sidewise, he lowered both arms. His katana was hidden away from view behind his body.
He gave a confident glance at Xiuying. She looked at him with a surprise, only smiling in response. She also got into a ready stance, her feet spread out slightly. Her jian was now flipped in her hand in a reverse grip. The blade rested along her arm. Her free arm was relaxed.
Looking at Hayate again, she gave a confident smirk.
"Wǒmen zǒu ba!" (Let's go!)
He took a step forward and disappeared from the spot. He reappeared once again in the air behind the demons as he landed. Several demon heads were already separated from their bodies. The demons turned to look at the him. Leaving them open to a smiling Xiuying who attacked the closest one. Quickly exchanging her jian between her hands. Then with a thrust she stabbed the blade into the back of the knee of one demon. Collapsing due to that injury, it was left open to the blade that reaped its life with the next strike. Without waiting, she went after her next target. Hayate appeared behind her back, stabbing his katana into the head of a demon that had turned towards her. Pulling out his katana, his back was towards Xiuying.
"Xièxiè." (Thank you.)
With a pair of smiles, the two fought together. Protecting the other's back. Their coordination was in sync with one another. Even though this was their first time. The demons were reduced steadily. The two's coordination overcame the disadvantageous odds.
In five minutes, there were no more demons. Hayate still wary of another attack used his senses to check the surroundings until he realized the cold oppressive air was already gone. Sighing in relief as he sheathed his katana. Xiuying did the same as she sheathed her jian. The two looked at one another, but it was Hayate who bowed first.
"I thank you for the help. I do not know what would have happened if I was still alone."
"Do not mind. I was looking for you. You are the one called Hayate Kanzaki, right?"
"…Yes…that is my name. Why were you looking for me?"
"To challenge you to a duel!"
He couldn't process the line of thought that lead to that.
"Why do you wish for a duel?"
"I heard rumours about a Demon Hunter who is very active compared to the rest. Not only that, he is of my age. I came looking for you."
She calmly said with a smile on her face. Then she looked like she realized something and started staring at him.
"Oooh…your Spiritual Power is….very, very big as expected."
He did know that he had a large capacity for Spiritual Power. His control, on the other hand, was not that good yet. Like just now, he leaked Spiritual Power that others could sense. What she had said to him that made him worry.
"As…expected?"
"Yes, I hear that you possess largest amount known to Japan Demon Hunters."
How does that get measured? This is the first time I was told this. His thoughts were thinking about an irrelevant matter. He quietly shook his head and tried to get back on the main topic.
"There should be other Demon Hunters active right now. I cannot be the only one."
"That is true, but only you are truly active. This last week, I hear you hunt down many demons. Other Demon Hunters, I heard don't hunt as often as you. Or lack activity."
"That…is true…there has been a large amount here."
What is going on? If the activity is focused here. Is this some kind of special occurrence? Are the demons up to something? Or are they looking for something….or someone… He mentally tried to find a pattern, but he came up short. Lack of clues and understanding of the situation. He thought about the past number of weeks. He had taken over the hunting duties that were his mother's just about six months ago. There was a slight lack of activity for first five months. Then slowly a month ago it increased. Then in the last two weeks, the activity increased greatly. And in the last week alone, he had spent almost every night hunting Demons.
Could something big be happening soon? Or am I missing a key clue in this? He mused for a moment that maybe the activity was meant for something else. But this was not in line with the normal behaviors of demons. He was really lost for the moment. He quickly shook his head again in disappointment.
"There is no use dwelling on that. I must thank you again for the help. I must ask, what point is there to the duel?"
"There is a point. When I win, you will marry me."
Sword Detective Hayate - Chapter 2: Bath And Surprise
Sword Detective Hayate - Chapter 4: Duel
Tags:original, Sword Detective Hayate
Sword Detective Hayate – School Life Stories 1: Hayate Gets Love Letters
Sword Detective Hayate – Chapter 14: Ojou-sama and Soul Sister
Sword Detective Hayate – Chapter 13: A Cold
Sleepy_Kanzaki-kun
Name's Sleepy_Kanzaki-kun or people just call me Kanzaki. I'm a new writer that joined RTD and glad to be a part of the group. I hope you enjoy the story as it progresses.