PaperlayerView exact revision on arXiv

Source-linked AI summary

Synthesis of Control Barrier Functions Using a Supervised Machine Learning Approach

Mohit Srinivasan, Amogh Dabholkar, Samuel Coogan, Patricio Vela

arXiv:2003.04950v1cs.ROeess.SY

TL;DR

The paper addresses how to synthesize control barrier functions when unsafe regions are unknown and must be inferred from sensor data. It uses a kernel-SVM classifier trained on safe and unsafe samples from LiDAR measurements, with formal safety guarantees and ROS-based simulation results showing trajectories closely matching ground truth. Its online guarantee is local because instantaneous measurements do not characterize the entire unsafe boundary.

  • Problem

    Unknown unsafe regions make closed-form control barrier functions unavailable, creating a need to synthesize them from sensor measurements.

  • Method

    A kernel-SVM classifier learns barrier-function specifications from safe and unsafe samples generated from LiDAR measurements.

  • Results

    Offline synthesis guarantees safety for an under-approximated safe set, while ROS simulations with a LiDAR-equipped omnidirectional robot produce trajectories closely matching ground truth.

  • Takeaways & Limitations

    Sensor-based barrier synthesis supports safe robot operation in environments without prior obstacle-boundary knowledge.

  • Takeaways & Limitations

    The online method has only a local safety guarantee because instantaneous measurements do not cover the full unsafe-set boundary.

Abstract

from arXiv · show

Control barrier functions are mathematical constructs used to guarantee safety for robotic systems. When integrated as constraints in a quadratic programming optimization problem, instantaneous control synthesis with real-time performance demands can be achieved for robotics applications. Prevailing use has assumed full knowledge of the safety barrier functions, however there are cases where the safe regions must be estimated online from sensor measurements. In these cases, the corresponding barrier function must be synthesized online. This paper describes a learning framework for estimating control barrier functions from sensor data. Doing so affords system operation in unknown state space regions without compromising safety. Here, a support vector machine classifier provides the barrier function specification as determined by sets of safe and unsafe states obtained from sensor measurements. Theoretical safety guarantees are provided. Experimental ROS-based simulation results for an omnidirectional robot equipped with LiDAR demonstrate safe operation.

I. INTRODUCTION

The paper addresses the difficulty of using control barrier functions when obstacle boundaries are unknown, proposing sensor-driven synthesis while retaining formal safety guarantees and nominal-policy tracking.

  • I. INTRODUCTION: Unknown obstacle boundaries make closed-form barrier-function construction difficult and prevent direct use of CBF safety guarantees.The paper motivates learning barrier functions for robots operating without prior knowledge of obstacle boundaries.
  • I. INTRODUCTION: The proposed framework synthesizes barrier functions with an SVM from safe and unsafe samples obtained through sensor measurements.The paper presents both offline and online training methods for sensor-derived datasets.
  • I. INTRODUCTION: Formal guarantees show offline synthesis renders the system safe for an under-approximated conservative safe set, with a similar local guarantee online.The framework is evaluated in a ROS-based simulator using a LiDAR-equipped omnidirectional robot.
  • II. MATHEMATICAL BACKGROUND: Control barrier functions define safe regions and can impose affine-in-control constraints in quadratic programs for efficient online safety control.A zeroing control barrier function renders the safe set forward invariant, while the associated QP follows a nominal policy subject to safety.

III. PROBLEM STATEMENT

The problem is to synthesize barrier functions from LiDAR measurements when unsafe regions are unknown, supporting either offline learning from a dataset or online learning during traversal.

  • III. PROBLEM STATEMENT: LiDAR depth measurements identify unsafe state-space regions when the sensor has sufficiently fine angular resolution.The stated assumption is that the increment angle captures the environment’s spatial profile from a given offset distance.
  • III. PROBLEM STATEMENT: The state space contains unknown unsafe sets represented by unknown zeroing control barrier functions, while the robot follows a nominal feedback policy.The goal is to remain safe while minimally deviating from that policy.
  • III. PROBLEM STATEMENT: Sensor measurements and robot state provide boundary points satisfying h(x)=0 for the unsafe regions.These boundary samples support synthesis of the unknown barrier functions.
  • III. PROBLEM STATEMENT: The requested framework must learn the union of unsafe regions either offline from safe and unsafe samples or online from instantaneous measurements.The online formulation learns as the system traverses the domain.

