2011年,柯普出版了《激情之夜:人和机器所作的俳句两千首》( Comes
the Fiery Night: 2000 Haiku by Man and
Machine),其中有一部分是安妮写的,其他则来自真正的诗人。但书中并未透露具体篇目的作者是谁。如果你认为自己一定可以看出人类创作与机器作品的差异,欢迎挑战。
It is such a general and powerful tool for combining information in
the presence of uncertainty.
What is it?
You can use a Kalman filter in any place where you have
uncertain information about some dynamic system, and
you can make an educated guess about what the system is
going to do next.
Kalman filters are ideal for systems which are continuously changing.
They have the advantage that they are light on memory (they don’t need
to keep any history other than the previous state), and they are very
fast, making them well suited for real time problems and embedded
systems.
It could be data about the amount of fluid in a tank, the temperature
of a car engine, the position of a user’s finger on a touchpad, or any
number of things you need to keep track of.
How a Kalman filter sees
your problem
The Kalman filter assumes that both variables are random and Gaussian
distributed. Each variable has a mean value 𝜇, which is the center of
the random distribution (and its most likely state), and a variance 𝜎2,
which is the uncertainty.
截屏2021-03-23
下午8.36.39.png
从参数之间的关联发掘更多信息:比如机器人的速度和位置,如果速度快,那么位置可能就比较远。
This kind of relationship is really important to keep track of,
because it gives us more information: One measurement tells us
something about what the others could be. And that’s the goal
of the Kalman filter, we want to squeeze as much information from our
uncertain measurements as we possibly can!
参数之间的相关性,可以用协方差矩阵 (covariance matrix)
来表示,即矩阵中的每个元素 ∑ij 表示第 i 个和第 j
个状态变量之间的相关度。注意,协方差矩阵是一个对称矩阵,这意味着可以任意交换
i 和 j。
This correlation is captured by something called a covariance
matrix.
Describing the problem
with matrices
We need some way to look at the current state (at time k-1) and
predict the next state at time k. We can represent this prediction step
with a prediction matrix, Fk.
请注意,预测矩阵要求严格反映运动的特征,要求预测准确,不能模糊。
For prediction matrix, it takes every point in our
original estimate and moves it to a new predicted location, which is
where the system would move if that original estimate was the
right one.
图片
不太理解这个公示是如何推导出来的,数学的理论知识不够踏实。
screen shot 2021-03-24 at
20.14.01.png
External influence
外部系统的影响
There might be some changes that aren’t related to the state itself —
the outside world could be affecting the system.
control matrix
control vector
External uncertainty
Everything is fine if the state evolves based on its own properties.
Everything is still fine if the state evolves based on external forces,
so long as we know what those external forces are.
如何应对外界的不确定性,比如四旋翼控制中的风影响。
We can model the uncertainty associated with the “world” (i.e. things
we aren’t keeping track of) by adding some new uncertainty after every
prediction step * Every state in our original estimate could have moved
to a range of states.
图片讲解
In other words, the new best estimate is a prediction made from
previous best estimate, plus a correction for known external
influences.
And the new uncertainty is predicted from the old uncertainty, with
some additional uncertainty from the environment.
Refining the estimate
with measurements
We might have several sensors which give us information about the
state of our system.
Each sensor tells us something indirect about the state— in other
words, the sensors operate on a state and produce a set of readings.
The units and scale of the reading might not be the same as the units
and scale of the state we’re keeping track of. You might be able to
guess where this is going: We’ll model the sensors with a matrix.
卡尔曼滤波的精妙处:
One thing that Kalman filters are great for is dealing with sensor
noise. In other words, our sensors are at least somewhat unreliable, and
every state in our original estimate might result in a range of sensor
readings.
From each reading we observe, we might guess that our system was in a
particular state. But because there is uncertainty, some states
are more likely than others to have have produced the reading
we saw.
We have two Gaussian blobs: One surrounding the mean of our
transformed prediction, and one surrounding the actual sensor reading we
got.
配图
We must try to reconcile our guess about the readings we’d see based
on the predicted state (pink) with a different guess based on our sensor
readings (green) that we actually observed.
If we have two probabilities and we want to know the chance that both
are true, we just multiply them together.
The mean of this distribution is the configuration for which
both estimates are most likely, and is therefore the
best guess of the true configuration given all the
information we have.
Combining Gaussians
Kalman Filter Information
Flow
Wrapping up
卡尔曼滤波用于线性系统,扩展卡尔曼滤波适用于非线性系统。
This will allow you to model any linear system
accurately. For nonlinear systems, we use the extended Kalman
filter, which works by simply linearizing the predictions and
measurements about their mean.
In general, the major difference between a workflow engine and a
state machine lies in focus. In a workflow engine, transition to the
next step occurs when a previous action is completed, whilst a state
machine needs an external event that will cause branching to the next
activity. In other words, state machine is event driven and workflow
engine is not.
State machine is a good solution if your system is not very complex.
You may implement it if you are capable of drawing all the possible
states as well as the events that will cause transitions to them. In
general, state machines work well for network protocols or some of the
embedded systems.
Workflow engine implementation is a good way of managing business
processes. It is the right solution for task allocation, CRM and other
complex systems. All in all, its ultimate goal is to improve business
processes and company’s efficiency. That is why it perfectly suits for
business process automation.
根据 官方网站 介绍,CLIPS
(the C Language Integrated Production System) 于 1984
年由美国航空航天局约翰逊空间中心 (NASA’s Johnson Space Center)
推出,意在克服 LISP 移植性差、开发工具和硬件成本高、嵌入性低的缺点。
Developed at NASA’s Johnson Space Center from 1985 to 1996, the C
Language Integrated Production System (CLIPS) is a rule-based
programming language useful for creating expert systems and other
programs where a heuristic solution is easier to implement and maintain
than an algorithmic solution. Written in C for portability, CLIPS can be
installed and used on a wide variety of platforms. Since 1996, CLIPS has
been available as public domain software.
CLIPS 是一个基于 Rete 算法 的前向推理语言,用标准 C
语言编写。它具有高移植性、高扩展性、强大的知识表达能力和编程方式以及低成本等特点。
前向推理 (又叫正向推理,前向链接) 是使用推理引擎 (inference engine)
的主要方法之一,是在专家系统 (expert systems),业务和生产规则系统
(business and production rule systems) 上广泛应用的策略。
Forward chaining (or forward reasoning) is one of the two main
methods of reasoning when using an inference engine and can be described
logically as repeated application of modus ponens. Forward chaining is a
popular implementation strategy for expert systems, business and
production rule systems. The opposite of forward chaining is backward
chaining.
Forward chaining starts with the available data and uses inference
rules to extract more data (from an end user, for example) until a goal
is reached. An inference engine using forward chaining searches the
inference rules until it finds one where the antecedent (If clause) is
known to be true. When such a rule is found, the engine can conclude, or
infer, the consequent (Then clause), resulting in the addition of new
information to its data. Inference engines will iterate through this
process until a goal is reached.
前向推理应用规则从前提 (premises) 应用到结论
(conclusions)。目前,它使用暴力算法 (brute force
algorithm),随机选择来源(source)和规则,应用规则以得出结论,重新插入结论作为新的来源
(source),并迭代上述过程直到达到停止标准 2。
The forward chainer applies rules from premises to conclusions. It
currently uses a rather brute force algorithms, select sources and rules
somewhat randomly, apply these to produce conclusions, re-insert them
are new sources and re-iterate till a stop criterion has been met.
Rete has become the basis for many popular rule engines and expert
system shells, including Tibco Business Events, Newgen OmniRules, CLIPS,
Jess, Drools, IBM Operational Decision Management, OPSJ, Blaze Advisor,
BizTalk Rules Engine, Soar, Clara and Sparkling Logic SMARTS.
The system covers multilane and single-lane autonomous driving in a
hierarchical manner: - 第一级:变道选择。The top layer
of the system is a multilane strategy that handles
lane-change scenarios by comparing lane-level
trajectories computed in parallel.
第二级:车道内的轨迹优化和速度优化。Inside the lane-level trajectory
generator, it iteratively solves path and speed optimization based on a
Frenet frame.
For path and speed optimization, a combination of dynamic
programming and spline-based quadratic programming is proposed to
construct a scalable and easy-to-tune framework to handle traffic rules,
obstacle decisions and smoothness simultaneously.
In the figure, the HD map module provides a high-definition map that
can be accessed by every on-line module. Perception and localization
modules provide the necessary dynamic environment information, which can
be further used to predict future environment status in the prediction
module. The motion planning module considers all information to generate
a safe and smooth trajectory to feed into the vehicle control
module.
1 2 3 4 5 6
graph LR A[safety]-->B(traffic regulations) A-->C(range coverage) A-->D(cycle time efficiency) A-->E(emergency safety) C-->F(we aim to provide a trajectory with at least an eight second or two hundred meter motion planning trajectory)
In motion planner, safety is always the top priority. We consider
autonomous driving safety in, but not limited to, the following aspects:
traffic regulations, range coverage, cycle time efficiency and emergency
safety.
In addition to safety, passengers’ ride experience is also important.
The measurement of ride experience includes, but is not limited to,
scenario coverage, traffic regulation and comfort.
Typically, a multilane strategy should cover both nonpassive and
passive lane-change scenarios. * In EM planner, a nonpassive lane-change
is a request triggered by the routing module for the purpose of reaching
the final destination. * A passive lane change is defined as an ego car
maneuver when the default lane is blocked by the dynamic
environment.
We propose a parallel framework to handle both passive and nonpassive
lane changes. For candidate lanes, all obstacles and environment
information are projected on lane-based Frenet frames. Then, the traffic
regulations are bound with the given lane-level strategy. Under this
framework, each candidate lane will generate a best-possible trajectory
based on the lane-level optimizer. Finally, a cross-lane trajectory
decider will determine which lane to choose based on both the cost
functional and safety rules.
Path-Speed Iterative
Algorithm
大多数自动驾驶软件运动规划的做法是,沿着车道参考线 (reference
line,通常是从高精度地图中得到车道中心线) 把单车道问题转化为 Frenet
frames with time (SLT) 问题。其中,S 指 Frenet 坐标系下的纵向,L
指横向,T 指代时间。
Many autonomous driving motion planning algorithms are developed in
Frenet frames with time (SLT) to reduce the planning dimension with the
help of a reference line.
如何在 Frenet 中找到最优轨迹是一个 3D (S+L+T)
约束优化问题,文章中提到两种做法的路线之争。在我看来,现在工业界主流前沿的做法是第二种,第一种正在被逐渐淘汰。
Finding the optimal trajectory in a Frenet frame is essentially a 3D
constrained optimization problem. There are typically two types of
approaches: direct 3D optimization methods and the path-speed decoupled
method. * [方法一:无脑优化采样] Direct methods attempt to find the
optimal trajectory within SLT using either trajectory sampling or
lattice search. + These approaches are limited by their search
complexity, which increases as both the spatial and
temporal search resolutions increase. To qualify the
time consumption requirement, one has to compromise with increasing the
search grid size or sampling resolution. Thus, the generated trajectory
is suboptimal.
[方法二:path-speed 解耦,先求 path,再解 speed] The path-speed
decoupled approach optimizes path and speed separately.
Path optimization typically considers static obstacles. Then, the speed
profile is created based on the generated path. It is possible
that the path-speed approach is not optimal with the appearance of
dynamic obstacles. However, since the path and speed are
decoupled, this approach achieves more flexibility in both path and
speed optimization.
一个负责问题,如果一旦可以分为几个小问题,或者之前已经解决的问题,那么问题整体难度就会降低下来。
Path-speed decoupled
framework
EM planner 分别迭代优化 path 和 speed。在 path
优化中,利用上一帧的速度 (speed profile from the last cycle)
来预估和低速对象障碍物的交互,然后基于生成的 path 来优化速度。
注意,实践中要减少对上一次规划轨迹的依赖。
EM planner optimizes path and speed iteratively. The speed profile
from the last cycle is used to estimate interactions with
oncoming and low-speed dynamic
obstacles in the path optimizer. Then, the generated path is
sent to the speed optimizer to evaluate an optimal speed profile.
For high-speed dynamic dynamic obstacles, EM planner prefers a
lane-change maneuver rather than nudging for safety reasons.
Decisions and Traffic
Regulations
EM planner 先做出决策 (make
decisions),再规划轨迹。决策可以输出清晰的自车意图,把非凸问题约束为凸问题,不仅减少寻找最优轨迹的搜索空间,而且允许使用凸优化问题的优化方法。
In Apollo EM planner, we make decisions prior to providing a smooth
trajectory. The decision process is designed to make on-road intentions
clear and reduce the search space for finding the optimal
trajectory.
决策的路线之争。
Many decision-included planners attempt to generate vehicle states as
the ego car decision. These approaches can be further divided into
hand-tuning decisions and model-based decisions. *
[方法一:手写规则,扩展性差] The advantage of hand-tuning decision is
its tunability. However, scalability is its limitation. In some cases,
scenarios can go beyond the hand-tuning decision rule’s description. +
When considering dozens of obstacles, the decision behavior is difficult
to be accurately described by a finite set of ego car states.
[方法二:基于模型的决策] The model-based decision approaches
generally discretize the ego car status into finite
driving statuses and use data-driven methods to tune the model.
Targeting level-4 autonomous driving, a decision module shall include
both scalability and
feasibility.
* Scalability is the scenario expression ability (i.e., the autonomous
driving cases that can be explained). + 不要过拟合 (over-fit) 一个
issue,适用性差。 * For feasibility, we mean that the generated decision
shall include a feasible region in which the ego car can maneuver
within dynamic limitations. + Both hand-tuning and
model-based decisions do not generate a collision-free trajectory to
verify the feasibility. * 同意,decision
层并不会考虑是否能够生成轨迹,所以有些决策是无效的。
划重点:EM planner
的做法是先生成初略的轨迹来表示交互意图(不受限于障碍物数量);然后,生成一个有约束的凸走廊
(a convex feasible
space),用凸优化的方法来求解优化轨迹。 * 目前,ABC
是先生成决策,然后决策作为约束,在 ST planner 中搜索粗略的轨迹,和 EM
的做法不一致。
In EM planner’s decision step, we describe the behavior differently.
* First, the ego car moving intention is described by a rough
and feasible trajectory. Then, the interactions between
obstacles are measured with this trajectory. + This feasible
trajectory-based decision is scalable even when scenarios become more
complicated. * Second, the planner will also generate a convex
feasible space for smoothing spline parameters
based on the trajectory. + A quadratic-programming-based smoothing
spline solver could be used to generate smoother path and speed profiles
that follow the decision. This guarantees a feasible and smooth
solution.
In the first E-step, obstacles are projected on the lane
Frenet frame. This projection includes both static obstacle
projection and dynamic obstacle projection. *
静态障碍物的投影:Static obstacles will be projected
directly based on a Cartesian-Frenet frame transformation. *
动态障碍物的投影(负责):Considering the previous cycle planning
trajectory, we can evaluate the estimated dynamic obstacle and ego car
positions at each time point. + The overlap of dynamic
obstacles and the ego car at each time point will be mapped in the
Frenet frame.
For safety considerations, the SL projection of dynamic obstacles
will only consider low-speed traffic and oncoming obstacles. For
high-speed traffic, EM planner’s parallel lane-change strategy will
cover the scenario.
Although we projected obstacles on SL and ST frames, the optimal path
and speed solution still lies in a non-convex space. Thus, we use
dynamic programming to first obtain a rough solution; meanwhile,
this solution can provide obstacle decisions such as nudge,
yield and overtake.
基于针对障碍物的决策,生成一个凸区域 (convex hull,凸包),可供 QP
算法求解。
We use the rough decision to determine a convex hull for the
quadratic-programming-based spline optimizer.
通过优化器在凸空间内求解。
The optimizer can find solutions within the convex hull.
The SL projection is based on a G2 (continuous curvature derivative)
smooth reference line.
如何把动态障碍物转化到SL中?
参考上一次的自车规划轨迹 (last cycle
trajectory),可以得到自车在指定时间上位于 S
方向上的位置,来预估和障碍物预测轨迹的相交处 (interactions)。 > For
dynamic obstacles, we mapped the obstacles with the help of the last
cycle trajectory of the ego car. The last cycle’s moving trajectory is
projected on the Frenet frame to extract the station direction speed
profile. This will provide an estimate of the ego car’s station
coordinates given a specific time. The estimated ego
car station coordinates will help to evaluate the dynamic obstacle
interactions. + Once an ego car’s station coordinates have interacted
with an obstacle trajectory point with the same time, a shaded area on
the SL map will be marked as the estimated interaction with the dynamic
obstacle.
ST 投影帮助我们评估自车的速度轮廓 (speed profile)。因为在 ST
图中抠除障碍物占据的空间 (shaded
area),剩余的空间其实是速度可行区间。
ST projection helps us evaluate the ego car’s speed profile. The
remaining region is the speed profile feasible region.
The M-step path optimizer optimizes the path profile in the Frenet
frame. * This is represented as finding an optimal function of lateral
coordinate w.r.t. station coordinate in nonconvex SL space (e.g.,
nudging from left and right might be two local optima). * The path
optimizer includes two steps: dynamic-programming-based path
decision and spline-based path planning.
The dynamic programming path step provides a rough path profile with
feasible tunnels and obstacle nudge
decisions.
The step includes a lattice sampler, cost function and dynamic
programming search. + Lattice Sampler: The lattice
sampler is based on a Frenet frame. Multiple rows of points are
first sampled ahead of the ego vehicle. Points between different rows
are smoothly connected by quintic polynomial edges. +
撒点的做法来搜索粗略路线,使用五次多项式来拟合平滑路线。 + Cost
Function: Each graph edge is evaluated by the summation
of cost functionals. We use information from the SL projection, traffic
regulations and vehicle dynamics to construct the functional. +
从障碍物,交通规则和车辆动力学三方面来计算每个连接边(两个 lattice point
的连接线)的代价。此处略过 cost 函数的设计。 + Dynamic Programming
Search: Edge costs are used to select a candidate path with the
lowest cost through a dynamic programming search. The
candidate path will also determine the obstacle
decisions.
The spline QP path step is a refinement of the dynamic programming
path step. In a dynamic programming path, a feasible tunnel is generated
based on the selected path. Then, the spline-based QP step will generate
a smooth path within this feasible tunnel.
The spline QP path is generated by optimizing an objective function
with a linearized constraint through the QP spline solver.
目标函数组成
目标函数由平滑代价和引导线代价组成,其中引导线是上一步的 DP
path。
The objective function of the QP path is a linear
combination of smoothness costs and guidance line cost. * The
guidance line in this step is the DP path. The guidance line
provides an estimate of the obstacle nudging distance.
上述目标函数在 nudge 障碍物的距离和平滑性中做了平衡和取舍。
The objective function describes the balance between nudging
obstacles and smoothness.
The constraints in the QP path include boundary constraints and
dynamic feasibility. These constraints are applied on f(s), f’(s) and
f’’(s) at a sequence of station coordinates s0, s1,
..., sn.
在 EM planner 中,使用自行车模型 (bicycle model)
来考虑自车的动力学特性;在规划阶段,把车辆模型简化为自行车模型,是一种比较通用的做法。
In EM planner, the ego vehicle is considered under the bicycle
model.
左上角约束推导图
上面的操作和近似转换是做什么呢?在横向 (lateral direction)
约束求解中,l = f(s),因为 sin 不是线性的函数,所以使用 f(s)
的导数来替代 sin
函数。在允许一定误差的情况下,把一个非线性函数,转化为线性约束 (linear
constraints) 问题。
To keep the boundary constraint convex and linear, we add two half
circles on the front and rear ends of the ego car.
Since all constraints are linear with respect to spline parameters, a
quadratic programming solver can be used to solve the problem very fast.
* In addition to the boundary constraint, the generated path shall match
the ego car’s initial lateral position and derivatives. +
实现细节注意点:考虑车辆的初始状态。
M-Step DP Speed Optimizer
在 ST 图中,使用 DP 算法生成一个速度轮廓 (speed profile),即 v =
S(t)。
The speed optimizer generates a speed profile in the ST graph, which
is represented as a station function with respect to time S(t).
在 ST graph 中找最优 speed profile 是一个复杂的非凸问题。我们使用
dynamic programming 和 spline quadratic programming 在 ST
图中寻找一个平滑的速度轮廓 (非最优)。
We use dynamic programming combined with spline quadratic programming
to find a smooth speed profile on the ST graph.
DP speed 框架
The DP speed step includes a cost functional, ST graph grids and
dynamic programming search. The generated result includes a
piecewise linear speed profile, a feasible tunnel and
obstacle speed decisions.
待补充,obstacle speed decisions 是什么形式的决策呢?
首先,对整个 ST 图进行网格化处理,包括对障碍物进行网格化分割。 >
obstacle information is first discretized into grids on the ST
graph.
A piecewise linear speed profile function is represented as S = (s0,
s1, ..., sn) on the grids.
Cost function 由三部分组成: - Velocity keeping cost: * This term
indicates that the vehicle shall follow the designated speed when there
are no obstacles or traffic light restrictions present. V^ref describes
the reference speed, which is determined by the road speed limits,
curvature and other traffic regulations. - Smoothness cost: * The
acceleration and jerk square integral describes the smoothness of the
speed profile. - Total obstacle cost: * The distances
of the ego car to all obstacles are evaluated to determine the total
obstacle costs.
DP 搜索时要注意车辆动力学限制;同时,可以根据运动学约束做剪枝
(pruning) 操作。
The dynamic constraints include acceleration, jerk limits and
a monotonicity constraint since we require that the generated
trajectories do not perform backing maneuvers when driving on the road.
* Some necessary pruning based on vehicle dynamic constraints is also
applied to accelerate the process.
知识点,如何把导数问题简化为有限差分问题。
ai = ((si-si-1)/dt - (si-1 - si-2)/dt)/dt。
M-Step QP Speed Optimizer
因为锯齿形的线性速度轮廓不能满足运动学特性,所以使用 spline QP step
去填补这个空缺 (fill this gap)。
Since the piecewise linear speed profile cannot satisfy dynamic
requirements, the spline QP step is needed to fill this gap.
For both the path and speed optimizers, we find that piecewise
quintic polynomials are good enough. The spline generally contains 3 to
5 polynomials with approximately 30 parameters. Thus, the
quadratic programming problem has a relatively small objective function
but large number of constraints.
In addition to accelerating the quadratic programming, we use
the result calculated in the last cycle as a hot start. *
注意,在 EM
文章中,优先使用上一次的规划轨迹,不仅可以提高求解效率,同时容易和上一次的决策保持一致。
因为使用上一次的规划轨迹来求解,QP 问题可以平均在 3ms 内求解。
The QP problem can be solved within 3 ms on average, which satisfies
our time consumption requirement.
DP and QP alone both have their limitations in the non-convex domain.
A combination of DP and QP will take advantage of the two and reach an
ideal solution.
DP: As described earlier in this manuscript, the DP
algorithm depends on a sampling step to generate candidate
solutions. Because of the restriction of processing time,
the number of sampled candidates is limited by the sampling
grid. Optimization within a finite grid yields a rough
DP solution. In other words, DP does not necessarily, and in
almost all cases would not, deliver the optimal
solution.
For example, DP could select a path that nudges the obstacle from
the left but not nudge with the best distance.
DP 方法受限于采样精度 (求解性能约束),不能找出最优的结果。
QP: Conversely, QP generates a solution based on the convex
domain. It is not available without the help of the DP step.
For example, if an obstacle is in front of the master vehicle, QP
requires a decision, such as nudge from the left, nudge from the right,
follow, or overtake, to generate its constraint. A random or
rule-based decision will make QP susceptible to failure or fall into a
local minimal.
QP 主要是解决凸优化问题,需要 DP 把非凸问题简化为凸优化问题。
目前,ABC's 的 stopping
constraints,并不是输出一个决策,而是输出一个约束到 ST 中,在 ST
中进行决策的优化。从而,决策上的约束,可以把一个非凸问题化简为凸优化问题。
DP + QP: A DP plus QP algorithm will minimize the limitations of
both: (1) The EM planner first uses DP to search within a grid to reach
a rough resolution. (2) The DP results are used to generate a
convex domain and guide QP. (3) QP is used to search for the
optimal solution in the convex region that most likely contains global
optima.
Although most state-of-the-art planning algorithms are based on
heavy decisions, EM planner is a
light-decision-based planner. It is true that a
heavy-decision-based algorithm, or heavily rule-based algorithm, is
easily understood and explained. The disadvantages are also clear: it
may be trapped in corner cases (while its frequency is closely related
to the complexity and magnitude of the number of rules) and not always
be optimal. * 和 EM planner 相比,目前 ABC 做法的缺陷,在行为决策部分
(reasoner),规则的痕迹太重了。那么,能否引入比较智能的算法或者架构,来解决这类约束呢?这也是自己下一步的努力方向。
* 自动驾驶不能通过重规则 (heavy-decision-based algorithm)
来实现,最好的做法还是通过优化来实现。
这个示例中,进行了两次迭代 (两轮 EM
迭代)。通常,环境越复杂,计算迭代时间越复杂,所以优化问题是一个没有时间收敛上限的问题。
In general, the more complicated the environment is, the the more
steps that may be required.
建议在读论文前,先阅读 Case Study
这一章,了解文章在解决什么问题,以及如何解决这个问题,对文章的实现有初步了解。
COMPUTATIONAL PERFORMANCE
这篇文章把三维 (station-lateral-speed) 的问题,化简为两个二维问题
(station-lateral problem and station-speed
problem),那么大大简化了计算复杂度。也就是,问题复杂度降维了。
Because the three-dimensional station-lateral-speed problem has been
split into two two-dimensional problems, i.e., station-lateral
problem and station-speed problem, the computational complexity
of EM planner has been significantly decreased, and thus, this planner
is very efficient. It takes less than 100 ms on
average.
从问题复杂度 O(n(M+N))
来分析求解效率,可以应用到论文中,具有学术的感觉。但是,为什么是 M
(后续车道) + N (障碍物数量) 呢?
Assuming that we have n obstacles with M candidate path profiles and
N candidate speed profiles, the computational complexity of this
algorithm is O(n(M+N)).
One critical issue in autonomous driving vehicles is the challenge of
safety vs. passability. A strict rule increases the safety of the
vehicle but lowers the passability, and vice versa.
EM planner described in this manuscript is also designed to solve the
inconsistency of potential decisions and planning,
while it also improves the passability of autonomous driving vehicles. *
通过复用上一次的决策 (hot
start),如果环境不发生大的变化,决策容易和上一次的决策保持一致。 *
决策不稳定,也是目前 ABC 遇到的常见问题之一。
EM planner 把一个 3D 问题化简为 2 个 2D
问题,化繁为简,降低了问题难度,提高了求解效率。
EM planner significantly reduces computational complexity by
transforming a three-dimensional station-lateral-speed problem into two
twodimensional station-lateral/station-speed problems. It could
significantly reduce the processing time and therefore increase the
interaction ability of the whole system.
The spline QP path and speed optimizer uses the same constrained
smoothing spline framework. In this section, we formalize the smoothing
spline problem within the quadratic programming framework and linearized
constraints. Optimization with a quadratic convex objective and
linearized constraints can be rapidly and stably solved.
A purely peer-to-peer version of electronic cash would allow online
payments to be sent directly from one party to another without going
through a financial institution.
论文的主要成就:使用点对点的技术,在不依赖第三方交易平台 (financial
institution, a trusted third party)
的情况下,利用区块链技术,实现了去中心化的目的,解决了双重支付
(double-spending) 问题。
Digital signatures provide part of the solution, but the main
benefits are lost if a trusted third party is still required to prevent
double-spending. We propose a solution to the double-spending problem
using a peer-to-peer network.
What is needed is an electronic payment system based on cryptographic
proof instead of trust, allowing any two willing parties to transact
directly with each other without the need for a trusted third party.
本文提出的比特币系统,具有以下三个优点: -
基于密码学原理,而不是信任来建立支付系统。 * based on cryptogtaphic
proof instead of trust - 不需要引入第三方金融机构。 * without third
party financial institutions - 交易不可逆。 * no reverse
transactions
Transactions
我们定义一枚电子货币就是一条数字签名链。 > We define an electronic
coin as a chain of digital signatures.
Each owner transfers the coin to the next by digitally signing a hash
of the previous transaction and the public key of the next owner and
adding these to the end of the coin. A payee can verify the signatures
to verify the chain of ownership.
平均所需工作量将随所需 0
比特呈指数级增长,而验证却只需执行一次哈希。一般情况下,10 min
求解出一次答案,也就是挖矿的过程。
The proof-of-work involves scanning for a value that when hashed,
such as with SHA-256, the hash begins with a number of zero bits. The
average work required is exponential in the number of zero bits required
and can be verified by executing a single hash.
POW 约束:当前区块包含了上一区块的 hash
值,从而形成带时间戳、可验证的链式结构;一旦消耗了 CPU
算力使区块满足了工作量证明,那么除非重做这个工作否则就无法更改区块。由于后面的区块是链接在这个区块后面的,改变这个区块将需要重做所有后面的区块。
Once the CPU effort has been expended to make it satisfy the
proof-of-work, the block cannot be changed without redoing the work. As
later blocks are chained after it, the work to change the block would
include redoing all the blocks after it.
POW 特点:按 CPU 投票,解决了多数决定中的确定方式问题 (the problem of
determining representation in majority decision
making)。最长的链代表了多数决定,因为有最大的计算工作量证明的精力投入到这条链上。
Proof-of-work is essentially one-CPU-one-vote. The majority decision
is represented by the longest chain, which has the greatest
proof-of-work effort invested in it.
To compensate for increasing hardware speed and varying interest in
running nodes over time, the proof-of-work difficulty is determined by a
moving average targeting an average number of blocks per hour. If
they're generated too fast, the difficulty increases.
Network
分布式网络的运行步骤
新交易向所有节点广播。
每个节点将新交易收集到一个区块。
每个节点为它的区块寻找工作量证明。
当一个节点找到了工作量证明,就向所有节点广播这个区块。
节点只有在区块内所有交易都是有效的且之前没有被支付的情况下接收这个区块。
节点通过使用这个区块的哈希值作为上一个哈希值,在链中创建下一个区块的方式表示对这个区块的接受。
根据规定,节点总是认为最长的链为正确的并持续致力于延长它。
Nodes always consider the longest chain to be the correct one and
will keep working on extending it.
网络的鲁棒性
新交易的广播不必到达所有的节点。
只要到达一些节点,不久就会进入到一个区块。
区块广播也是能容忍消息丢失的。
如果一个节点没有收到某个区块,它将在收到下一个区块时发现它丢失了一个区块然后去请求这个区块。
New transaction broadcasts do not necessarily need to reach all
nodes. As long as they reach many nodes, they will get into a block
before long. Block broadcasts are also tolerant of dropped messages. If
a node does not receive a block, it will request it when it receives the
next block and realizes it missed one.
Incentive
激励组成
我们约定,区块中的第一笔交易是特殊的交易,奖励区块创建者一枚属于 TA
的新货币
(挖矿收益)。这就增加了对支持网络的节点的激励,并提供了一种分发货币到流通领域的方法。
* BTC 消耗 CPU 计算时间和电力 (CPU time and electricity)
资源来稳定地增加新货币,替代了中心发币机构。
By convention, the first transaction in a block is a special
transaction that starts a new coin owned by the creator of the block.
This adds an incentive for nodes to support the network, and provides a
way to initially distribute coins into circulation, since there is no
central authority to issue them.
The incentive can also be funded with transaction fees. If the output
value of a transaction is less than its input value, the difference is a
transaction fee that is added to the incentive value of the block
containing the transaction.
激励会有助于鼓励节点保持诚实,遵守规则比破坏系统和他自己财产的有效性更有利。
The incentive may help encourage nodes to stay honest. He ought to
find it more profitable to play by the rules, such rules that favour him
with more new coins than everyone else combined, than to undermine the
system and the validity of his own wealth.
A block header with no transactions would be about 80 bytes. If we
suppose blocks are generated every 10 minutes, 80 bytes * 6 * 24 * 365 =
4.2MB per year.
It is possible to verify payments without running a full network
node. A user only needs to keep a copy of the block headers of the
longest proof-of-work chain, which he can get by querying network nodes
until he's convinced he has the longest chain, and obtain the Merkle
branch linking the transaction to the block it's timestamped in.
He can't check the transaction for himself, but by linking it to a
place in the chain, he can see that a network node has accepted it, and
blocks added after it further confirm the network has accepted it.
As such, the verification is reliable as long as honest nodes control
the network, but is more vulnerable if the network is overpowered by an
attacker.
为了更加独立的安全性以及更快的支付确认,收款频繁的公司可能仍需运行他们自己的节点。
Businesses that receive frequent payments will probably still want to
run their own nodes for more independent security and quicker
verification.
To allow value to be split and combined, transactions contain
multiple inputs and outputs. Normally there will be either a
single input from a larger previous transaction or multiple inputs
combining smaller amounts, and at most two outputs: one
for the payment, and one returning the change, if any, back to the
sender.
The necessity to announce all transactions publicly precludes this
method, but privacy can still be maintained by breaking the flow of
information in another place: by keeping public keys anonymous. The
public can see that someone is sending an amount to someone else, but
without information linking the transaction to anyone.
又一层隐私保障
作为额外的防火墙,对每笔交易使用新密钥 (new key
pair) 对可以防止他们被关联到一个共同的拥有者。
As an additional firewall, a new key pair should be used for each
transaction to keep them from being linked to a common owner.
Some linking is still unavoidable with multi-input transactions,
which necessarily reveal that their inputs were owned by the
same owner. The risk is that if the owner of a key is revealed,
linking could reveal other transactions that belonged to the same
owner.
节点使用 CPU
算力来投票,通过致力于延长有效区块来表达对其接受,通过拒绝在无效区块上工作来表达对其抵制。任何需要的规则和激励都可通过这个共识机制来加强。
We have proposed a system for electronic transactions without relying
on trust. We started with the usual framework of coins made from digital
signatures, which provides strong control of ownership, but is
incomplete without a way to prevent double-spending. To solve this, we
proposed a peer-to-peer network using proof-of-work to record a public
history of transactions that quickly becomes computationally impractical
for an attacker to change if honest nodes control a majority of CPU
power. The network is robust in its unstructured simplicity. Nodes work
all at once with little coordination. They do not need to be identified,
since messages are not routed to any particular place and only need to
be delivered on a best effort basis. Nodes can leave and rejoin the
network at will, accepting the proof-of-work chain as proof of what
happened while they were gone. They vote with their CPU power,
expressing their acceptance of valid blocks by working on extending them
and rejecting invalid blocks by refusing to work on them. Any needed
rules and incentives can be enforced with this consensus mechanism.
我的评价:BTC
系统是站在巨人的肩膀上实现,是一种去中心化,分布式的的经济学。首先,数字签名货币体系是已经通用的,但是有明显的双重支付缺陷没有被很好地解决。基于工作量证明的已有研究,作者提出
P2P 交易记账系统,根据 CPU 算力来模拟投票 和
筛选出诚实节点,并且把最长的工作量证明链作为交易账单;各个节点通过致力于延长有效区块来表达对其接受,通过拒绝在无效区块上工作来表达对其抵制;通过挖矿奖励的形式,鼓励了数字货币交易的普及,以及各节点的记账积极性。
在论文中,Waymo case by case 地概述了其他人类驾驶员的 “违反道路规则”
是如何导致 “严重” 碰撞的。
专业名词介绍
automated vehicles (AVs)
automated driving system (ADS)
operational design domain (ODD)
Abstract
这份报告总结了 Waymo 在凤凰城 (Phoenix) 测试区域的 610
万英里的自动驾驶测试数据,包括有车上安全员监管 ( trained operator behind
the steering wheel) 的自动驾驶,和 65000 英里的没有安全驾驶员无人驾驶
(driverless operation)。 > The data presented in this paper
represents more than 6.1 million miles of automated driving in the
Phoenix, Arizona metropolitan area, including operations with a trained
operator behind the steering wheel from calendar year 2019 and 65,000
miles of driverless operation without a human behind the steering wheel
from 2019 and the first nine months of 2020.
报告中承认,这段测试期间 Waymo 自动驾驶汽车卷入了 18
起真实的碰撞事故和 29
次仿真事故(被安全驾驶员及时接管,但是在模拟器中发生碰撞事故),所幸均没有造成致命伤害。
> There were 47 contact events that occurred over this time period,
consisting of 18 actual and 29 simulated contact events, none of which
would be expected to result in severe or life-threatening
injuries
Waymo
表示,绝大多数事故都和人类驾驶员的不守规则和其他错误相关;由其他司机不谨慎行为诱发的事故频率清楚地提醒人们,只要自动驾驶汽车与人类司机共享道路,避免碰撞就是一大挑战。
> Nearly all the events involved one or more road rule violations or
other errors by a human driver or road user. > The presence of
collisions that resulted from challenging situations induced by other
drivers serves as a reminder of the limits of AV collision avoidance as
long as AVs share roadways with human drivers.
在 Waymo
看来,报告不只是向公众公开测试里程和事故,更是做了一个向公众分享自动驾驶行驶安全的一个例子。
> The long-term contributions of this paper are not only the events
and mileages shared, but the example set by publicly sharing this type
of safety information.
报告的目的是公开更多数据,来尽力提高公众对自动驾驶车辆的信心和接受程度
(acceptance)。 > The purpose of this paper is to make available
relevant data to promote awareness and discussions that ultimately
foster greater public confidence in AVs.
Public Road Testing
在测试初期,为了保证 AVs
在公开道路测试时的安全和行为合理,会有经过培训的驾驶员坐在驾驶员的位置,随时准备接管车辆。
> In order to perform initial public road testing of AVs in a safe
and responsible manner, trained vehicle operators are seated in the
driver’s seat and can take over the driving task at any time.
反现实的仿真用来预测自车在接管后的一段时间内的表现,给我们提供如果安全员没有接管,那么自车会发生什么的视角。
> Counterfactual disengagement simulation is used to represent the
predicted vehicle response for a brief period (seconds) after
disengagement, and the simulation outcome provides insight into what
could have happened had the trained operator not intervened. > MC:
只能提供极短时间的仿真,否则容易和真实世界背离。另外,需要有精细的模型,可以预期如果没有接管发生,交通参与者的行为。
反事实的接管仿真可以独立使用 (individually) 也可以聚合使用 (in
aggregate)。 > The outcomes of counterfactual disengagement
simulations are used both individually and in aggregate.
独立仿真时间:场景库的虚拟仿真,可以作为评估软件开发的测试集。 >
Individual counterfactual disengagement simulation: If the simulation
outcome reveals an opportunity to improve the behavior of the ADS, then
the simulation is used to develop and test changes to software
algorithms. The disengagement event is also added to a library of
scenarios, so that future software can be tested against the scenario.
>
在细分领域,自动驾驶的策略会随着接管场景而发生调整和变化,容易造成回滚,而这些场景集合可以作为软件的回滚测试的一部分。
聚合使用:评估 AVs 的路测表现。 > At an aggregate level, Waymo
uses results from counterfactual disengagement simulations to produce
metrics relevant to the AV’s on-road performance.
软件进化带来的仿真不可复现性问题 > Waymo’s models will
continue to evolve, and even for these brief simulations, future models
may result in different simulated outcomes.
Aims and Contributions of
this Paper
报告包括在 610 万英里测试中的事故总计和事故描述
(包括真实的事故和实际接管但发生仿真事故)。这部分里程,相当于美国普通持证司机
500 多年的驾驶里程。 > This paper includes safety data in the form of
event counts and event descriptions from over 6.1 million miles of
driving conducted in the Waymo Driver’s driverless ODD. This mileage
figure represents over 500 years of driving for the average U.S.
licensed driver.
本文提供了两种信息:一种是在或无安全驾驶员情况下的真实碰撞(actual
contact
event);一种是驾驶员接管,但是在后续的仿真中发生碰撞的,但是因为安全员接管实际没有发生碰撞。
> For these miles, this paper provides information regarding
every actual contact event that vehicles were involved in during
driverless operation with and without trained operators, as well
as
events in which the vehicle’s trained operator disengaged and
subsequent counterfactual simulation resulted in any contact between the
AV and the other agent, had the disengagement not occurred
Waymo 自动驾驶软件的最高速度是 45 英里每小时,换算成公里数是
72.4km/h。除了大雨和沙尘暴天气,会在白天和夜间进行无人驾驶测试。 >
The ODD includes roadways with speed limits up to and including 45 miles
per hour. Driverless operations occur at all times day and night, except
during inclement weather including heavy rain and dust storms.
报告分享的数据来源于两方面: - 无人驾驶(Driverless
operation),即车上没有驾驶员,在整个过程中由自动驾驶系统 (automated
driving system) 控制车辆。 > Driverless operation, in which the
automated driving system controls the vehicle for the entire trip
without a human driver behind the wheel or otherwise being available to
assume any part of the driving task.
> MC: 这种模式下,在 2019 年初到 2020 年九月底的测试里程是 6.5
万英里。
由驾驶员的自动驾驶(Self-driving with trained
operators):虽然由自动驾驶系统控制车辆,但是车上有安全驾驶员可以随时接管车辆。
> Self-driving with trained operators , in which the automated
driving system controls the vehicle but there is a trained vehicle
operator in the driver’s seat who can disengage and take over the
driving task.
> MC: 这种模式下,2019 年全年的测试里程是 6.1
百万里程。提供一整年的测试数据,可以控制和规避潜在的季节影响
(controlling for potential seasonality
effects)。在评估自车表现时,不能忽略季节影响,比如秋天有落叶误感,方向盘急打要比冬季严重。
Data from Actual
Collisions and Minor Contacts
数据包括自动驾驶 (self-driving with trained operators mode)
或无人驾驶 (driverless mode) 模式下每一个真实碰撞 (actual collision)
和小事故 (minor contact event),甚至包括行人撞上静止自车的事故。 >
This definition encompasses not only every severity of collision, but
also events such as a pedestrian walking into the side of the stationary
AV.
Data from
Counterfactual (“What If”) Simulation
Simulation of
the AV motion post-disengagement
接管后的仿真 (post-disengage simulation) 第一步,就是仿真自车的表现
(AV’s counterfactual post-disengage
motion)。这样的仿真比较简单,容易快速实现。 > The first step in
post-disengage simulation is therefore to simulate the AV’s
counterfactual post-disengage motion. > This is performed by
providing a simulation running Waymo self-driving software with the AV’s
pre-disengage position, attitude, velocity, and acceleration along with
the AV’s recorded sensor observations and simulating the response of the
software and resulting motion of the Waymo vehicle.
检测是否和其他交通参与者有碰撞,重叠的位置 (overlapping
positions) 意味着有潜在的碰撞 (potential collision)。 > Overlapping
positions indicate a potential collision. After the AV’s post-disengage
motion is simulated, a check is performed to determine if the simulated
positions of the AV overlap at any point with the recorded positions of
other agents.
仿真第二步:在接管和仿真两种情况下,自车的行为存在不一致
(比如位置和速度不一样),那么就会影响其他参与者的行为,所以做仿真时,参与者的行为可能和实际不符,需要为其他交通参与者重新建模
(modeling the behavior of other
agents)。这是比较困难的,需要有比较丰富的模型和交互设计。 > This may
not be realistic in cases where the other agents would
likely have responded differently to the AV’s counterfactual simulated
motion than they did to the AV’s actual post-disengage motion. In such
cases, further simulation is required.
为其他交通参与者长时间建模是比较有挑战性的,但是在接管后的短时间内建立冲突避免
(conflict-avoidance) 或避障行为 (collision-avoidance) 是可行的做法。
> While modeling agent behavior over long periods of time is
challenging, understanding plausible conflict-avoidance or
collision-avoidance behavior over the short time horizon following a
disengagement is a more feasible task.
Waymo 使用人类避障行为模型 (human collision avoidance behavior
models)
来反映短期内障碍物的表现;可以使用离散的多因素(反应时间、刹车和打方向盘的力度)来反映交通参与者可行的反应空间
(the space of plausible reactions)。 > Waymo expresses short-term
agent responses using human collision avoidance behavior models. >
These models aim to capture the responses of human drivers,
motorcyclists, cyclists, and pedestrians to collision avoidance
situations, such as braking by a lead vehicle or being cut-off by
another agent who fails to yield right-of-way. > Because only the
agent’s short-term response needs to be modeled, the space of plausible
reactions to such stimuli can be defined using a discrete set of
factors such as response times to specific inputs and brake or
swerve ability.
因为上述的多因素因环境因人而异(比如反应时间),Waymo 在开发和评估
AV 行为时,使用一个范围来表示可能的人类驾驶表现 (a broad spectrum of
potential human driving performance).
为了透明度和简单性,本文使用确定的模型 (deterministic model)
来对一个给定的输入产生给定的输出。 > Waymo considers a broad spectrum
of potential human driving performance in developing and evaluating the
AV, but for transparency and simplicity, the results reported in this
paper are based on deterministic models that generate a single response
to a given input.
> Other methods can be used to capture a range of possible human
responses, such as probabilistic counterfactual outcomes, but they are
more complex.
Waymo 独有的人类避碰模型是基于现在已有的道路使用者的行为模型
(road user behavior modelling frameworks),并基于人类自然的避碰模型
(naturalistic human collision) 和差点碰撞的数据 (near-collision)
来校正。 > Waymo’s proprietary human collsion avoidance behavior
models are based on existing road user behavior modelling frameworks and
calibrated using naturalistic human collision and near-collision
data.
交通参与者的反应被其刹车和转向性能所限制。Waymo
针对不同类型的交通参与者以及不同的触发场景 (different
stimuli),使用不同的模型。 > The agent’s response is further
constrained by human braking and steering limitations. Waymo uses
different models for different types of agents, including heavy
trucks, pedestrians, and cyclists, and for different stimuli
such as a forward agent braking or an agent emerging from behind an
occlusion.
> MC:
如果单车智能比较高,贴近于人类驾驶员的表现,那么是否可以使用自动驾驶软件的算法模拟车辆的行为;也就是说其他车和自车的表现拟合度比较高,能否使用自车模型来仿真其他车的表现呢?
人类避碰模型的使用场合和条件:当仿真接管后的 AV
轨迹和交通参与者的实际轨迹有重叠,那么就会在接管后的仿真中使用人类避障模型
(human collision avoidance behavior models)。 > Human collision
avoidance behavior models are employed for disengagements in which there
is overlap between the simulated post-disengage trajectory of the AV and
the actual post-disengage trajectory of another agent.
> In these cases, instead of using the agent’s recorded
post-disengage trajectory, the post-disengage trajectory of the other
agent is determined by applying the relevant human collision avoidance
behavior model.
Contact analysis of
simulated collisions
Waymo
仿真分析表明,接管很少会造成实际上的碰撞(大部分是防御性接管)。事实上,超过
99% 的接管没有仿真的接触 (simulated contact) 发生。 > Our simulation
analysis indicates that disengagements would rarely result in contact.
In fact, in more than 99.9% of disengagements, no simulated contact is
found to occur.
> MC: 因为 Waymo
的软件开发程度比较高,才可以有这样的把握;对于初创期的软件,没有充分的道路测试,切不可使用这样的结论。
Waymo
根据伤害可能性、碰撞物体、撞击速度和撞击几何结构分析,以确定某些事故的严重性,。
如何碰撞发生,那么如何确定碰撞的严重程度 (event severity) 呢?Waymo
根据碰撞障碍物的类型 (collision object),相对速度 (impact velocity)
和碰撞位置 (impact geometry) 来确定可能的伤害程度 (likelihood of
injury)。Waymo 使用国家碰撞数据库 (national crash databases)
来为事故严重程度分级 (event severity
category),事件的统计等级分为预计无伤害 (S0) 到可能的严重伤害 (S1、S2 和
S3)。 > This determination categorizes collisions based on likelihood
of injury and is based on the collision object (e.g., other vehicles,
static objects, or vulnerable road users such as pedestrians or
cyclists), impact velocity, and impact geometry.
> Waymo’s methods for determining event severity category are
developed using national crash databases and are periodically refined to
reflect updated data.
Results: Collisions and
Minor Contacts
Collision Categories
上表中的碰撞类型列分类 (collision typology)
是根据美国国家机构的专业分类 (using the Manner of Collision categories
from National Highway Traffic Safety Administration (NHTSA) collision
databases such as the Fatality Analysis Reporting System);
碰撞程度行分类是基于国际标准 ISO 26262
来评估碰撞的严重程度,从没有伤害的 S0 (no injury expected)
到有关键伤害的 S3 (possible critical injuries
expected),碰撞的伤害逐渐增大。 > categorized in rows according to
their collision typology using the Manner of Collision
categories from National Highway Traffic Safety Administration (NHTSA)
collision databases such as the Fatality Analysis Reporting
System.
> columns categorized by estimated event severity using the ISO 26262
severity classes: S0, S1, S2, and S3, ranging from no injury expected
(S0) to possible critical injuries expected (S3). * MC:
虽然中美两国的交通法规和驾驶习惯不同,但是这样的交通事故分类是可以拿来参考的。
Waymo 报告中的碰撞事故中,没有 S2 或 S3 级别事故发生,最严重的事故是
S1 级别 (airbag-deployment-level),有 3 次保护气囊弹出。 > There were
no actual or predicted S2 or S3 events. One actual event involved
deployment of another vehicle’s frontal airbags and the Waymo vehicle’s
side airbags.
Waymo
通过和人类的事故相比较,来表明其自动驾驶软件在减少人员伤亡上的可能性。
> Comparison between these human collision statistics and Waymo event
counts provides insight into the Waymo Driver’s opportunity for reducing
injuries and fatalities due to collisions.
In total, the Waymo vehicle was involved in 20 events involving
contact with another object and experienced 27 disengagements that
resulted in contact in post-disengagement simulation, for a total of 47
events (actual and simulated).
报告以图片形式 (diagrams have been provided),重点关注了 3
个和弱势交通群体的交互事故,以及 8 个有安全气囊弹出的严重事故。 >
Specifically, diagrams have been provided for every actual or simulated
event in which a pedestrian or cyclist was involved (three events) and
every event with actual or simulated airbag deployment for any involved
vehicle (eight events).
Single Vehicle Events
根据 Manner of Collision 的分类标准,交通事故可以分为单车事故 (single
vehicle events) 和多车事故 (multiple-vehicle events)。 > The Manner
of Collision categories within the NHTSA crash database can be broadly
classified as either single vehicle events, which involve a single
motorized vehicle in transport, or multiple-vehicle events, which
involve the impact of at least two motorized vehicles in transport.
Waymo 自动驾驶车辆没有发生偏离车道 (road departure)
和撞上行人的单车事故 (struck a pedestrian or
cyclist);而这类事故在人类驾驶数据中占比约为 60%。 > The Waymo Driver
did not have any events (actual or simulated) in this data that involved
road departure, contact with the roadway environment/infrastructure or
other fixed objects, or rollover. There were also no collisions (actual
or simulated) in which the Waymo Driver struck a pedestrian or
cyclist.
Waymo 在减速或者静止时,被行人或滑板车从右侧撞上。 > In each
instance, the Waymo Driver decelerated and stopped, and a pedestrian or
cyclist made contact with the right side of the
stationary Waymo vehicle while the pedestrian or cyclist was traveling
at low speeds. *
MC:我怀疑自车突然急刹,行人来不及反应而撞上去。
Multiple Vehicle
Events: Reversing Reversing
倒车碰撞 (reversing collisions)
事故经常发生在停车场,很少出现在交警报告数据库中。 > Reversing
collisions (e.g., rear-to-front, rear-to-side, rear-to-rear) are usually
associated with parking lot events or occur on local ( ≤ 25 mph)
roadways and do not frequently appear in databases of police-reported
crashes.
In both scenarios, the Waymo vehicle was stopped or traveling
forward at low speed and the other vehicle was reversing at a
speed of less than 3 mph at the moment of contact to the side of the
Waymo vehicle.
Multiple
Vehicle Events: Same Direction Sideswipe
同方向剐蹭 (sideswipe) 主要发生在变道 (lane changing) 和并道 (lane
merging) 行为时。 > These events are typically experienced during
lane changing or merging maneuvers.
> The Waymo Driver was involved in ten simulated
same direction sideswipe collisions.
Other
vehicle changing lanes, Waymo vehicle straight
The other vehicle changed lanes into the area
occupied by the Waymo vehicle, which resulted in simulated or actual
sideswipe collisions.
Other
vehicle straight, Waymo vehicle changing lanes
In both of these simulations, the Waymo Driver made a lateral
movement in front of a vehicle traveling straight in an
adjacent lane.
Multiple
Vehicle Events: Head-on or Opposite Direction Sideswipe
对头碰撞极易发生严重的交通事故 (high severity)。 > Head-on
collisions have the potential for high severity outcomes.
不能期待驾驶员是理性的,或者一定会有避碰动作:道路情况复杂,你永远不知道司机是什么状态,可能是车辆失控
(impaired) 或疲劳驾驶 (fatigued) 等异常情况。 > The absence
of simulated collision avoidance movement by the other vehicle
reflects our assumption based on driving behavior and circumstances that
the other driver was significantly impaired or fatigued.
如何区别示意图中哪部分是真实,哪部分是仿真的:actual collisions are
represented in color, while simulated ones feature a black and white
background. Solid trajectory lines represent those observed in real
life, while dashed trajectories and shaded poses represent simulated
conditions. Diagrams are intended for visual reference only, and are not
drawn to scale.
Multiple Vehicle Events: Rear
End
追尾碰撞 (rear end collisions) 是最常见的人类驾驶员的碰撞行为。 >
Rear End collisions are the most common collision type in human-driven
collisions.
> The Waymo Driver was involved in fourteen actual and two simulated
rear end collisions
Rear
end struck event group, Waymo vehicle stopped or gradually decelerating
for traffic controls or traffic ahead while traveling straight
上面的事故,是唯一一个发生在没有安全驾驶员的无人驾驶模式下
(driverless mode)。 > Sole collision in driverless mode, without a
trained operator in the driver’s seat.
Rear
end struck event group, Waymo vehicle moving slower while traveling
straight
In the other collision, the Waymo vehicle, traveling straight at the
speed limit, was struck by a vehicle traveling 23 (57-35) mph
over the posted speed limit.
Rear end
struck event group in right turning maneuvers
These collisions occurred while the Waymo was stationary or near
stationary waiting for crossing traffic to clear after having
gradually slowed to account for this traffic.
Rear
end struck event with braking of lead vehicle during left turn
自车在路口左转急刹停 (a deceleration to a near
stop),后面车辆跟车距离不够来不及刹车。 > The remaining rear end
struck collision involved a deceleration to a near stop by the Waymo
Driver while making a left turn in an intersection with a following
vehicle that was traveling at a speed and following distance
that did not allow for the following driver to successfully
respond to the Waymo Driver’s braking.
Rear end striking event
背景车有挑衅行为 (antagonistic
motive),在前方没有障碍物的情况下,故意插入 (cut in) 自车前方后急刹
(braked hard
immediately),自车来不及急刹,从后方撞上。这是唯一一起在仿真中,自车追尾其他车的事故。
> The single simulated event in this grouping involved a vehicle that
swerved into the lane in front of the Waymo and braked
hard immediately after cutting in despite lack of any obstruction ahead
(consistent with antagonistic motive).
Multiple Vehicle Events:
Angled
Angled collisions, those that are typically seen at intersections and
involve crossing or turning vehicles, account for approximately
one quarter of all human-driven collisions and a
similar fraction of the contribution to all human-driven fatalities.
Angled
event group with the other vehicle not yielding to Waymo
right-of-way
The collisions in this grouping (ten simulated, one actual) involve
the Waymo vehicle traveling straight in a designated
lane at or below the speed limit. In all scenarios, the
turning/crossing other vehicle either disregarded traffic controls or
otherwise did not properly yield right-of-way.
路权的定义: > Right-of-way is determined based on the
positions of vehicles prior to contact with respect to the
intersection geometry, roadway markings, and the status
of traffic control devices. Right-of-way is useful as a means of
categorizing some events, but it can be insufficient to
determine collision responsibilities since it does not reflect
all road rule violations (e.g. speeding), nor does it provide
information regarding collision avoidability.
为了减少碰撞风险,Waymo 车辆即使在有路权时也会让行 (yielding)。 >
In order to avoid collisions, the Waymo Driver recognizes that
yielding even when the Waymo vehicle is entitled to right-of-way
may be more appropriate to decrease the risk of collision, for
example when encountering an incautious other agent.
In both instances, when the simulated Waymo Driver became aware of
the other vehicle's intention to enter the travel lane, the simulated
Waymo Driver initiated braking in an attempt to avoid/mitigate impact. *
如果检查到其他车不让行,那么 Waymo 自车会开始刹车来避免碰撞。
上面这个碰撞不常见,需要认真思考下。
左转车辆应该礼让直行车辆,如果不礼让,怎么办呢? Waymo
目前的做法也只能是安全员接管。 > The simulated collision in Figure 9
(Event H) depicts a vehicle making a left turn across the Waymo
vehicle’s travel path. The Waymo Driver’s simulated response to the
vehicle’s action was the initiation of braking just prior to entering
the intersection.
这是最严重的一类碰撞事故 (the most severe collision)。 > It is the
most severe collision (simulated or actual) in the dataset and
approaches the boundary between S1 and S2 classification.
Angled
event group with Waymo vehicle crossing another vehicle’s path
The collisions in this grouping involve four
simulated collisions, where the Waymo Driver was making a right turn
from a rightmost lane that was either splitting to an additional lane,
or had been the result of two lanes merging to one.
Waymo
向右变道时和右侧车道的直行车辆发生碰撞,类似于国内的自车右转,与自行车道的交互。
> In each event, a passenger vehicle attempted to pass the Waymo
vehicle on the right while the Waymo Driver was slowing to make the
right turn with the right turn signal activated.
Discussion
这份报告的目的是:供工业界,政策制定者和公众学习;促进关注和讨论,以及加快公众对自动驾驶的接受程度。
> The goal of this transparency is to contribute to broad learning
with the industry, policymakers, and the public; promote awareness and
discussions; and foster greater public confidence in automated
vehicles.
Of the fifteen angled events, eleven events were characterized by the
other vehicle failing to properly yield right-of-way to the Waymo
vehicle traveling straight at or below the speed limit. > MC:
针对自车有路权,其他车辆不让行的情况,Waymo
也依赖安全驾驶员及时接管。
Collision
Avoidance: Management of Human-Driver-Related Contributing Factors
人类驾驶行为的不稳定性和不安全性,导致了绝大多数的碰撞。几乎所有的事故都是因为其他交通参与者违背交通规则或者交通表现有偏差。
> Humans exhibit a large variation of driving behaviors including
deviations from traffic rules and safe driving
performance that can lead to collisions.
> Nearly all events summarized above involved one or more road rule
violations or other driving performance deviations by another
road user.
Waymo
在努力实现不因为自身原因造成碰撞的同时,也尽量减少因为人类走神
(inattention),激进驾驶 (aggressive driving) 和超速 (speeding)
带来的可能碰撞。 > In addition to Waymo's key focus on not causing
collisions, Waymo also works to mitigate possible collisions due to
human behaviors such as inattention, aggressive driving, and
speeding.
Although many of these situations would not be present in a
future with a high proportion of AVs, we envision sharing roads with
human drivers for the foreseeable future. The rare contact
events described in this paper are used to develop enhanced collision
avoidance to improve traffic safety, and we will continue to
focus on enhancing avoidance of human-induced collisions. >
这些场景在道路上不常见,但是也无法避免,自动驾驶同行可以反思遇到的这些
corner cases.
Waymo 在努力减少事故发生的可能性
(likelihood),而不仅仅是避免碰撞。自车的行为,要能够被其他交通参与者
(other road users) 可判断 (interpretable) 和可预测 (predictable)。 >
Beyond collision avoidance, Waymo also continually investigates
improvements to the Waymo Driver’s behaviors to reduce the likelihood of
conflict with human-driven vehicles and other road users.
> This illustrates a key challenge faced by AVs operating in a
predominantly human traffic system and underscores the
importance of driving in a way that is interpretable and predictable by
other road users.
相比于人类,Waymo
的自动驾驶能力是可以不断提升的,适用到整个车队上。 > Unlike human
drivers, who primarily improve through individual
experience, the learnings from an event experienced by a single
AV can be used to permanently improve the safety performance of
an entire fleet of AVs.
Aggregate Safety Performance
Waymo 车辆在单车表现 (single-vehicle collision typology) 和 追尾问题
(rear-end collisions) 上的良好表现,已经优于人类。 > The Waymo Driver
experienced zero actual or simulated events in the “road departure,
fixed object, rollover” single-vehicle collision typology, reflecting
the system's ability to navigate the ODD in a highly reliable
manner.
> In addition, while rear-end collisions are one of the most common
collision modes for human drivers, the Waymo Driver only recorded
a single front-to-rear striking collision (simulated)
and this event involved an agent cutting in and immediately braking
without allowing for adequate separation distance (consistent with
antagonistic motive).
Lower-severity collision
risk
无论是人类驾驶员,还是自动驾驶车辆,轻微事故 (lower-severity events)
发生的频率要高于严重事故 (higher-severity) 的发生频率。 > In both
human-driven and automated vehicles, lower-severity events (S0 and S1)
occur at significantly higher frequency than higher-severity (S2 and S3)
events. As a result, fewer miles are needed to draw statistical
conclusions about S0 and S1 rates.
> When comparing driving data, the mileage needed to reveal
statistically significant differences also depends on the
magnitude of the differences in the actual rates being
compared.
For a given metric, the larger the difference in performance, the
fewer miles that are required to establish statistical
confidence in a hypothesis of non-inferiority or
superiority.
如何统计和判责 > low-severity data, when evaluated in the context
of each event’s collision geometry, may be informative of high-severity
risk.
现有的道路公开测试,可以为 S0 or S1 提供统计上的支持 (sufficient
statistical signal)。 > The 6.1 million miles in self-driving with
trained operators mode underlying the data in Section 3 provide
sufficient statistical signal to detect moderate-to-large differences in
S0 and S1 event frequencies, and Waymo makes use of these event
rates for tracking longer-term improvements to the Waymo Driver.
Higher-severity collision
risk
现有的道路公开测试,无法为 S2 or S3 提供强有力的统计支持。 > 6.1
million miles does not provide statistical power to draw meaningful
conclusions about the frequencies of events of severity S2 or S3.
> MC:目前的测试里程,可以为 Lower-severity
提供支持,但是不能为偶发的 Higher-severity 提供支持,里面有统计噪声
(statistical noise)。
> At this mileage scale, the statistical noise is extremely large and
zero or low event counts only provide performance
bounds, which necessitates the consideration of other metrics
to fully assess the safety of the Waymo Driver.
通过仿真和封闭场测试来评估高风险的表现. > Waymo uses other
methods to evaluate the higher-severity performance, including both
simulation-based and closed-course scenario-based collision-avoidance
testing.
从低风险事故中发掘高风险事故的信息。 > Low-severity data, when
evaluated in the context of each event’s collision geometry, may be
informative of high-severity risk.
Comparison benchmarks
Human driver collision rates have been widely discussed as providing
a benchmark for AVs.
警方统计的交通事故可能会忽略一部分低风险事件 (non-police-reportable
contact),所以 police-reported 不足以代表人类的真实事故发生频率。 >
By including low-speed events involving non-police-reportable contact
(e.g. a less than 2 mph vehicle-to-vehicle contact or a pedestrian
walking into the side of a stationary vehicle), the scope of
events is considerably greater than the scope of police-reported or
insurance-reported collisions commonly used to generate performance
baselines. As such, comparing the data presented in
this paper to police-reported collision numbers is not an apt
comparison.
Obtaining reliable event counts that include such minor events
typically requires analysis of naturalistic driving
data.
Limitations and Future Work
Limitations related to the statistical power of the mileages reported
have been discussed in the above section on aggregate collision
frequencies. > 即,目前的测试里程,可以为 Lower-severity
提供支持,但是不能为偶发的 Higher-severity 提供支持,里面有统计噪声
(statistical noise)。
Limitations of
counterfactual simulations
反事实仿真只是预测,但不是绝对的准确。 > Due to the nature of
human agent behavior, disengagement simulations are not definitive:
counterfactual simulations predict what could have occurred, but cannot
definitively predict exactly what would have occurred.
> As a result, had the driver not disengaged, some of the reported
simulated collisions may not have actually occurred (e.g. other agents
may have behaved differently). Conversely, other events that, in
simulation did not result in contact, may have actually resulted in
collisions (e.g. if the other agent had been distracted at the critical
moment).
Waymo therefore takes a cautious approach to
interpreting both the outcomes of individual collisions and aggregate
performance metrics, and considers them in the context of other
indicators of AV performance.
Secondary collision in
simulated events
The severities ascribed to the simulated collisions are based
on the single impact depicted in the simulation. Owing to
complexities in accurately modeling post-impact vehicle dynamics (which
may or may not involve subsequent steering and braking maneuvers from
the other vehicle), the outcome of any secondary collisions that might
occur subsequent to the simulated event are not explicitly modeled.
Waymo
的第一次碰撞,可以包含绝大多数的严重事故,二级事故不是很重要;二次碰撞需求显得不是那么紧迫。
> In Waymo’s ODD, the vast majority of primary vehicle-to-vehicle
collisions (99% for all collisions, 95% for fatal collisions)
included in police-reported crash databases involve either a
single vehicle-to-vehicle collision event or a subsequent collision
event of equal or lesser severity.
Interpreting disengage
performance
Waymo 安全驾驶员的避障表现,不代表人类驾驶员的避障表现。 > Care
should be taken in drawing conclusions based on the collision-avoidance
performance of Waymo’s trained operators during disengagements, which
for the reasons described below, is not predictive of the
collision-avoidance performance of the overall population of human
drivers.
Waymo 驾驶员和普通人类驾驶员的区别在哪里呢?
受过专业培训: Waymo vehicle operators are selected from a subset of
the driving population with good driving records and receive instruction
specific to Waymo AVs, defensive driving training, and
education regarding fatigue.
避免被打扰:When operating a vehicle, strict rules are in place
regarding handheld devices including cell phones and operators are
continually monitored for signs of drowsiness.
注意力更集中:Unlike drivers in human-driven vehicles, while the AV
is in self-driving mode, Waymo’s trained operators do not execute
navigation, path planning, or control tasks, but instead are focused on
monitoring the environment and the Waymo Driver’s response to it.
Trained vehicle operators are therefore able to focus their full
attention on being ready to disengage and execute collision avoidance,
and their performance at this task is expected to be superior to
that of a human in a traditional driving role.
Future work
We expect and invite other safety researchers to review the events
and mileages presented here and make their own findings regarding the
safety performance of Waymo’s operations demonstrated in this data.
Conclusion
Taken together, these 47 lower severity (S0 and S1) events (18 actual
and 29 simulated, one during driverless operation) show
significant contribution from other agents, namely
human-related deviations from traffic rules and safe driving
performance.
The frequency of challenging events that were induced by incautious
behaviors of other drivers serves as a clear reminder of the
challenges in collision avoidance so long as AVs share roadways with
human drivers.
由其他司机不谨慎行为诱发的事故频率清楚地提醒人们,只要自动驾驶汽车与人类司机共享道路,避免碰撞就是一大挑战。只要和人类共享道路
(share roads),完全安全的自动驾驶是不可行的,需要降低过高的期望
(inflated expectations)。 > Statistics regarding the high percentage
of human collisions that are attributed to human error may lead to
inflated expectations of the potential immediate safety benefits of AVs.
AVs will share roads with human drivers for the foreseeable future, and
significant numbers of collisions due to human driver errors that are
simply unavoidable should be expected during this
period.
和人类现有数据比较,碰撞分布发生变化;可以认清楚自动驾驶的优点
(机器稳定以及不知疲倦)以及劣势,优点可以及早加以利用,但是如何规避缺点却是一个难点。
> Due to the typology of those collisions initiated by other actors
as well as the Waymo Driver’s proficiency in avoiding certain collision
modes, the data presented shows a significant shift in
the relative distributions of collision types as compared to national
crash statistics for human drivers.
这是业界首次发布百万英里自动驾驶中的碰撞事故。评估自动驾驶汽车安全性没有标准的方法,Waymo
作为行业领头羊的担当,希望通过公布这些数据,推动政策制定者、研究人员甚至其他公司承担制定通用框架的任务。
> This is the first time that information on every actual and
simulated collision or contact has been shared for millions of miles of
automated driving.
> The most significant long-term contributions of this paper will
likely not be the actual data shared, but the example set by publicly
sharing this type of safety performance data and the dialogs that this
paper fosters.
读完这本书后,自己认识到这本书成稿于 PC
时代,那时候互联网不发达,作者给出的建议在手机时代不一定实用。比如转手二手物品时,作者推荐通过跳蚤市场和二手市场来面对面交易,而现在在网络上有一些二手交易平台,足不出户就可以以优惠的价格转手自己多余的东西;在对报纸处理中,还提到剪报这种跨时代的做法。同时,作者描写的是日本的社会,和中国存在文化和生活差异,比如日本人际交往中的纪念品和土特产繁多,垃圾处理有严格的规定,甚至有专门的垃圾处理费用,这部分经验在中国却不怎么实用。最后一点,作者以女性的视角来描写收纳,侧重点在厨房、衣服和书,读者群体以女性居多,对男性同胞就不够通用。