Verifiable Obstacle Detection

We will use the mathematical problem formulation of reach-avoid control to justify why we do not need to classify obstacles for collision avoidance purposes. The current section is motivated by [summers2010verification, summers2011stochastic] but we simplify the notations and the problem in a deterministic setting while the references consider stochastic problem formulations. Let $x_k\in X$ be the 2D-position of the vehicle at discrete time instance $k\ge 0$, where $X\subseteq R^2$ is the set of the state space. The set $D\subset X$ is the destination, and the sets $O_i\left(k\right)\subset X$ for $i\in M_O\triangleq \{1,2,\cdots ,M\}$ are obstacles, where $O_i\left(k\right)$ represents the $i^{th}$ obstacle and $M_O$ is the index set for the obstacles. The set $O_i\left(k\right)$ could be time-varying but it is assumed that the obstacles do not overlap with the destination, i.e., ${\cup }_{i\in M_O}(D\cap O_i(k\left)\right)=\varnothing$ $\forall$ $k$. For brevity, further mentions of $O_i\left(k\right)$ are reduced to $O_i$. Now, the reach-avoid control problem is to drive the vehicle to the destination $D$ while avoiding obstacles $O_i$ for $i\in M_O$ within finite time horizon $N$, given initial condition $x_0$. The success of this mission can be characterized by the following index $r$:

where $1_S(\cdot ):X\to \{0,1\}$ is the indicator function for a set $S$, and $\wedge$ is the logical AND. In short, $r=1$ if and only if the objective is achieved. The index $r$ in (2) can be used as a cost function of the optimal control problem as in [summers2010verification, summers2011stochastic]. Therefore, one is required to evaluate the indicator functions in (2), which means that it is required to know the set $D$ and $X\setminus O_i$ for $i\in M_O$.

However, index $r$ in (2) can be equivalently formulated as

and this expression can be used instead for the optimal reach-avoid control problem. The formulation (3) indicates that one could also address the control problem only with knowing ${\cup }_{i\in M_O}{O}_i$, but not individual obstacle sets $O_i$, i.e., one does not need to classify/distinguish individual obstacles for the reach-avoid control purpose.

It should be noted that classification adds valuable information that supports advanced features like predictive tracking, maneuver planning and improves AV performance. The argument here is only that object classification is not a necessity for obstacle avoidance and therefore not a part of minimal requirements for safety critical obstacle detection.

Collision avoidance involves many factors, from perception to vehicular control. While the dynamics and ethics of collision avoidance are complex [goodall2014ethical], the safety-critical obstacle detection system is required to detect all obstacles that can potentially collide with the AV. We utilize a physical model for collision risk from our prior work [9460196], where the potential risk of collision is determined by the overlap of the existence regions [schmidt2006research] of obstacles and AV within the AV’s time to stop.

The height of an obstacle is only useful in making a binary determination for collision avoidance, i.e., whether or not the obstacle is completely clear above the height of the AV. For example, in Figure 1 (a) the overhead road sign is completely above the AV, its exact height has no implication for collision avoidance. The box contains valuable information that is required to identify the obstacle within the box to be a vehicle, however as discussed in Section IV-A, such a recognition of the obstacle class is not a requirement for collision avoidance. Thus for safety-critical collision avoidance contains as much relevant information as . Therefore as long as an obstacle’s height is not erroneously detected to be above and clear of the AV, we can simply consider the top or bird’s eye view of the AV’s surroundings. While such a view of obstacles is not traditionally used in perception systems, however, path planning in AV, an inherently 2D problem, regularly uses this representation [ming2021survey].

The distance to an obstacle must be accurately detected for the collision-free operation of the AV. For collision avoidance, this distance is the minimum distance between the perimeters of the obstacle and the AV. Many safety parameters like safe following distance, time to collision and time to stop, are a function of the distance between the AV and obstacles [seiler1998development, cheng2019longitudinal], and therein lies the difference in underestimation and overestimation error in distance detection.