IV. CONTROL BARRIER FUNCTION SYNTHESIS FRAMEWORK

The synthesis framework formulates unsafe-region identification as biased kernel-SVM classification, emphasizing correct classification of unsafe states and using the learned classifier as a barrier-function specification.

  • A. Support Vector Machines: Kernel SVMs classify safe and unsafe states and provide the learned barrier-function specification.A kernel maps nonseparable data into a higher-dimensional space where obstacle and safe regions can be separated.
  • A. Support Vector Machines: The SVM uses separate positive- and negative-class penalties to bias classification toward correctly identifying unsafe states.The optimization includes classification constraints with slack variables and class-specific costs.
  • A. Support Vector Machines: A Gaussian kernel performs the nonlinear mapping, with bandwidth σ as a hyperparameter.The dual optimization uses the kernel to avoid explicitly defining the feature map.
  • A. Support Vector Machines: Setting C−=∞ and ∞>C+>1 creates a hard margin for unsafe states while permitting some safe-state misclassification.This asymmetry reflects that labeling an unsafe state as safe is undesirable, whereas labeling a safe state as unsafe does not compromise safety.

B. Training Dataset Generation

The training-data generator converts LiDAR scans into world-coordinate unsafe boundary samples and radially offset safe samples, then combines them for SVM training.

  • B. Training Dataset Generation: LiDAR measurements and robot state are transformed from polar scan coordinates into world Cartesian coordinates.The transform maps sensor measurements into points usable by the SVM.
  • B. Training Dataset Generation: Finite LiDAR depth readings identify points on unsafe-set boundaries and populate the negative training set.The unsafe samples correspond to detected boundary points.
  • B. Training Dataset Generation: Each unsafe boundary point is projected radially backward toward the robot by a finite offset distance d to generate positive safe samples.The construction follows the line segment joining the robot state and the detected boundary point.
  • B. Training Dataset Generation: Figure 1 depicts unsafe boundary samples in red, offset safe samples in green, and LiDAR rays as red dashed lines.The figure illustrates one sensor-derived training-dataset instance.
  • B. Training Dataset Generation: The positive and negative labeled samples are combined into the training dataset used by the SVM classifier.The procedure is summarized as the training dataset generator algorithm.

C. Barrier Function Synthesis with Kernel-SVMs

The method uses kernel SVMs to transform sensed safe and unsafe samples into a signed level-set barrier function. The synthesized function classifies unsafe samples with a formal guarantee.

  • Gaussian kernels map sampled points into an approximate occupancy representation for capturing safe and unsafe region boundaries.The resulting classifier is evaluated through posterior probabilities for the two classes.
  • Posterior class probabilities are converted into margin scores that define the signed level-set barrier function.The resulting approximator is described as a two-hidden-layer Gaussian kernel neural network.
  • The synthesized barrier satisfies bh(x) < 0 for every unsafe training sample x in O−.This follows from the hard-margin treatment of unsafe samples and the universal approximation capability of RBF kernels.
  • The kernel-SVM procedure outputs an estimated barrier function bh from training dataset T.Algorithm 2 takes T as input and returns bh.

D. Offline Barrier Function Synthesis & Control

The offline approach learns one barrier function from LiDAR-derived obstacle-boundary samples and uses it as a single QP constraint. Under the stated set-containment assumption, the resulting estimated safe set is forward invariant.

  • Offline data and synthesis: LiDAR supplies sufficiently dense unsafe-boundary samples for p unknown unsafe regions characterized by barrier functions hi.The analysis assumes an oracle provides these samples.
  • Offline data and synthesis: A single synthesized barrier function captures all unsafe sets, reducing the QP to one barrier constraint.The QP controller combines this constraint with a nominal controller while solving for control inputs.
  • QP control: The offline controller repeatedly solves the QP, updates the state, and applies the resulting control until the task goal is reached.The algorithm uses a nominal controller as input.
  • Safety guarantee: As LiDAR angular resolution θres approaches zero, the estimated unsafe set over-approximates the true unsafe regions.The estimated unsafe region is defined by bh(x) ≤ 0.
  • Safety guarantee: If the true unsafe set S is contained in the estimated set bS, trajectories starting in bSc remain in bSc for all t ≥ 0.The guarantee follows from enforcing the estimated barrier constraint in the QP and establishing forward invariance.

