Multi-Robot Collision Avoidance

Motivation

Multi-Robot affects most of these!

Physics: Differential Drive Robot

Physics: Differential Drive Robot

Physics: Differential Drive Robot

Demo

Bézier Curves

Bézier Curve
A Bézier curve $\vp : [0, 1] \rightarrow \mathbb R^d$ of degree $n$ is defined by $n+1$ control points $\vp_0, \ldots, \vp_n \in \mathbb R^d$ as follows: $$\begin{align*} \vp(t) &= \sum_{i=0}^n b_{i,n}(t) \vp_i\\ b_{i,n}(t) &= {n \choose i} t^i\left(1-t\right)^{n-i}. \end{align*}$$
Cubic Bézier Curve
$$\begin{align*} \vp(t) &= (1-t)^3 \vp_0 + 3 t (1-t)^2 \vp_1 \\ &+ 3 t^2 (1-t) \vp_2 + t^3 \vp_3 \end{align*}$$

Bézier Curves Properties

  • Endpoint interpolation: The curve connects $\vp_0$ and $\vp_n$, i.e., $\vp(0) = \vp_0$ and $\vp(1) = \vp_n$
  • $C^n$ smoothness
  • Convex hull property: The curve lies inside the convex hull of their control points, i.e., $\vp(t) \in ConvexHull\{\vp_0,\ldots,\vp_n\}\ \forall t\in[0, 1]$

Cubic Bézier Curve Optimization

Cubic Bézier Curve
$$\begin{align*} \vp(t) &= (1-t)^3 \vp_0 + 3 t (1-t)^2 \vp_1 + 3 t^2 (1-t) \vp_2 + t^3 \vp_3\\ \vp(0) &= \vp_0\\ \vp(1) &= \vp_3\\ \dot{\vp}(t) &= 3(1-t)^2 (\vp_1 - \vp_0) + 6 (1-t) t (\vp_2 - \vp_1) + 3t^2 (\vp_3 - \vp_2)\\ \dot \vp(0) &= 3(\vp_1 - \vp_0)\\ \dot \vp(1) &= 3(\vp_3 - \vp_2)\\ \end{align*}$$

Demo

Voronoi Cells

Voronoi region
Let $q_1,\ldots,q_K$ be a set of configurations on the state space $\mathcal Q$. The Voronoi region is defined as $$ R_k = \{ q \in \mathcal Q\mid d(q, R_k) \leq d(q, R_j), \text{ for all } j \neq k\} $$

Collision Avoidance Via Buffered Voronoi Cells (BVC)

  • Sense neighbor robots' position
  • Compute Voronoi regions (safe polyhedra per robot)
  • Shrink ("buffer") regions to account for robot size (still polyhedra)
  • Trajectory optimization / control with constraint to stay within safe region for some time

D. Zhou, Z. Wang, S. Bandyopadhyay, and M. Schwager, “Fast, on-line collision avoidance for dynamic vehicles using buffered voronoi cells,” IEEE Robotics and Automation Letters (RA-L), vol. 2, no. 2, pp. 1047–1054, 2017

Demo

Try it Yourself