We determine a projection signifying a line on the road that the AV cannot cross without colliding with the obstacle for each obstacle. Figure 1 (c) shows an example of this. A circle is drawn with its center at the AV’s sensor hub and radius equal to the closest point on the obstacle from AV. The projection of the obstacle is then found as a line segment, tangent to the point where the above circle touches the obstacle. This line segment is shown as a thick line segment in Figure 1 (c). This line segment is a representation of the obstacle. Note that as new sensor inputs come in over time, the AV and obstacle move relative to each other, and the projection moves accordingly. So the line segment only represents the obstacle in the current frame to make safety-critical decisions until the next sensor frame is received and processed.

With this minimal representation of the ground truth obstacles, containing only the minimal information about the obstacles as required for safety-critical collision avoidance, we can now determine when detected obstacles are sufficiently detected to avoid collisions.

Each detected obstacle that meets the distance criteria ($\text{lx}@sectionsign$IV-D) and falls within the direction of an obstacle can now be used to determine if a ground truth obstacle is sufficiently covered by detected obstacles to avoid collisions with the ground truth obstacle. Detected obstacles are projected on the projection of the ground truth obstacle to determine what parts of the ground truth projection are covered by the detected obstacles, as shown in Figure 1 (d). The projected detection must provide enough information to avoid collisions for an obstacle to be considered as detected. As with distance ($\text{lx}@sectionsign$IV-D) this coverage may not be perfect but should have bounded errors. A limited proportion of the ground truth projection must be covered. This is equivalent to the traditionally used intersection over union (IOU) limits. It should be noted that the error margin of coverage is less important than that of the distance. The minimum distance always tracks the distance between the closest points between the AV and the obstacle, changing with each sensor input frame.

In this section we have discussed various features of obstacles a perception system may detect and detailed their relevance for safety-critical collision avoidance. Many properties of obstacles that are considered critical parts of perception in AV (e.g., class, 3D dimensions, road sign information), while indeed required for achieving the mission of autonomous driving, are not necessary for safety-critical collision avoidance. In brief, an obstacle is considered detected for safety-critical obstacle avoidance if the following are accurately determined (a) the distance of obstacle from AV, within bounded error margins. (b) a line on the road that the obstacle makes unsafe for the AV to cross. An obstacle detection system that reliably meets the above requirements can be used to detect safety-critical faults in perception by more complex perception systems, thus providing fault detection and collision avoidance system. The fusion of verifiable algorithms with DNN and the control decisions based on the verifiable algorithms have additional challenges that will be addressed in future works.

A rotating LiDAR contains several lasers stacked vertically. Each laser is given an index $r\in \mathrm{1...}N$, where $N$ is the number of lasers. Each laser has an inclination angle ${\xi }_i$ from the horizontal, positive below the horizontal, the set of which is represented by $\xi$. The lowest laser below the horizontal is assigned index $r=1$ and $r=N$ index represents the highest laser, usually inclined above the horizontal. The LiDAR is mounted on the vehicle at a height $H_L$ above the wheelbase. For rotating LiDAR, the horizontal step angle $\text{Uppsi}$ is uniform and can be calculated as ${360}^o/SamplesPerRotation$. The sensor is considered the origin point for the coordinate system. At each rotation, a new column of N samples is recorded and indexed with $c$. The sensor returns a range image, a 2D depth image of range values $R_{r,c}\forall r\in \mathrm{1...}N,c\in \mathrm{1...}\text{Uppsi}$. While we assume the more prolific rotating LiDAR, a solid state LiDAR [roriz2021automotive] would have similar parameters. Table II and Figure 2, respectively, summarize and represent some of these parameters, using example values from real world dataset [sun2020scalability].

We assume the following constraints for the validity of the Detectability model in Section VI:

C1: All LiDAR beams encountering solid obstacles, including ground, within the max range of the LiDAR, return with strong enough intensity from the first obstacle they encounter so that the return is recorded. This assumption holds in real world except when; (a) there are physical impediments in the air like dust, smoke, fog or rain; or, (b) adversarial objects with extremely reflective, absorbent or transparent surfaces.

C2: The obstacle’s width, projected on a plane perpendicular to the LiDAR beams falling on the obstacle, must be enough to have LiDAR points returned from it. For example, a thin sheet aligned parallel to the LiDAR beam’s direction can never be detected. According to the formula for circle arc length, a conservative bound can be established:

Since $\text{Uppsi}$ is small, the arc length is approximately equal, though always greater than the chord length for the same points. Being a small value, this width is not a prohibitive constraint, e.g., using values from Table II the width constraint at max LiDAR range of $75$ $m$ is just $17$ $cm$.

C3: At least one LiDAR point exists on the ground before the obstacle. This is an algorithmic constraint [bogoslavskyi17pfg]. While we focus on the primary Top LiDAR only in rest of this work, additional low height limited field of view (FOV) LiDAR sensors can be used for obstacles closer than $D_{min}$, e.g., Front, Rear, Side-Left and, Side-Right LiDAR in Waymo Open Dataset [sun2020scalability].

Furthermore, the following are assumed initially ($\text{lx}@sectionsign$VI-A) and relaxed in later sections:

A1: Obstacle touches the ground at ${90}^o$, i.e., ${\alpha }_o={90}^o$. Relaxed in Sections VI-B and VI-C.

A2: There is no ground inclination change between the vehicle and the obstacle. Relaxed in Section VI-D.

A3: No noise in detected range. Relaxed in Section VI-E.

We start with a simple system model, as shown in Figures 2 and 5, with Assumptions A1, A2 and A3.

Ground Removal: The primary part of the Depth Clustering algorithm is ground removal, i.e., determining which range image points are on obstacles vs. ground. FN errors can occur if points on obstacles are mistakenly considered part of the ground. Ground removal is based on vertical depth discontinuity using the inclination angles $\alpha$. Assuming the first point ($r=1$) to always be on the ground, a sharp change in $\alpha$ above a threshold ${\alpha }_{th}$ indicates that a point is on an obstacle. The first point must lie on the ground for the subsequent comparisons to be meaningful (C3). Inclination angle is calculated from the range image, as designed by Bogoslavskyi and Stachniss [bogoslavskyi17pfg], shown in Figure 2, as

The point $r,c$ is considered to not be on the ground if, $R_{r-1,c}$ is on the ground, ${\alpha }_{th}<{45}^o$, and

If $R_{r-1,c}$ is not on ground then $R_{r,c}$, is also considered to not be on ground. The lowest row of points $R_{0,c}$ are assumed to be on the ground ($\text{lx}@sectionsign$V-B C3). The column index corresponds to a rotational position of the sensor. For brevity, the column index is omitted for points in the same column only.

At horizontal distance $D$ from the sensor, the height of a LiDAR beam $r$ can be calculated as:

For brevity, $H_r(D,{\xi }_r,H_L)$ is referred to as $H_r\left(D\right)$ from this point as ${\xi }_r$ and $H_L$ are constant once a LiDAR sensor is chosen and placed on an AV. Let us define $r=min\left\{i|H_i\right(D)>0^o\}$, i.e., $R_r$ is the first point on the obstacle.

With this background, we can determine the minimum height of an obstacle that can be detected when the obstacle is at a distance of $D$ from the sensor (Figure 2). It is required to check three consecutive LiDAR points to detect an obstacle, according to the ground removal algorithm presented in (5) through (9).

Theorem 1 consists of two sets of conditions based on the obstacle’s height. The second set indicates that if the height of the obstacle is sufficiently large, then there will be more than two LiDAR points on the obstacle (${\alpha }_{r+1}={90}^o$). This allows us to detect the obstacle without further condition on the angle $\Delta {\alpha }_r$. The first set is the case that, when the size of the obstacle is small, there is only one LiDAR point on the obstacle, which requires us to have an additional condition for the angle $\Delta {\alpha }_r$.

The first condition set in Theorem 1 implies that the minimum height to be detected at distance $D$ satisfies

which depends on the distance $D$ and threshold ${\alpha }_{th}$.

In this case, if $R_i$ is at the end of the inclined obstacle, then its height at a distance $D$ is found by

This height can be used to determine whether there are more than two LiDAR points on the obstacle. Further notice that the angle ${\alpha }_r$ is found by reduced height $\frac{H_r\left(D\right)}{tan\left({\xi }_r\right)/tan\left({\alpha }_o\right)+1}$ and increased width $D+\frac{H_r\left(D\right)}{tan\left({\xi }_r\right)+tan\left({\alpha }_o\right)}-\frac{H_L}{tan\left({\xi }_{r-1}\right)}$. This observations induce the following Corollary from Theorem 1.