E. Online Barrier Function Synthesis & Control

The online method synthesizes barrier functions from incrementally sensed data and provides local safety guarantees, but not a global guarantee because the full unsafe-set boundary is unknown.

  • Online synthesis: Online synthesis initializes without state-space information beyond the nominal feedback policy and updates a kernel-SVM barrier using sensed measurements.The controller repeatedly solves a QP and updates the robot state while the goal remains unreached.
  • Online synthesis: Using only current measurements yields a local barrier estimate, whereas aggregating past measurements improves the estimate as unsafe-region samples accumulate.Data aggregation can become computationally expensive because the dataset must be continuously updated.
  • Experimental comparison: The five-obstacle experiment compares ground-truth, offline, and online kernel-SVM trajectories using correlation and Fréchet-distance values.Both initial conditions show high correlations and small Fréchet distances, indicating similarity to the ground-truth trajectory.
  • Safety guarantee: As θres →0, the estimated unsafe set locally over-approximates the true unsafe region within the sensor range.The guarantee is stated for states locally within the sensing region Br(x).
  • Safety guarantee: Unlike the offline case, online synthesis provides no global unsafe-set over-approximation guarantee because the robot lacks samples covering the entire unsafe boundary.Safety nevertheless holds locally under locally Lipschitz robot dynamics.

V. EXPERIMENTAL RESULTS

The STDR experiments evaluate path planning in unknown environments, including both ellipsoidal obstacles and obstacles whose shapes are not easily represented by closed-form polynomial level sets.

  • Experimental environments: Two STDR environments occupy a 3.2 x 2 workspace: one contains five ellipsoidal obstacles, and the other contains more general obstacles.The robot has no a priori environment knowledge and follows a nominal controller toward a goal point while avoiding obstacles.
  • Robot and task: The robot dynamics are modeled as ˙x = u, with a nominal policy directing it toward x_goal and a goal region defined by ∥x−x_goal∥≤0.1.Ground-truth data for the first scenario are obtained using a grid-based method.

A. Evaluation Metrics

Trajectory outcomes are evaluated with correlation and Fréchet distance, combining evolutionary and Euclidean mismatch measures; the STDR experiments illustrate the controllers’ use in difficult obstacle geometries.

  • Evaluation metrics: The evaluation uses correlation coefficient R and Fréchet distance F to compare generated trajectories.Together, these metrics assess both how trajectories evolve relative to one another and their Euclidean separation.
  • Evaluation setting: In the STDR scenario, offline and online kernel-SVM controllers navigate obstacles that are difficult to characterize with closed-form polynomials while maintaining safety.The figure shows trajectories for two initial conditions in an unknown environment.

1) Correlation Coefficient:

The correlation coefficient measures how changes in one trajectory correspond to changes in another and provides intuition about their flow similarity.

  • Correlation coefficient: The correlation coefficient captures the change in one trajectory with respect to another and indicates the flow of one trajectory relative to the other.Trajectories are typically considered highly correlated when R exceeds 0.7.

2) Fr´echet Distance:

Fréchet distance measures Euclidean mismatch between trajectories, with smaller values indicating closer agreement. In the five-obstacle scenario, the learned-barrier trajectories remained close to the ground-truth behavior.

  • 2) Fréchet Distance:: Fréchet distance measures the Euclidean distance mismatch between two trajectories, with F = 0 indicating identical trajectories.
  • 2) Fréchet Distance:: The five-obstacle evaluation compares trajectories generated by offline and online kernel-SVM barrier estimation with a ground-truth trajectory.
  • 2) Fréchet Distance:: Distances < 0.10 were obtained on average for each case, indicating small Euclidean mismatch between the trajectories.
  • 2) Fréchet Distance:: The offline kernel-SVM estimated barrier function closely replicated the true barrier functions according to its very high correlation and very small Fréchet distance.
Loading 2003.04950v1…