基于多目标进化搜索的无人自主系统仿真测试方法及系统

阅读：评论：0

reports.in proceedings of the acm joint meeting on european software engineering conference and symposium on the foundations of software engineering)。这种方法的问题在于，测试场景完全依赖于已发生的事故，难以覆盖边缘场景，无法对驾驶进行充分测试。
4.第二种方法是运用搜索技术生成仿真测试场景(参见：alessio gambi,marc mueller,and gordon fraser.2019.automatically testing self-driving cars with search-based procedural content generation.in proceedings of acm sigsoft international symposium on software testing and analysis.318
–
328)、(参见：moritz klischat and matthias althoff.2020.a multi-step approach to accelerate the computation of reachable sets for road vehicles.in proceeding of ieee international conference on intelligent transportation systems(itsc).ieee,1
–
7)、(参见：guanpeng li,yiran li,saurabh jha,timothy tsai,michael sullivan,siva kumar sastry hari,zbigniew kalbarczyk,and ravishankar iyer.2020.av-fuzzer:finding safety violations in autonomous driving systems.in proceedings of ieee international symposium on software reliability engineering(issre).25
–
36)。对无人自主系统的运动空间进行建模，将场景参数化，包括场景的环境变量、参与者的运动轨迹和时间信息等；在场景空间范围内，运用搜索方法得到场景参数值，生成具体场景。由于场景空间过于复杂且庞大，基于搜索技术的场景生成方法，会带来大量的时间开销；此外，由于搜索算法本身的局限性，会导致局部最优化问题，即场景演变和进化过程中，会趋于一致，难以全面暴露系统的安全性违规问题。对于像百度apollo这样每周发布软件更新的自动驾驶技术供应商来说，难以将现有的测试技术扩展到如此快速发展的系统。此外，与其他系统不同的是，无人自主系统还需要对系统进行长时间的运行测试，场景运行时间过短不符合实际运行时长。目前现有场景生成方法中，没有考虑到场景时长对系统安全问题的影响。

技术实现要素：