We are interested in the first beam on the obstacle, where its index is defined by $r_g=min\left\{i|H_i\right(D)>h_g\}$. Noticing the height of the obstacle tip is $h_o+h_g$, we can reformulate Theorem 1 as the following corollary.

The minimum detectable height for this case is found by

Assumptions: We maintain all assumptions in $\text{lx}@sectionsign$VI-A except A2, i.e., Ground inclination ${\alpha }_g$ could be non-zero (Figure 5).

Ground inclination affects the detectability model only when relative inclination changes between the obstacle and the AV. This section assumes that ground inclination starts before the obstacle position, i.e., $d<D$. There are two cases.

Case I: The inclination starts after the beam $R_{r-1}$, i.e.,

We can extend Corollary 1 to find the detectability condition. The first beam touching the obstacle must be higher than the ground at distance $D$. Let us define

If $R_{r_f+1}$ is at the end of the obstacle, then

which is the threshold to determine whether $R_{r_f+1}$ is on the obstacle. Furthermore, ${\alpha }_{r_f}$ is found by increased height $\frac{H_{r_f}\left(D\right)-(D-d)tan\left({\alpha }_g\right)}{1-tan\left({\xi }_{r_f}\right)tan\left({\alpha }_g\right)}+(D-d)tan\left({\alpha }_g\right)$ and decreased width $D+\frac{H_{r_f}\left(D\right)-(D-d)tan\left({\alpha }_g\right)}{tan\left({\xi }_{r_f}\right)-cot\left({\alpha }_g\right)}-\frac{H_L}{tan\left({\xi }_{r_f-1}\right)}$. This observation induces the following Corollary.

Case II: The inclination starts before the beam $R_{r-1}$, i.e.,

In this case, the beam point of $R_{r_f-1}$ land on different point from that of the case II. This decreases relative height $H_L-R_{r_f-1}sin\left({\xi }_{r_f-1}\right)$ and increases relative width $\frac{H_L}{tan\left({\xi }_{r_f-1}\right)}-R_{r_f-1}cos\left({\xi }_{r_f-1}\right)$ between $R_{r_f-1}$ and $R_{r_f}$. This changes ${\alpha }_{r_f}$ found in Corollary 3. It is also worth to notice that if

then ${\alpha }_{r_f-1}={\alpha }_g$, and thus we have $\Delta {\alpha }_r={\alpha }_r-{\alpha }_g$. Using these facts, one can find an extension of Corollary 3.

Assumptions: We maintain all assumptions in $\text{lx}@sectionsign$VI-A except A3, i.e., there exists a depth detection error. Minor inaccuracies in depth detection can be a problem when finding $\Delta x,\Delta z$. In particular, the $i^{th}$ beam returns noisy measurement $y_i=R_i{ϵ}_i$ [wang2019pseudo] instead of its ground truth distance $R_i$ from the sensor to the obstacle where ${ϵ}_i\in [1-ϵ,1+ϵ]$ is unknown noise with a known sensor error bound $ϵ$, e.g., Velodyne HDL-64E S3 LiDAR has a range detection inaccuracy of $\pm 2$ $cm$ [velodynehdl64].

Under mild assumptions, Theorems 2 and 3 provide a bound of the first angle ${\alpha }_r$ on the obstacle, and a bound of the angle ${\alpha }_i$ between two consecutive points on the obstacle.

The assumptions $y_{r}cos\left({\xi }_r\right)\ge y_{r-1}cos\left({\xi }_{r-1}\right)$ and $y_{r}sin\left({\xi }_r\right)\le y_{r-1}sin\left({\xi }_{r-1}\right)$ are mild because $R_{r}cos\left({\xi }_r\right)\ge R_{r-1}cos\left({\xi }_{r-1}\right)$ and $R_{r}sin\left({\xi }_r\right)\le R_{r-1}sin\left({\xi }_{r-1}\right)$ hold for most of the cases, and ${ϵ}_i$ is around $1$. For the same reason, the assumption $y_{i}sin\left({\xi }_i\right)\le y_{i-1}sin\left({\xi }_{i-1}\right)$ is mild as well.