Learning Composable Behavior Embeddings for Long-horizon
Visual Navigation

We consider a goal-directed navigation task where a robot needs to navigate from its current location $s$ to a goal $g$. We assume that a demonstration containing a sequence of RGB observations $o_{1},o_{2},...,o_{T}$ connecting $s$ and $g$ is given to the robot. Since the trajectory can be long and complex, intermediate information needs to be memorized to help the robot follow the demonstration [12, 17, 11].

Similar to [35], our navigation system guides the robot by generating relative waypoints that are used by a low-level controller to compute motor commands (e.g., velocity and steering angle). To follow a demonstrated trajectory, the robot could use visual control to match its observations against the sequence of demonstrated observations as in [17, 11, 12]. However, such an approach is highly memory inefficient, since it requires rather densely stored images. To overcome this problem, CBE encodes the sequence of visual observations $o_{1},o_{2},...,o_{T}$ into a low-dimensional behavior embedding $z_{D}$ (Figure 1). During execution, at each time step, a waypoint generator uses $z_{D}$ and the current observation to produce a waypoint for the low-level controller. Both state and action space are continuous, and the system operates in a closed-loop fashion to correct any drift due to noise and non-holonomic kinematic constraints. Different demonstrations and their executions can be of different lengths.

For very long and complex trajectories, a single $z$ is insufficient due to compounding errors. To address this problem, we segment long trajectories into sequences of embeddings, interleaved by visual attractors for state calibration. The segmented behaviors are used for solving downstream navigation tasks, which we detail in Sec V.

The behavior encoder $\mathbb{B}_{\text{enc}}$ (left half of Figure 2) maps observation streams $o_{1},o_{2},o_{3},...,o_{T}$ into a low-dimensional embedding $z_{D}=\mathbb{B}_{\text{enc}}(o_{1},o_{2},...,o_{T})$. To do so, each pair of adjacent images is input to a CNN that generates a feature vector fed into an LSTM to compute the embedding for each time step. Since the encoder is recurrent, it outputs a sequence of embeddings, where embedding $z_{i}$ encodes the observed behavior from $o_{1}$ to $o_{i+1}$. The complete trajectory is encoded into $z_{T-1}$ (i.e., $z_{D}$).

Since encoding and execution are only coupled by the embedding, the whole CBE network can be trained end-to-end. Through end-to-end learning, the encoder learns a common behavior manifold (Sec.V). The embedding can be extremely low-dimensional (e.g., 32), which significantly saves memory compared to SLAM [13] or other learning-based approaches [12, 11].

The waypoint generator (right side of Figure 2) executes a behavior while tracking the robot’s progress. The robot starts with its initial observation, $o^{\prime}_{1}$, which does not have to exactly match the beginning of the demonstration, $o_{1}$. At every time step $t$, an LSTM unit takes as input the embedding $z_{D}$ of the demonstration and the embedding $z^{\prime}_{t}$ of the images observed so far (computed using the same encoder network used for demonstration embeddings), along with features provided by an “Attractor” network described below. Using these, the recurrent unit predicts the next local waypoint, $x_{t},y_{t}$, and the current progress, $\phi_{t}$. The waypoint is input into the robot’s low-level controller to generate motor commands. The low-level controller can be a simple PID controller, or it may support local obstacle avoidance [35]. The progress indicator $\phi_{t}$ provides the fraction of the demonstration the robot has completed at time $t$. It is used as a condition for behavior switching. After receiving the next observation, $o^{\prime}_{t+1}$, new attractor features and embedding $z^{\prime}_{t+1}$ are computed and input to the next LSTM step. This process is repeated until the robot reaches the goal, indicated by $\phi=1$.

Attractor Network. During execution, the robot’s initial location and orientation may not exactly match the beginning of a demonstration, requiring the robot to align its initial location sufficiently well to follow the demonstrated trajectory. Similarly, to determine when the robot has reached the goal, solely accumulating motion information from the observed images is not accurate enough. CBE solves these problems via the attractor network, which combines the robot’s current observation $o^{\prime}_{t}$ with $o_{1}$ and $o_{T}$ (i.e, attractors) to provide features that can relate the current observation to the beginning and end of the demonstration. The attractor network is a CNN that generates $f_{o^{\prime}_{1},o_{1}}$ and $f_{o^{\prime}_{t},o_{T}}$ which are concatenated with the embedding (see Figure 2 and 4).

