Fastron: An Online Learning-Based Model and Active Learning Strategy for Proxy Collision Detection

Nikhil Das, Naman Gupta, Michael C. Yip

Abstract

We introduce the Fastron, a configuration space (C-space) model to be used as a proxy to kinematic-based collision detection. The Fastron allows iterative updates to account for a changing environment. By using a modified kernel perceptron and a specialized active learning strategy, Fastron achieves significant speedups in collision checking for robotic motion planning.

Introduction

In robotics, motion planning is fundamentally dependent on collision detection. To navigate from one point to another, a robot must continuously verify if its configuration (C-space) overlaps with physical obstacles. Traditional Kinematic-based Collision Detections (KCDs) are computationally expensive, often consuming over 90% of the processing time in sampling-based planners like Rapidly-exploring Random Trees (RRTs).

Fastron addresses this bottleneck by acting as a "proxy" model. Instead of performing heavy kinematic math for every check, Fastron learns the shape of C-space obstacles on the fly, providing a lightweight alternative that filters out safe configurations rapidly.

Methods and Architecture

Fastron, short for "Fast Perceptron," is built upon three core technical pillars designed for speed and safety in dynamic environments:

  1. Modified Kernel Perceptron: Unlike standard binary classifiers, Fastron utilizes a Gaussian kernel to model the complex, non-linear boundaries of C-space obstacles. It incorporates One-Step Weight Correction for immediate error correction and Conditional Biasing to ensure the model remains conservative, favoring safety by slightly "padding" obstacles.
  2. Active Learning Strategy: To maintain an accurate map without checking every point, Fastron employs a two-stage active learning loop. The Exploitation stage checks points near known boundaries where changes are likely, while the Exploration stage samples the broader space to detect new obstacles.
  3. Sparsity and Efficiency: The model actively prunes redundant support points to prevent slowdowns as more data is collected. Furthermore, it reuses a pre-calculated Gram matrix of distances, avoiding the high overhead typically associated with kernel methods.
The Fastron algorithm architecture, illustrating the loop between the kinematic collision detector and the active learning-based model update.

Key Insights

  • The Proxy Philosophy: Fastron prioritizes being "good enough" and extremely fast over perfect precision. It acts as a high-speed filter, only invoking the expensive KCD "oracle" when the active learning strategy identifies a need for updates.
  • Obstacle Independence: Unlike traditional checkers that slow down as the number of objects increases, Fastron models the C-space directly. This means its check time remains nearly constant regardless of workspace complexity.
  • Safety via Bias: By applying a higher bias to collision configurations, the model creates a buffer zone, maintaining high recall and minimizing the risk of missing real collisions.

Performance and Results

The algorithm was evaluated using 2-DOF and 7-DOF (PR2 arm) simulations against industry-standard libraries like the Flexible Collision Library (FCL) and Gilbert-Johnson-Keerthi (GJK).

Comparative performance metrics of Fastron (FCD) against FCL and GJK, highlighting the significant speedup in collision detection time.

As shown in the experimental results, Fastron achieved proxy collision checks 2 to 8 times faster than GJK and FCL, respectively. When integrated into an RRT planner, the overall collision checking stage was approximately 3.7 times faster. Despite being a proxy, Fastron maintained a recall rate of 90-98%, ensuring high safety standards through its conservative padding strategy.

Limitations and Future Work

While highly efficient, Fastron's conservative nature leads to a higher false-positive rate, which can make navigating narrow passages difficult in very crowded environments. Additionally, the memory requirements for storing the Gram matrix may become a bottleneck in extremely high-dimensional spaces. Future research will focus on resampling strategies to improve precision in tight spaces and developing confidence scores to better guide the active learning process.

Summary updated

Abstract

We introduce the Fastron, a configuration space (C-space) model to be used as a proxy to kinematic-based collision detection. The Fastron allows iterative updates to account for a changing environm...
BibTeX
@inproceedings{das2017fastron,
  author = {Nikhil Das and Naman Gupta and Michael C. Yip},
  title = {{Fastron: An Online Learning-Based Model and Active Learning Strategy for Proxy Collision Detection}},
  booktitle = {Conference on Robot Learning},
  year = {2017},
  url = {https://openreview.net/forum?id=e8AngpRf-ho},
}
Figure