Basic Concepts of Embodied Navigation Algorithms

This chapter establishes the minimal knowledge framework for embodied navigation: how robots estimate their own position based on sensor observations, construct or read maps, plan paths, and convert these paths into executable control actions. After studying this, one should be able to understand the scenarios, sensors, navigation grids, targets, and evaluation metrics in the subsequent Habitat experiments.

A complete navigation system continuously executes the following loop:

mermaidflowchart LR
    A[相机与深度等观测] --> B[定位与状态估计]
    B --> C[地图或场景表示]
    C --> D[全局路径规划]
    D --> E[局部规划与避障]
    E --> F[速度或离散动作]
    F --> G[机器人与环境]
    G --> A

Each module has different responsibilities: the localization policy answers “where is the robot”, the mapping policy answers “what is the structure of the environment”, the planning policy answers “from where should it pass through”, and the control policy answers “how to move at this moment”. The end-to-end policy can combine multiple modules into a single model, but during evaluation, the perception, path, and execution stages still need to be distinguished.

2. Common Task Definitions

Task	Target Input	Typical Output	Main Challenges
Point Target Navigation	Relative or target coordinates	Movement, turning, stopping	Position error and obstacle avoidance
Object Target Navigation	Target category or target image	Motion actions and stop decision-making	Target search and semantic generalization
Image Target Navigation	Reference image of target location	Motion actions and stop decision-making	View change and location matching
Visual Language Navigation	Natural language path description	Continuous or discrete navigation actions	Instruction alignment, historical memory and path selection
Exploration and Active Perception	Coverage or information gain targets	Observation position sequence	Unknown space modeling and sampling efficiency

3. Map and Planning

The two-dimensional grid map divides space into passable, occupied, and unknown areas, making it suitable for classic planning algorithms such as A* and Dijkstra. Three-dimensional simulators typically generate navigation grids based on scene grids and robot dimensions, while planners only search on passable surfaces.

3.2 Global Planning and Local Planning

Global planning generates an overall route from the starting point to the target based on the known map. Local planning uses current sensor data to handle moving obstacles, map errors, and control constraints. Without local obstacle avoidance but with a global route, robots have difficulty adapting to dynamic environments; without a global goal but with local responses, they are prone to circling in complex spaces or getting trapped in specific areas.

3.3 Classic Search Algorithm

Dijkstra: Expands nodes based on the cumulative path cost, which yields the shortest path in a graph with non-negative edge weights.
A*: Adds heuristic estimates of the goal based on the cumulative cost; usually, fewer nodes are expanded than Dijkstra.
Fast Expand Random Tree: Samples and expands tree structures in continuous high-dimensional spaces, suitable for planning problems with kinematic constraints.

4. Sensors and Status

RGB cameras provide textures and semantics, depth cameras provide surface distances, lidar provides stable geometric scans, and odometers and inertial measurement units provide short-term motion estimates. Ideal poses can be obtained directly in the simulation environment, but whether training and testing allow the use of this information must be specified by the task protocol.

5. Common Evaluation Metrics

Success Rate

Success rate statistics refer to the proportion of rounds in which the target reaches the designated number of steps correctly and performs the stop action. The target distance threshold, collision conditions, and stop action requirements must remain unchanged.

Path Length Weighted Success Rate

The path length-weighted success rate takes into account both success and path efficiency. Trajectories that are successful but with significant detours score lower than those that reach the shortest path successfully.

Target Distance and Collision

The target distance is suitable for analyzing the degree to which the failed trajectory approaches the target; the number of collisions, collision time, or safe distance are used to analyze execution safety. The definition of collisions may vary across different papers, so verify the protocol before comparison.

6. Minimum Learning Check

Before entering the Habitat practice, ensure you can answer the following questions:

What type of pose, category, image, or language target does the current task provide to the policy?
Can the policy read real poses or full maps?
Is the action a discrete forward movement and turning, or a continuous velocity?
Does successful judgment require explicit stopping?
How many rounds, which scenarios, and which initial states are used for evaluation?

Next, study the Habitat-Sim environment and dataset , and then engage in Habitat-Lab tasks and evaluation practices.

1. Navigation Closed Loop