VFH-Based Obstacle Avoidance System

Introduction and Motivation

The Vector Field Histogram approach to Obstacle Avoidance allows real-time obstacle avoidance for our drones, through

Its improved method of clustering LiDAR detections for each oscillation into fixed angular sectors
Calculating obstacle densities for each sector based on distance and number of detections
Summarising the 2D FoV of our drone into a Polar Histogram for each LiDAR oscillation
Clustering safe sectors into ‘candidate valleys' based on obstacle-density data
Choosing the best candidate valley based on the drone’s immediate next waypoint
Deflecting the drone to the best candidate valley chosen (or stopping and reversing if no candidate valleys exist)

(The Vector Field Histogram approach is named such because it constructs a histogram grid representing obstacle densities in a polar coordinate system and uses a vector field to determine a feasible navigation path)

The previously implemented Bendy-Ruler approach relied on reactive bending around obstacles directly in front of it, whereas the improved approach (due to its broadened scope and applicability) extends beyond just reactive manoeuvres, giving us a more detailed understanding of obstacle distribution.

Key improvements of the updated system include:

Smarter Path Selection: Instead of making immediate reactive turns or complete stops when an obstacle is detected, the new approach evaluates multiple trajectory options and selects the most optimal path.

Improved Obstacle Representation through Density-Clustering: Clusters LiDAR obstacle data by density (calculated using proximity and number of readings in a sector) rather than shape, which is more relevant when choosing a safe path to deflect the drone.

Reduced Sensitivity to Sensor Noise: By aggregating LiDAR data for an entire oscillation into a histogram with obstacle-density values for discrete sectors calculated independently, VFH reduces the likelihood of considering ‘noise’, or faulty and isolated LiDAR readings.

Waypoint Integration: The optimised approach considers the drone’s next waypoint when making a deflection, balancing obstacle-avoidance with global path-following and keeping the drone on course while manoeuvring safely around unsafe areas.

Overview and Background

The key idea behind VFH is constantly visualising the entire 2D FoV of the drone by calculating obstacle density values for each (e.g 5^o wide) sector, allowing us to make more informed, planned, and optimal path deflections as the LiDAR data flows through.

The system is designed as a modular pipeline that processes real-time LiDAR data, extracts obstacle densities, and computes safe navigation paths for the drone. The pipeline operates in a continuous loop, where LiDAR scans are parsed into oscillations, transformed into sector obstacle density maps, and fed into a polar histogram. For each oscillation, this histogram is then analysed to determine the best flight direction, and commands are relayed to the drone using the Flight Interface (switching to GUIDED mode during deflection) and then continuing the autonomous mission as planned.

For a more detailed read on the working and motivation behind this approach, please skim through this link: https://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1/borenstein_VFHisto.pdf

System Workflow

(todo: flow chart for pipelines + more visual diagrams + code snippets + polar histogram diagram)

detection

The system configures LiDAR settings and fetches LiDAR readings
These readings contain distance and angle values that represent the environment around the drone.
The Detection module ensures that valid LiDAR detections are processed while filtering out invalid or noisy data.
These detections are passed to the LiDAR Parser for further processing in the form of LidarDetection objects.

lidar_parser

The lidar_parser module clusters continuous LiDAR readings into oscillations.
An oscillation represents a full sweep of the LiDAR sensor from one end to the other and back.
The parser tracks the angle direction (UP or DOWN) to detect when a full oscillation is completed.
Once an oscillation is detected, it is converted into a LidarOscillation object, which is passed to the VFH module for sector-based density calculation.

vfh

The vfh module takes a LidarOscillation as input and generates a polar obstacle density representation.
The polar obstacle density represents obstacle distribution across different angular sectors.
Unlike traditional clustering methods, this approach does not attempt to classify obstacles by shape. Instead, it prioritises density-based representations.
The density is calculated by:
- Dividing the scan into angular sectors.
- Assigning each sector a density value based on LiDAR readings.
- Applying confidence factors and decay rates to fine-tune obstacle representation
The VFH module calculates obstacle density by weighting LiDAR detections based on confidence and distance, giving higher priority to closer obstacles.

The generated PolarObstacleDensity object is passed to the vfh_decision module for trajectory planning.

vfh_decision

The vfh_decision module processes the PolarObstacleDensity to determine the safest and most efficient steering direction. It identifies valleys—clear paths between obstacles—and evaluates them based on:

Density threshold: Ensures a sector is safe for navigation if its density falls below this value.
Minimum consecutive sectors: Prevents the drone from choosing narrow, unreliable gaps.
Wide valley check: In AUTO mode, the drone prioritises its original route and only deviates if absolutely necessary.

The system then selects the best valley based on:

Proximity to the target direction (favoring paths aligned with the mission).
Valley width, ensuring smooth and stable navigation.

If no safe valleys exist, the system issues a "REVERSE" command to halt or backtrack. Once a direction is chosen, the command is sent to the Flight Interface for execution.

action_module

(Todo: this Task is under Asana: https://app.asana.com/0/75198147526823/1209038079752672 )

Autonomy