5.为解决上述问题，本发明提出了一种基于多目标进化搜索的无人自主系统仿真测试方法。运用系统的原子性操作与复合行为，构造场景参与者(npc：仿真场景中，除无人自主系统控制的对象外，场景中存在的其他参与者)的行为序列。原子性操作能够提高搜索的随机性，复合行为根据无人自主对象的实时位置，对其产生更为显著的干扰。通过多目标进化搜索，从无人自主系统的碰撞风险、无人自主系统受到的干扰、场景的差异程度这三个目标，对npc的行为序列进行搜索，生成对抗性高、差异度大的场景。通过并行方式执行多个搜索进程，并改进场景初始化方法，来测试无人自主系统在长距离运行时的表现。
6.为解决上述问题，本发明采取以下技术方案：
7.一种基于多目标进化搜索的无人自主系统仿真测试方法，包括以下步骤：
8.对场景参与者npc的行为即原子性操作和复合行为进行建模，得到原子基因和复合基因，一个npc的行为序列由至少两个原子基因和至少一个复合基因组成；对仿真场景进行编码，将每个场景表示为一个可进化个体，由至少两个染体组成，每个染体对应一个npc的行为序列；
9.通过多个原子基因与复合基因的随机组合，生成不同的初始场景个体；运行场景并获取每个个体的如下运行数据：无人自主对象的轨迹和速度、npc的轨迹和速度；
10.针对三个搜索目标：场景风险程度、对无人自主系统的干扰程度和场景差异度，定义如下四个适应度函数：无人自主对象的最小预计碰撞时间mettc、无人自主对象的运行轨迹相较于规划路径的最大偏移量dfp、无人自主对象在运行过程的加速度最大变化量voa、npc运行轨迹与已生成的关键场景的平均欧式距离aedf，其中mettc度量场景风险程度，dfp和voa度量对无人自主系统的干扰程度，aedf度量场景差异度；利用该四个适应度函数处理所述运行数据，计算出场景关键度值；
11.对所有个体的四个适应度函数指标按照计算出的场景关键度值进行综合排序，筛选出关键度高的场景并作为种子场景；利用场景进化算法对所述种子场景进行交叉和突变，生成下一代场景；
12.将生成的场景输入模拟器中，并在场景中设置一个虚拟物理对象，连接无人自主系统，运行场景对无人自主系统进行测试；并行运行多个互为独立的搜索进程，保存各搜索进程生成的测试场景；逐个运行多个搜索进程生成的场景，在场景运行过程中记录适应度函数计算所需的运行数据，并在场景执行结束时反馈给对应的搜索进程；其中在无人自主系统的运行过程中检测其安全状态，记录无人自主系统发生碰撞的场景并进行保存，用于场景重放。
13.进一步地，所述原子性操作由随机生成的速度和方向组成，所述复合行为包括多个自动机模型，每个自动机模型为根据场景运行时npc与无人自主系统的实时相对位置以一定的概率所执行的行为序列。
14.进一步地，利用pareto优化算法对四个适应度函数指标进行综合排序，方法为：首先对所有个体的每项适应度函数值进行排序，对mettc和aedf升序排序，对dfp和voa进行降序排序；计算场景间的拥挤距离并进行排序，拥挤距离越大，排名越高。
15.进一步地，所述场景进化算法包括交叉算法和突变算法；该交叉算法为场景之间染体的均匀交叉，为每个筛选出的个体生成交叉概率，决定其是否参与交叉；该突变算法用于个体内部的基因突变，包括单点突变、双点交叉和基因重排，双点交叉是随机选择两条染体进行均匀交叉，基因重排是对个体内每条染体上的基因进行重新排序。
16.进一步地，利用场景进化算法对所述种子场景进行交叉和突变，包括：
17.对无人自主系统未出现碰撞的场景，选择个体内所有染体中与自动驾驶车辆预计碰撞时间最小的基因，进行单点突变；若基因为原子基因，修改其属性值或者将其替换为复合基因；若基因为复合基因，将其替换为原子基因；
18.对无人自主对象发生碰撞的场景，生成突变概率，根据突变概率进行双点交叉或者基因重排；
19.当连续两代筛选出的场景均相同时，重启进化进程。
20.进一步地，并行运行多个互为独立的搜索进程时，为每个搜索进程分配一个标识号，并创建一个队列，保存各搜索进程生成的测试场景；从队列头开始依次获取场景数据，并运行场景；在场景运行完毕后，根据搜索进程分配的标识号，将记录的场景运行数据反馈给对应的搜索进程。
21.一种基于多目标进化搜索的无人自主系统仿真测试系统，包括：
22.场景构造模块，用于对场景参与者npc的行为即原子性操作和复合行为进行建模，得到原子基因和复合基因，一个npc的行为序列由至少两个原子基因和至少一个复合基因组成；
23.场景初始化模块，用于对仿真场景进行编码，将每个场景表示为一个可进化个体，由至少两个染体组成，每个染体对应一个npc的行为序列；通过多个原子基因与复合基因的随机组合，生成不同的初始场景个体；运行场景并获取每个个体的如下运行数据：无人自主对象的轨迹和速度、npc的轨迹和速度；
24.场景评价模块，用于针对三个搜索目标：场景风险程度、对无人自主系统的干扰程度和场景差异度，定义如下四个适应度函数：无人自主对象的最小预计碰撞时间mettc、无人自主对象的运行轨迹相较于规划路径的最大偏移量dfp、无人自主对象在运行过程的加速度最大变化量voa、npc运行轨迹与已生成的关键场景的平均欧式距离aedf，其中mettc度量场景风险程度，dfp和voa度量对无人自主系统的干扰程度，aedf度量场景差异度；利用该四个适应度函数处理所述运行数据，计算出场景关键度值；
25.场景进化模块，用于对所有个体的四个适应度函数指标按照计算出的场景关键度值进行综合排序，筛选出关键度高的场景并作为种子场景；利用场景进化算法对所述种子场景进行交叉和突变，生成下一代场景；
26.场景仿真模块，用于将生成的场景输入模拟器中，并在场景中设置一个虚拟物理对象，连接无人自主系统，运行场景对无人自主系统进行测试；并行运行多个互为独立的搜索进程，保存各搜索进程生成的测试场景；逐个运行多个搜索进程生成的场景，在场景运行过程中记录适应度函数计算所需的运行数据，并在场景执行结束时反馈给对应的搜索进程；其中在无人自主系统的运行过程中检测其安全状态，记录无人自主系统发生碰撞的场景并进行保存，用于场景重放。
27.本发明的优点包括：从动态行为的角度，对无人自主系统仿真场景进行建模，并编码为具有遗传属性的个体；构建动态参与者的复合行为模式，提高了对无人自主系统干扰的有效性；从场景风险程度、对无人自主系统的干扰程度、场景差异度这三大目标，设计适应度函数，指导场景进化，提高测试场景的对抗性和多样性；设计时空持续的多线程运行环境，支持无人自主系统的长距离行驶测试，提高了仿真测试的全面性与效率。
28.本发明的积极效果为：采用本发明可以对工业级别的无人自主系统进行仿真测试，将npc的动作建模为原子性操作与复合行为，构造仿真场景；通过多目标遗传算法，指导场景的进化，生成对抗性高、差异度大的测试场景，提高无人自主系统的安全性违规风险，增加场景的多变性，发现更多类型的无人自主系统安全性问题。仿真测试过程中，并行执行多个进化搜索进程，提高测试效率；改进场景运行的初始化方法，交替持续地运行多个进化搜索进程生成的场景，能够观测无人自主系统在长距离执行过程中的表现，更全面地对无人自主系统进行测试。
附图说明
29.图1为一种基于多目标进化搜索的无人自主系统仿真测试流程图。
30.图2为npc车辆相对于无人自主系统的方位划分示意图。
31.图3为npc车辆位于自动驾驶系统前方且处于同一车道的行为自动机示意图。
32.图4为npc车辆位于自动驾驶系统前方且处于不同车道的行为自动机示意图。
33.图5为npc车辆位于自动驾驶系统后方且处于同一车道的行为自动机示意图。
34.图6为某一时刻无人自主对象和一npc的行驶速度和方向示意图。
35.图7为场景个体的筛选流程图。
36.图8为场景个体间交叉的样例示意图。
37.图9为场景个体内基因单点突变的样例示意图。
38.图10为场景个体内染体间双点交叉的样例示意图。
39.图11为场景个体内基因重排的样例示意图。
40.图12为仿真测试与多进化进程执行的交互示意图。
具体实施方式
41.为使本发明的上述特征和优点能更明显易懂，下文特举实施例，并配合所附图作详细说明如下。
42.本实施例公开了一种基于多目标进化搜索的无人自主系统仿真测试方法，该方法的主要内容包括：
43.对npc的行为进行建模，包括原子性操作和复合行为，分别建模为原子基因和复合基因；复合行为是事件驱动的概率行为序列，通过自动机模型定义其不同条件下的执行过程。对仿真场景进行编码，将每个场景表示为一个可进化个体，由染体组成，染体是原子基因和复合基因所组成的序列。
44.定义了多目标适应度函数，从场景风险程度、对无人自主系统的干扰程度、场景差异度三个维度，对生成场景的对抗性和多样性进行度量，选择出种子场景；使用场景进化算法，对种子场景进行交叉和突变，包括场景间交叉、基因突变、染体交叉和基因重排，从而生成对抗性更强、多变性更高的场景。
45.并行执行多个搜索进程和模拟测试，在仿真环境中定义一个虚拟物理对象(是仿真场景中连接无人自主系统的对象)，连接被测无人自主系统，使其在模拟器中持续运行；逐个执行多个搜索进程生成的场景，对无人自主系统产生持续的干扰。记录适应度函数计算所需的运行数据，包括无人自主对象和npc的实际轨迹与速度，并在一个场景执行结束时反馈给对应的搜索进程。在无人自主系统的运行过程中，监测其安全性，记录无人自主系统出现安全性违规的场景，并运行重放方法，能够对保存的关键场景进行重放。
46.本实施例提出的一种基于多目标进化搜索的无人自主系统仿真测试方法，如图1所示，具体实现步骤如下：
47.(1)场景表示：将每个场景表示为一个个体，每个个体由2到i个染体构成；每个染体对应一个npc的行为序列，由2到m个原子基因和1到n个复合基因组成。每个原子基因对应一个原子性操作，每个复合基因是一个复合行为。原子性操作由随机生成的速度和方向组成，复合行为通过多个自动机模型，根据场景运行时npc与无人自主系统的实时相对位置，以一定的概率执行产生的行为。
48.(2)场景评价与选择：通过多个原子基因与复合基因的随机组合，生成初始场景。运行场景获取每个个体的运行数据，包括无人自主对象的轨迹和速度、npc的轨迹和速度；根据多目标的适应度函数，函数包括无人自主对象的最小预计碰撞时间、无人自主对象的
运行轨迹相较于规划路径的最大偏移量、无人自主对象在运行过程的加速度最大变化量、npc运行轨迹与已生成的关键场景的平均欧式距离，计算出场景关键度值。运用pareto优化对多指标进行综合排序，筛选出关键度高的场景，作为种子场景，进行场景变异，生成下一代场景。
49.(3)场景进化搜索：场景变异包括交叉算法和突变算法，交叉算法为场景之间染体的均匀交叉，为每个筛选出的个体，生成交叉概率r，决定其是否参与交叉。突变算法用于个体内部的基因突变，包括单点突变、双点交叉、基因重排。对无人自主系统未出现碰撞的场景，选择个体内所有染体中，与自动驾驶车辆预计碰撞时间最小的基因，进行单点突变；若基因为原子基因，修改其属性值或者将其替换为复合基因，若基因为复合基因，将其替换为原子基因。对无人自主对象发生碰撞的场景，生成突变概率，根据突变概率进行双点交叉或者基因重排。双点交叉是随机选择两条染体进行均匀交叉，基因重排是对个体内每条染体上的基因进行重新排序。当连续两代筛选出的场景均相同时，重启进化进程。
50.(4)仿真测试：将生成的场景输入模拟器中，并在场景中设置一个虚拟物理对象，连接无人自主系统；运行场景对无人自主系统进行测试。并行运行多个互为独立的搜索进程，为每个搜索进程分配一个标识号，并创建一个队列，保存各搜索进程生成的测试场景。从队列头开始依次获取场景数据，根据场景开始运行时，无人自主系统的实时位置，对npc的初始位置进行坐标转换。在场景运行过程中，记录无人自主系统的运行轨迹、各时刻的速度和加速度、各npc的行驶轨迹和速度；在场景执行完毕后，根据搜索进程标识号，将记录的场景运行数据反馈给对应的搜索进程，用于场景评价，而后将该场景从队列中移除。监测无人自主系统的安全状态，记录无人自主系统发生碰撞的场景，存储为数据文件；设计并实现场景复现方法，从存储的数据文件中读取场景数据，自动化复现场景的运行过程。
51.本实施例还提供一种基于多目标进化搜索的无人自主系统的仿真测试系统，其包括：场景构造模块、场景初始化模块、场景评价模块、场景进化模块、仿真测试模块；其中：
52.场景构造模块，对npc的驾驶行为进行建模，包括原子性操作和复合行为。运用行驶速度和行驶角度两个属性定义原子性操作，并定义了复合行为的自动机模型，描述复合行为在执行过程中，位于相对于无人自主系统的不同方位时，所执行的概率行为。每个场景由至少一个npc构成，每个npc的行为序列由大于一个原子性操作和不少于一个复合行为组成。原子性操作可以保证npc轨迹搜索的随机性，复合行为根据npc与无人自主系统的实时相对位置，使npc能够对无人自主系统产生有效干扰，提高了搜索的有效性。
53.场景初始化模块，将场景编码为可遗传个体，每个个体由至少两条染体构成，每条染体对应一个npc的行为序列；每个染体由多个基因组成，包括大于一个原子基因和不少于一个复合基因，每个原子基因对应一个原子性操作，每个复合基因对应一个复合行为，并为原子基因和复合基因分配运行时长。随机生成原子性操作与复合行为的组合，为进化搜索生成初始场景。
54.场景评价模块，从三个维度对场景的关键度进行评估：场景的危险程度，指无人自主对象与npc发生碰撞的风险概率；对无人自主系统的干扰程度，包括无人自主系统偏离初始规划路径的程度、无人自主系统出现紧急制动的程度；场景差异度：npc的行驶轨迹与已发现的关键场景中npc行驶轨迹的差异度。根据这三个目标，制定相应的适应度函数，对生成的场景进行度量和评价；运用pareto优化对多目标度量值进行综合排序，筛选出关键度
高的场景。
55.场景进化模块，设计并实现了场景进化算法，对场景评价模块筛选的场景，进行变异操作。变异算法包括交叉算法和突变算法。交叉算法用于跨场景的变异，能够提高场景的多样性；突变算法用于场景内的变异，能够提高场景的关键度和对抗性。生成交叉概率决定场景是否参与交叉，生成突变概率决定场景内部突变操作的类型。在进化搜索过程中，判定进化进程是否出现收敛，重启出现收敛的进化进程。
56.仿真测试模块，设计并实现了一个时空连续的无人自主系统仿真测试场景，并行执行多个搜索进程，交替连续执行生成的测试场景，能够测试无人自主系统在长距离运行过程中的表现。设计并实现了场景输入的坐标转换机制，能够在仿真模拟器中衔接不同场景的执行，为测试场景交替执行提供支持，并减少了场景运行的时间开销。在场景运行过程中，监测无人自主系统的状态，记录发生无人自主系统安全性违规的场景，并实现了自动化的场景重放，能够更好地对关键场景及无人自主系统的问题进行分析。
57.对上述模块的功能详细说明如下：
58.场景构造模块的实现如下：
59.对场景中npc的驾驶行为进行建模。使用表示第t个npc的第i个行为操作，npc的行为序列表示为原子行为由速度和方向构成，速度在[0,speed
limit
]的范围内随机生成，speed
limit
为npc的最大限速。以自动驾驶系统的测试为例，npc的复合行为由加速、减速、沿着车道行驶、变道四种行为组成，这些行为由仿真平台svl模拟器支持实现。复合行为定义了四组条件触发的行为序列，根据npc车辆与自动驾驶车辆的实时相对位置，以一定的概率，执行相应的行为。触发条件为npc车辆相对于自动驾驶车辆的所处方位，如图2所示，包括正前，正后，左前，左后，右前和右后，av为自动驾驶车辆的位置，正前为av当前所在车道的方向。复合行为包含四个自动机模型，每个模型都是由位置条件触发的概率行为序列。
[0060]
d为npc车辆与自动驾驶车辆的距离，spd为npc车辆的速度，spd
min
为车辆保持行驶状态的最小速度，lane为npc车辆所在的车道，lane
ego
为自动驾驶车辆所在的车道。图3所示为npc车辆位于自动驾驶车辆前方且处于同一车道的行为自动机，包含三种概率相同的行为转换：减速、变到相邻车道再转回原车道、刹车。图4所示为npc车辆位于自动驾驶车辆前方且处于不同车道(包含左前方和右前方)的行为自动机，npc车辆首先切换到自动驾驶车辆所在的车道，然后随机执行以下行为之一：减速、沿着车道行驶、变道、刹车。图5所示为npc车辆位于自动驾驶车辆后方且处于同一车道的行为自动机，如果d不小于安全距离，npc车辆将继续加速，直到d小于安全距离；然后npc车辆切换到相邻车道并加速，直到npc车辆与自动驾驶车辆的相对位置为左前方或右前方，将触发图4的自动机。第四种自动机的触发条件为npc车辆位于自动驾驶车辆后方且处于不同车道，npc车辆将加速直到其位于自动驾驶车辆的左前方或右前方，将触发图4的自动机。
[0061]
场景初始化模块的实现如下：
[0062]
测试场景个体si＝{c1,c2,...,cn}，染体cn＝{b1,b2,m1,...,bi,mj}。每一个个体si对应一个测试场景，包含两条及以上的染体cn。每一条染体cn由至少一个复合基因mj和两个以上的原子基因bi组成。bi对应一个原子性操作，由速度和方向构成。mj对应一个复
合行为。单个原子基因的执行步长为1秒，单个复合基因的执行步长为4秒。一个场景的运行时间由基因步长之和最大的染体所决定。通过多个原子基因与复合基因的随机组合，生成初始场景。
[0063]
场景评价模块的实现如下：
[0064]
场景评价包括三个目标：
[0065]
1)目标1：场景风险——无人自主系统与npc具有较高的碰撞概率；
[0066]
2)目标2：对无人自主系统的扰动——使无人自主系统在行驶过程中偏离计划路线、出现紧急制动；
[0067]
3)目标3：场景多样性——npc的运行轨迹与已发现的关键场景存在较大差异。
[0068]
根据三个搜索目标，定义了四个适应度函数，对场景的关键程度进行度量：最小预计碰撞时间(mettc)、无人自主系统轨迹的最大偏移量(dfp)、无人自主系统运行过程的最大加速度变化量(voa)、npc轨迹与已发现关键场景的平均欧式距离(aedf)。mettc是目标1的度量函数，dfp和voa是目标2的度量函数，aedf是目标3的度量函数。
[0069]
(1)mettc：最小预计碰撞时间是场景中无人自主对象和npc之间的最小预计碰撞时间(ettc)。ettc的定义为两个对象以当前方向和当前速度继续运行，发生碰撞所需要的时间。图6显示的是某一时刻无人自主对象和某一npc的运行速度和方向，(x2，y2)是npc在该时刻的位置，(x1，y1)是无人自主对象在该时刻的位置，(x
+
，y
+
)为npc和无人自主对象以当前状态行驶预计发生碰撞的位置。v2是从车的瞬时速度，v是无人自主对象当前状态下的瞬时速度，v
x
，vy是瞬时速度的x轴和y轴分量。θ1是无人自主对象当前状态下的方向角度，θ2是npc当前状态下的方向角度。ettc的计算公式如下：
[0070][0071][0072][0073]
在场景运行过程中，每0.1s记录一次npc的位置和速度；场景执行完毕后，对场景个体内所有染体上的每个基因，计算其执行过程中最小的ettc，作为该基因的ettc；所有基因的ettc的最小值为mettc。当场景中无人自主对象出现碰撞，则mettc为0。mettc越小，场景的关键度越高。
[0074]
(2)dfp
[0075]
在仿真场景中，无人自主系统在不受到任何影响的情况下，默认会控制无人自主对象沿着车道匀速行驶；当行驶途中受到有效干扰时，会实时调整行驶路径。通过实时监控无人自主对象的行驶状态，每0.1秒记录一次位置；若记录了t个位置，则无人自主对象的默认行驶路径表示为tre＝(e0，e1，...，e
t
)，e
t
＝(e
t
.x，e
t
.y)，x，y是无人自主对象在对应时刻的预估位置坐标；由e0出发、下一个点的位置＝0.1s*无人自主对象的默认速度。在场景运行过程中，实时记录无人自主对象实际运行的位置和速度，实际行驶路径为tra＝(p0，p1，...，p
t
)，p
t
＝(p
t
.x，p
t
.y)，x，y是无人自主对象在对应时刻的位置坐标。dfp的计算公式如下：
[0076][0077]
dfp越大，场景关键度越高。
[0078]
(3)voa
[0079]
在场景运行过程中，每1s记录一次无人自主对象的实际速度大小，表示为ve＝(v0，v1，...，v
t
)。voa的计算公式如下：
[0080][0081]
voa越大，场景关键度越高。
[0082]
(4)aedf
[0083]
aedf的计算公式如下，s代表场景，sk表示第k个场景，ed为场景间的欧式距离，tr代表npc的轨迹，dis为轨迹间的欧式距离。
[0084][0085][0086]
在场景运行过程中，每0.1s记录一次npc的位置，表示为tri＝((x0，y0)，(x1，y1)...，(xn，yn))；计算aedf时，需要对记录的轨迹进行坐标转换。首先定位无人自主对象在场景中的起点位置，计算其与所在地图原点的横纵坐标差(δx，δy)；而后对每个记录的坐标点，进行坐标转换p＝(x
i-δx，y
i-δy)。转换后的轨迹表示为δy)。转换后的轨迹表示为另一场景中，转换后的npcj的轨迹为x，y为该npc在这一时刻的位置坐标。轨迹间的欧式距离计算公式如下：
[0087][0088]
若m＞n，则若m＞n，则均等于aedf越高，场景关键度越高。
[0089]
如图7所示，在场景运行结束时，根据上述四个指标，计算场景的关键度得分。当一代场景全部运行结束，运用pareto优化对这一代所有个体的四项得分进行综合排序：首先对所有个体的每项适应度函数值进行排序，对mettc和aedf升序排序、对dfp和voa进行降序排序；计算场景间的拥挤距离并进行排序，拥挤距离越大，排名越高。选择排名前k个个体作为种子个体，参与下一轮的迭代。
[0090]
场景进化模块的实现如下：
[0091]
场景进化搜索是对上一代筛选保留的种子个体，进行交叉和突变操作；如果连续三代中筛选保留的种子个体没有改变，将重新启动进化进程。
[0092]
对种子个体的进化操作具体步骤如下：
[0093]
1)对每个个体，依次生成交叉概率r～u(0，1)，若r≥threshold
crossover
，则将该个
体添加到交叉个体集中，其中threshold
crossover
是场景个体间进行染体交叉的阈值，该阈值可以由测试人员自定义，常见的取值为0.4或0.5；
[0094]
2)对交叉个体集的所有个体，两两之间进行均匀交叉，通过不同个体的染体进行单点交叉实现的，如图8所示，s1和s2进行交叉，在个体的染体数量内随机选择一个交叉点，图8的交叉点为1，交叉后生成的新个体为s3和s4；
[0095]
3)在该代个体的交叉完成后，清空交叉个体集；
[0096]
4)对无人自主系统未发生碰撞的场景个体，选择ettc最小的基因，进行单点突变，如果该基因是原子基因，修改其属性值(速度、方向)或用复合基因替换；如果该基因是复合基因，则将其替换为原子基因，并随机生成其属性值。如图9为一个复合基因突变的样例；
[0097]
5)对无人自主系统产生碰撞的场景个体，生成突变概率r～u(0,1)，若r≤threshold
mutation
，对该个体进行双点交叉，其中threshold
mutation
是场景个体间进行基因突变的阈值，该阈值可以由测试人员自定义，如图10所示，随机选择该个体内的两条染体，在被选中的染体上各随机选择一个交叉点，在这两个点之间进行染体的随机交叉，交换两个点之间的基因。染体c1和c2的交叉点分别为p1和p2，双点交叉之后生成新个体s2；
[0098]
6)若突变概率r》threshold
mutation
，对该个体进行基因重排，如图11所示，对s1的每条染体c1和c2，随机改变基因顺序，基因重排之后生成新个体s2。
[0099]
仿真测试模块的实现如下：
[0100]
并行运行多个搜索进程，为每个搜索进程分配一个唯一标识id；在仿真程序中，维护一个场景队列，保存各搜索进程生成的场景；在每个场景开始执行前，根据无人自主系统的实时位置，对npc的轨迹坐标进行转换。具体步骤如下：
[0101]
1)启动模拟器，在虚拟环境中随机选择一个位置，生成一个物理虚拟对象，连接无人自主系统；
[0102]
2)启动多个独立的搜索进程，每个搜索进程生成的场景，输入场景队列中；
[0103]
3)从队列头部获取第一个场景的数据，根据场景数据中无人自主系统的位置(x,y)以及无人自主系统在仿真环境中的当前实时位置(x1,y1)，，对npc的初始位置(x
p
,y
p
)进行转换，转换后的初始位置为(x
p
+δx,y
p
+δy)；δx＝x
i-x，δy＝y
i-y；
[0104]
4)执行该场景，在场景运行过程中，观测无人自主系统是否发生碰撞，并每0.1s记录一次无人自主对象的位置、npc的位置、npc的速度，每1s记录一次无人对象的速度；
[0105]
5)执行完毕后，根据场景的进程id，将第4步记录的数据反馈给对应的搜索进程，并将无人自主对象产生碰撞的场景，并存储为数据文件；
[0106]
6)第5步完成后，清除场景中所有的npc，将该场景数据从队列中移除，将无人自主对象设置为默认的运行状态；
[0107]
7)重复执行第3-第6步；
[0108]
8)读取存储的场景数据文件，根据其中npc与无人自主对象的运行数据，在模拟器中复现该场景，进行进一步的分析。
[0109]
虽然本发明已以实施例公开如上，然其并非用以限定本发明，本领域的普通技术人员对本发明的技术方案进行的适当修改或者等同替换，均应涵盖于本发明的保护范围内，本发明的保护范围以权利要求所限定者为准。