Since behavior embeddings are learned from egocentric observations, compounding error is inevitable, implying that $z$ may not encode a complex long-horizon behavior precisely. We solve this by segmenting a long trajectory into a sequence of behaviors, each of which is specified by its embedding $z_{D}$ and initial and final observations, $o_{1}$ and $o_{T}$, respectively. Via the attractor features, $o_{1}$ provides robustness toward noisy locations when starting a behavior, and $o_{T}$ helps the behavior reach the goal location accurately enough to transition to the next behavior (related to funnels in LQR-Trees [36]).

We find fixed-distance segmentation works well in practice (Sec. V). Given an observation sequence $o_{1},o_{2},...o_{T}$, we segment it into equally spaced segments, subject to the constraint that every segment contains no more than $K$ observations, where $K$ is determined by a validation set. Visual attractors are placed at the segmentation boundaries, and two adjacent segments share attractors.

Behavior Switching. When a robot executes a sequence of behaviors, it needs to know when it can safely switch from the current behavior to the next. It makes the switching decision by checking if the progress indicator of executing the current behavior $\phi_{\text{current}}$ is close to 1 (set to 0.95 in practice). If the condition holds, the robot resets its internal states and starts executing the next behavior $z_{\text{next}}$.

The segmentation method described in Sec. III-D can be extended to enable a robot to re-compose behavior segments from multiple demonstrations. In Figure 3, a robot is given demonstrations $A\rightarrow B$ and $C\rightarrow D$. If the attractor $\mathcal{A}_{2}$ and $\mathcal{A}^{\prime}_{2}$ are close enough, then the robot can execute behaviors $z_{1},z^{\prime}_{2},z^{\prime}_{3}$ sequentially to go from $A$ to $D$, even though no direct demonstration is available. This also allows us to further compress demonstrations by removing repeated behaviors (e.g., one of $z_{2}$ and $z^{\prime}_{2}$).

Learning Choice Points. Fixed-distance segmentation does not guarantee that visual attractors from different demonstrations are placed at consistent locations, making it difficult to connect demonstrations. To mitigate this, we use a simple algorithm to find spatially consistent attractors. We train a classifier $d_{t}=\mathbb{C}(o_{t-k+1},...,o_{t})$ that takes the most recent $k$ observations and predicts the next waypoint direction (discretized into 128 bins) using the training dataset. We compute the variance $\sigma_{t}$ of the directional distribution to measure the uncertainty. Intuitively, $o_{t}$ with high variance suggests that future trajectories may diverge and thus $o_{t}$ is usually associated with spatially consistent locations such as intersections and doorways. Given a trajectory $o_{1},...,o_{T}$, we use $\mathbb{C}$ to compute the directional variances $\sigma_{1},...,\sigma_{T}$. Then we use a peak finding algorithm to find a set of choice points along a trajectory. While there are more sophisticated methods such as [37] that can potentially find better choice points, we find this simple approach to be effective (see Sec. V-D).

Figure 5 shows the t-SNE plot of embeddings extracted from training trajectories. The plot shows that the embedding space encodes a meaningful behavior manifold. From left to right, trajectory lengths are increasing. From top to bottom, there is a smooth progression from “right turns” to “going straight” and to “left turns”. The embedding space learns to encode visual odometry, even though it is not explicitly told to do so. We think this is why the learned embeddings generalize well to novel environments and can encode long-range behaviors, while being low-dimensional.

We study how well a robot can navigate between two locations with a single CBE behavior in unseen environments. We collected a set of trajectories of lengths ranging from 16 time steps to more than 200 time steps, with 500 trajectories collected for each time step. We extract an embedding from each trajectory to condition the waypoint generator. We jitter the robot’s initial pose to simulate imperfect alignment. We compare with the following baselines:

A common navigation task that robots perform is to navigate between two places [17, 12, 11]. We show that by incorporating behaviors, a robot can follow a long trajectory with very sparse guidance. We sparsify a trajectory by segmenting it into a sequence of behaviors (Sec. III-D). We compare with [11] that sparsifies a trajectory by reasoning about target reachability. Compression ratio is defined as $T/N$, where $N$ is the number of landmarks and $T$ is the total number of observations. For CBE, $N$ is approximately equal to the number of behaviors. We vary segment length $K$ in Sec. III-D to adjust the number of behaviors. For Visual SLAM and RPF, we only report their success rates.

We selected semantically meaningful locations (e.g., rooms) in each test environment as starts and goals and generated 500 long trajectories with an average length of 20 m. A robot follows each trajectory with a jittered initial pose. Figure 9(a) compares the trajectory following success rates at different sparsity levels. Incorporating behaviors significantly increases sparsity compared to a behavior-less approach [11]. Without visual attractors, CBE performs considerably worse, as the robot is not able to calibrate its state well to switch to the next behavior reliably. Visual SLAM performs competitively with high-resolution images, but fails completely when using the same low-resolution images as other baselines. Figure 9(b) shows a qualitative example, where a 20 m long trajectory (450 time steps) is segmented into four behaviors and the robot executes the behaviors sequentially to reach the goal.

Memory efficiency. Table I shows that CBE is at least 10x more efficient at encoding visual demonstrations than the baselines. A trajectory sparsified by CBE usually contains fewer than 10 embeddings (32 floats each), interleaved by visual attractors (800 floats each). In comparison, Visual SLAM stores over ten thousand feature descriptors, and existing learning-based methods require storing either dense visual features or raw images. This opens up opportunities to build compact topological maps of novel environments, studied next.

We follow the same setup as in [11, 18], where a robot builds a topological map of an environment from a set of experience trajectories consisting of RGB observations. A topological map is a directed graph where vertices are anchor observations selected from the trajectories and edges encode connectivity. This graph structure is often used in goal-conditioned navigation tasks, where a robot needs to plan a least-cost path to get to a specified goal.

We leverage behaviors to build sparse and well-connected topological maps. We first perform choice-point based segmentation as described in Sec. III-E, followed by distance-based segmentation (Sec. III-D) if needed. Each vertex stores an 800-dim attractor feature. Edges are either behavioral edges (via segmentation) or proximal edges (created by linking attractors). A robot first localizes itself and the goal using a network that predicts visual overlap [11]. Then the robot uses the Dijkstra algorithm to find the shortest path and executes the sequence of behaviors along the path.

We selected 10 to 14 semantically meaningful locations (e.g., rooms) in each test environment and collected pairwise trajectories to cover most of the traversable area. We built a topological map out of these trajectories. For planning, we let a robot start at one of the locations, plan a path to every other location, and follow the path. Table II compares the sizes of topological maps built by CBE and planning success rates against the baseline methods. CBE builds much more compact maps and is significantly more memory efficient. SPTM [18] subsamples observations and extracts a 512-dim feature vector from each observation. However, it is not robust enough for controlling a non-holonomic robot in a continuous state and action space. SLC [11] performs competitively, but at the expense of storing significantly more information per vertex (five $64\times 64$ RGB images). The main failure cases of SLC are caused by faulty edges in the map due to visual aliasing. In comparison, CBE maps have much fewer vertices, store only an 800-dim feature per-vertex, and achieve similar or higher planning success rates due to less visual aliasing. Figure 11 visualizes the distribution of vertices in the map.

Impact of choice points on generalization. To see the necessity of using choice points for mapping, we evaluate pairwise connectivity between locations when using a fraction of all pairwise demonstrations to build the map. In Figure 10, we can see that without choice points there is almost no generalization. This is because fixed-distance segmentation (Sec. III-D) creates attractors that are inconsistently distributed in an environment, making it difficult to link attractors from different demonstrations. Detecting choice points significantly improves connectivity, but there is still a gap compared to a dense map. It can be a future work to improve choice point detection to close this gap.