技术特征：

1.一种基于多目标进化搜索的无人自主系统仿真测试方法，其特征在于，包括以下步骤：对场景参与者npc的行为即原子性操作和复合行为进行建模，得到原子基因和复合基因，一个npc的行为序列由至少两个原子基因和至少一个复合基因组成；对仿真场景进行编码，将每个场景表示为一个可进化个体，由至少两个染体组成，每个染体对应一个npc的行为序列；通过多个原子基因与复合基因的随机组合，生成不同的初始场景个体；运行场景并获取每个个体的如下运行数据：无人自主对象的轨迹和速度、npc的轨迹和速度；针对三个搜索目标：场景风险程度、对无人自主系统的干扰程度和场景差异度，定义如下四个适应度函数：无人自主对象的最小预计碰撞时间mettc、无人自主对象的运行轨迹相较于规划路径的最大偏移量dfp、无人自主对象在运行过程的加速度最大变化量voa、npc运行轨迹与已生成的关键场景的平均欧式距离aedf，其中mettc度量场景风险程度，dfp和voa度量对无人自主系统的干扰程度，aedf度量场景差异度；利用该四个适应度函数处理所述运行数据，计算出场景关键度值；对所有个体的四个适应度函数指标按照计算出的场景关键度值进行综合排序，筛选出关键度高的场景并作为种子场景；利用场景进化算法对所述种子场景进行交叉和突变，生成下一代场景；将生成的场景输入模拟器中，并在场景中设置一个虚拟物理对象，连接无人自主系统，运行场景对无人自主系统进行测试；并行运行多个互为独立的搜索进程，保存各搜索进程生成的测试场景；逐个运行多个搜索进程生成的场景，在场景运行过程中记录适应度函数计算所需的运行数据，并在场景执行结束时反馈给对应的搜索进程；其中在无人自主系统的运行过程中检测其安全状态，记录无人自主系统发生碰撞的场景并进行保存，用于场景重放。2.如权利要求1所述的方法，其特征在于，所述原子性操作由随机生成的速度和方向组成，所述复合行为包括多个自动机模型，每个自动机模型为根据场景运行时npc与无人自主系统的实时相对位置以一定的概率所执行的行为序列。3.如权利要求1所述的方法，其特征在于，利用pareto优化算法对四个适应度函数指标进行综合排序，方法为：首先对所有个体的每项适应度函数值进行排序，对mettc和aedf升序排序，对dfp和voa进行降序排序；计算场景间的拥挤距离并进行排序，拥挤距离越大，排名越高。4.如权利要求1所述的方法，其特征在于，mettc的计算方法为：根据场景中无人自主对象和npc的当前状态的位置、运行速度和运行方向，计算npc和无人自主对象以当前状态行驶预计发生碰撞的位置，根据无人自主对象的当前状态的位置和运行速度以及预计发生碰撞的位置，计算无人自主对象和npc之间的预计碰撞时间ettc；场景执行完毕后，对场景个体内所有染体上的每个基因计算其执行过程中最小的ettc，作为该基因的ettc；所有基因的ettc的最小值为mettc。5.如权利要求1所述的方法，其特征在于，aedf的计算方法为：首先定位无人自主对象在一场景中的起点位置，计算其与所在地图原点的横纵坐标差；然后根据该横纵坐标差对每个记录的坐标点进行坐标转换，得到转换后的npc的轨迹tr
i
；根据同样的方法计算在另
一场景中获得转化后的npc的轨迹tr
j
；根据上述两个轨迹tr
i
、tr
j
以及npc在当前时刻的位置坐标，计算轨迹间的欧式距离；根据上述轨迹间的欧式距离计算场景间的欧式距离，在根据该场景间的欧式距离计算aedf。6.如权利要求1所述的方法，其特征在于，所述场景进化算法包括交叉算法和突变算法；该交叉算法为场景之间染体的均匀交叉，为每个筛选出的个体生成交叉概率，决定其是否参与交叉；该突变算法用于个体内部的基因突变，包括单点突变、双点交叉和基因重排，双点交叉是随机选择两条染体进行均匀交叉，基因重排是对个体内每条染体上的基因进行重新排序。7.如权利要求6所述的方法，其特征在于，利用场景进化算法对所述种子场景进行交叉和突变，包括：对无人自主对象发生碰撞的场景，生成交叉概率，根据交叉概率，进行场景之间的染体均匀交叉；对无人自主系统未出现碰撞的场景，选择个体内所有染体中与自动驾驶车辆预计碰撞时间最小的基因，进行单点突变；若基因为原子基因，修改其属性值或者将其替换为复合基因；若基因为复合基因，将其替换为原子基因；对无人自主对象发生碰撞的场景，生成突变概率，根据突变概率进行双点交叉或者基因重排；当连续两代筛选出的场景均相同时，重启进化进程。8.如权利要求7所述的方法，其特征在于，预先设置场景个体间进行染体交叉的阈值threshold
crossover
和场景个体间进行基因突变的阈值threshold
mutation
；如果交叉概率大于等于threshold
crossover
，则对每个个体两两之间进行均匀单点交叉；如果突变概率小于等于threshold
mutation
，则对该个体进行双点交叉；如果该突变概率大于threshold
mutation
，则对该个体进行基因重排。9.如权利要求1所述的方法，其特征在于，并行运行多个互为独立的搜索进程时，为每个搜索进程分配一个标识号，并创建一个队列，保存各搜索进程生成的测试场景；从队列头开始依次获取场景数据，并运行场景；在场景运行完毕后，根据搜索进程分配的标识号，将记录的场景运行数据反馈给对应的搜索进程。10.一种基于多目标进化搜索的无人自主系统仿真测试系统，其特征在于，包括：场景构造模块，用于对场景参与者npc的行为即原子性操作和复合行为进行建模，得到原子基因和复合基因，一个npc的行为序列由至少两个原子基因和至少一个复合基因组成；场景初始化模块，用于对仿真场景进行编码，将每个场景表示为一个可进化个体，由至少两个染体组成，每个染体对应一个npc的行为序列；通过多个原子基因与复合基因的随机组合，生成不同的初始场景个体；运行场景并获取每个个体的如下运行数据：无人自主对象的轨迹和速度、npc的轨迹和速度；场景评价模块，用于针对三个搜索目标：场景风险程度、对无人自主系统的干扰程度和场景差异度，定义如下四个适应度函数：无人自主对象的最小预计碰撞时间mettc、无人自主对象的运行轨迹相较于规划路径的最大偏移量dfp、无人自主对象在运行过程的加速度最大变化量voa、npc运行轨迹与已生成的关键场景的平均欧式距离aedf，其中mettc度量场景风险程度，dfp和voa度量对无人自主系统的干扰程度，aedf度量场景差异度；利用该四个
适应度函数处理所述运行数据，计算出场景关键度值；场景进化模块，用于对所有个体的四个适应度函数指标按照计算出的场景关键度值进行综合排序，筛选出关键度高的场景并作为种子场景；利用场景进化算法对所述种子场景进行交叉和突变，生成下一代场景；场景仿真模块，用于将生成的场景输入模拟器中，并在场景中设置一个虚拟物理对象，连接无人自主系统，运行场景对无人自主系统进行测试；并行运行多个互为独立的搜索进程，保存各搜索进程生成的测试场景；逐个运行多个搜索进程生成的场景，在场景运行过程中记录适应度函数计算所需的运行数据，并在场景执行结束时反馈给对应的搜索进程；其中在无人自主系统的运行过程中检测其安全状态，记录无人自主系统发生碰撞的场景并进行保存，用于场景重放。

技术总结

本发明公开一种基于多目标进化搜索的无人自主系统仿真测试方法及系统，属于计算机仿真领域，运用系统的原子性操作与复合行为，构造场景参与者NPC的行为序列。原子性操作能够提高搜索的随机性，复合行为根据无人自主对象的实时位置，对其产生更为显著的干扰。通过多目标进化搜索，从无人自主系统的碰撞风险、无人自主系统受到的干扰、场景的差异程度这三个目标，对NPC的行为序列进行搜索，生成对抗性高、差异度大的场景。通过并行方式执行多个搜索进程，并改进场景初始化方法，来测试无人自主系统在长距离运行时的表现。主系统在长距离运行时的表现。主系统在长距离运行时的表现。