日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

動的な進化的探索による自動運転システムの多様な要求違反パターンの検出
石川 冬樹

Yixing Luo

Xiao-Yi Zhang

Paolo Arcaini

自動運転システムにおいては，安全性や快適さ，交通ルール遵守などに関する複数の要求を満たすことが求められる．ゆえに自動運転システムのシミュレーションテストにおいては，それら複数要求の優先度も踏まえつつ，それぞれに対する違反や複合的な違反について検出する必要がある．安全性要求違反となる衝突ケースなど，特定の違反をSearch-based Testing などにより探索することは行われてきたが，多様な要求違反パターンを検出することは従来なされていない．本発表においては，動的な進化的探索による自動運転システムの多様な要求違反パターンの検出手
法 [1] について論じる．提案手法では，特定の要求違反パターンに対して進化的な探索を行う部品に対し，探索目的となる要求違反パターンを動的に切り替える優先付けの部品を組み合わせる．経路計画機能プログラムとそのシュミレーターにより提案手法の評価を行い，多様かつ優先度が高い要求違反パターンを効率的に検出することができることを示した．

た．他車や歩行者の初期位置や振る舞いなどシミュ

1 はじめにレーション設定となるパラメーターを探索すること

自動運転システムにおいては，他車や歩行者の位置で，特定の要求違反が起きるケースを検出する．しかなど刻一刻と変わる多様な状況に対して，安全性や快し，複数要求に対する違反の多様な組み合わせを包括適さ，交通ルール遵守などに関する複数の要求を満た的に扱うことは従来なされていない．

すような振る舞いをとることが求められる．実世界に本講演では，著者らが提案する自動運転システムのおいて多様な状況を制御し十分なテストを行うこと

多様な要求違反パターンの検出手法 [1] について論じは困難であるため，シミュレーションを用いたテストる．提案手法では，特定の要求違反パターンに対してが重要となる．この際，安全性や快適さなど複数の要進化的な探索を行う部品に対し，探索目的となる要求求における優先度も踏まえつつ，それぞれに対する違違反パターンを動的に切り替える優先付けの部品を反や複合的な違反について検出する必要がある．

組み合わせる．経路計画機能プログラムとそのシュミ

これまで，安全性要求違反となる衝突ケースなど，レーターにより提案手法の評価を行い，多様かつ優先個々の要求違反に対し，シミュレーションのシナリオ度が高い要求違反パターンを効率的に検出することや設定を探索する自動テスト生成は取り組まれてきができることを示した．本稿では提案手法およびその評価の概要について述べる．定式化や実験の詳細につTalk Abstract: Targeting Requirements Violations ofAutonomous Driving Systems by Dynamic Evolutionary SearchThis manuscript is a Japanese abstract of a talkabout a paper published in The 36th IEEE/ACM
International Conference on Automated Software
Engineering (ASE 2021)
石川 冬樹, Xiao-Yi Zhang, Paolo Arcaini, 国立情報学研究所, National Institute of Informatics.
Yixing Luo, 北京大学, Peking University.

いては [1] を参照いただきたい．

2 問題設定2. 1 経路計画機能
本研究では，自動運転システムのうち，ハンドル角や加減速を決定する経路計画機能を対象としたテストについて論じる．経路計画機能は，多種センサーから得られる他車や歩行者の位置などの認識結果を受性要求の表現とし，各シミュレーションにおいて一回けて，自車が進むべき方向や速度を継続的に決定，更での違反が起きる時刻があった場合に危険事象があっ新し続ける．経路計画機能の出力に基づいて，加減速たと見なす．この際に，要求が満たされるかどうかのやステアリングの操作が実行されることになる．

二値ではなく，自車と他車との距離とをもって，要求提案手法は経路計画機能の実装方式に依存しない充足の度合いを評価する関数を定義することもできが，本研究の具体的な実装・評価では，最適化に基づる．このように，各シミュレーションの実行結果となく経路計画機能を対象とした．すなわち，複数考えらる各時刻での自車や環境の状態列から，各要求の充れる経路に対して，安全性，快適さ，交通ルール遵守足度合いを判断する評価関数があると想定し，そのなどの指標を計算し，その指標が最もよい経路を選択結果に対する制約として要求の充足可否が判断するするような実装方式である．と仮定する．なお，同じ種類の要求が複数の評価関数に詳細化されることもある．例えば快適さであれば，

2. 2 テスト入力生成

縦方向の加速度と横方向の加速度など複数の観点か経路計画機能を実装したプログラムに対するシミュら閾値を定めることが考えられる．

レーションテストにおいては，道路形状，他車や歩行者の初期位置や振る舞い，信号が変わるタイミング

2. 4 目的などのパラメーターを設定して運転挙動を実行する．

評価対象となる要求が n 個あるとしたとき，一回これらのパラメーターがテストの入力として自動生のシミュレーションテスト実行に対し，各要求への違成の対象となる．経路計画機能の挙動，その結果とし反が発生したかどうかの結果は 2n 種類の要求違反パての自車の振る舞いは，他車との位置関係などの詳細ターンが考えられる．本研究においては，各要求に異なパラメーター値に依存する．例えば信号がない交差なる重要度が与えられていることも踏まえ，より多く点での右折の場合，対向車線の車や左右からの車が来の要求違反パターンを，より重要なものを優先して効るタイミングの複合によって，衝突や急加速などが発率的に引き起こすようなテスト生成を目指す．道路形

生しうる．

状，他車や歩行者の初期位置や振る舞い，信号が変わシミュレーション設定として任意の道路形状まで生るタイミングなどのシミュレーション設定となるパラ成していくと，可能性が膨大であり入力の妥当性確保メーター空間を効率よく探索することが必要となる．

や結果の解釈も難しい．自動運転システムに対して加えて，シナリオによっては特定の要求違反パター

は，追い抜きや右折などテスト対象として大まかなシンがほぼ起きないことがある．例えば追い抜きのシナリオを人手で列挙することが行われている．このナリオにおいて，横方向の加速度が大きくなりすぎため，追い抜きや右折など対象とするシナリオは固ることはほぼない．このような状況の把握も含めて，定し，そのシナリオ内でのパラメーターを探索する．

複数の要求およびそれらからなる要求違反パターン

例えば追い抜きであれば，初期位置として自車の前方を包括的に考慮したテスト生成を目指す．

一定範囲に，やや遅めに走る他車がいることは固定する．その制約内で，その車の位置や速度，追い抜き車

3 提案手法線における他車の位置や速度を探索する．

3. 1 概要
図 1 に提案手法の概要を示す．まず異なる種類の要

2. 3 要求違反パターン

求およびそれぞれを表現する評価関数が入力となる

経路計画機能に対しては，安全性，快適さ，交通（図左下の Requirements ）．また，安全性要求への違ルール遵守など複数種類の要求を考える必要があり，反が最も致命的だと考える，複数要求への違反はよりかつ各要求について複数の指標がある．例えば，自車致命的であると考えるというように，各要求違反に対と他車との距離が一定の閾値以下であることを安全して致命度が与えられていることを想定する．この致

命度の半順序を入力とし，初期ラウンドの探索における対象は知名度が高い要求違反パターンの検出を目的とする（図左の Initial Prioritization (IP) ）．

3. 3 進化計算による最適化 (EMOO)
あるラウンドにおいて検出目的とする要求違反パターンが与えられたときに，メタヒューリスティック

あるラウンドにおいて，特定の要求違反パターンが最適化によりパラメーターを探索し，要求違反パター検出目的と設定されたときに，メタヒューリスティッンが発生するようなシミュレーション設定を探索す

ク最適化に基づく入力探索を行う（図右上の Evolu-る．提案手法では，具体的なメタヒューリスティック

tionary Many-Objective Optimization (EMOO) ）．

手法として，NSGA-III を用いた．NSGA-III は多目ランダムに生成した入力値，すなわち他車の位置など的最適化であるため，対象とする要求違反パターンにのシミュレーション設定から開始し，シミュレーショ含まれる個々の要求違反につながるように評価関数をンの実行と評価を反復することにより，対象とする最適化する．最適化のラウンドは一定の世代数あるい要求違反パターンの評価関数値を悪くするようにパは所要時間で終了する．

ラメーターの最適化を行う．いわゆる Search-Based

Testing の一種であると言える．

3. 4 動的な優先付け (DP)

本研究固有の手法として，上記 EMOO 部品が検出あるラウンドにおける最適化の結果を受けて，次の目的とする要求違反パターンについて，ラウンドごとラウンドの検出目的となる要求違反パターンを選ぶ．に動的に見直し切り替えていく（図右下の Dynamic

この際にはまず要求違反パターンの起きやすさにPrioritization (DP) ）．初期に与えられた要求違反パ関する指標を更新する．これまで検出された要求違反ターンの致命度を踏まえつつも，これまでの探索結果パターンについては，起きやすさの指標に一定値を加を受けて，より多様で致命度が要求違反パターンを検える．探索対象となったが検出できなかった要求違反出するように，EMOO の検出目的を再設定する．

パターンについては，起きやすさの指標から一定値を減じる．残りの要求違反パターン，すなわち検出目的

3. 2 初期の優先付け (IP)としておらず，検出がされていないパターンについて初期化の時点においては，致命度によって要求違反は，起きやすさの指標は 0 に初期化する．

パターンの半順序が定まっているとする．具体的には二つの順序づけルールを適用する．

次に，要求違反パターン間の包含関係について加味する．ある要求違反パターン Vi に対して，それに二つの要求違反パターン Vi , Vj のそれぞれにおい含まれる要求違反の一部分のみを含むような要求違て，発生した要求違反のうち最も高い致命度をそれぞ反パターン Vj がある．Vj の起きやすさが高ければ，れ pi , pj とする．このとき pi > pj ならば Vi の方がVi の起きやすさも高いと考えられるため，Vj の起きVj より致命度が高いとする．

やすさの値を Vi の起きやすさに加える．

致命度が高い要求違反から比べていって，高い知名

最後にこのようにして得られた，起きやすさの順序度でより多くの要求違反を含む要求違反パターンのづけと，入力として持っている致命度の順序づけとを方が，致命度が高いとする．例えば，二つの要求違反マージすることで，次のラウンドにおける検出目的をパターン Vi , Vj において，致命度 5 の要求違反がと決めるための順序づけを得る．

もに 2 つ，致命度 4 の要求違反がともに 3 つあったとする．このとき致命度 3 の要求違反の数が異なる

4 評価結果なら，それが大きい要求違反パターンの方が，より致提案手法の実装および評価は，協働する企業より提命度が高いと見なす．

供された経路計画プログラムおよびそのシミュレー
ターの研究用プロトタイプを用いて行った．本稿では提案手法の評価について代表的な結果一部のみを示す．図 2 に，検出した要求違反パターンの致命度を比Random Initialization

Evolutionary Many-Objective Optimization (EMOO)

Population 𝑃𝑃

Initial Prioritization (IP)

Requirements

TargetedPattern𝒱𝒱𝑐𝑐 [0]Test Scenario 𝑆𝑆𝑆𝑆𝑆𝑆

Trajectory
𝒯𝒯

Requirements
Violation
EvaluationADS Simulator
Unfound patterns 𝒱𝒱𝑡𝑡
Searched patterns 𝒱𝒱𝑒𝑒𝑒𝑒

Criticality Ranking 𝒱𝒱𝑐𝑐
図1

Fitness Scores 𝒳𝒳

Targeted pattern 𝒱𝒱𝑡𝑡 [0]Dynamic Prioritization (DP)

提案手法の概要（ [1] より引用）

多く検出できている．右折と比べて相対的に起きうる状況が限られる追い抜きにおいてより差が大きくなっている．

5 おわりに本稿では，自動運転システムにおける経路計画機能のシミュレーションテストにおいて，多様な要求違反パターンを，それらの致命度を踏まえつつ検出する手法について提案した．

謝辞
図2

検出した要求違反パターンの致命度の和（ [1] より引用）

本研究および著者のうち石川，Zhang，Arcaini
は，科学技術振興機構 ERATO-MMSD プロジェク較したものである．

ト（JPMJER1603）および MIRAI-eAI プロジェク

提案手法を EMOO-DP とし，そこから動的な優ト（JPMJMI20B8）の支援を受けた．本研究で用い先付け (DP) を外したものを EMOO-IP としていた経路計画プログラムおよびシミュレーターは，マツる．この場合は，まだ検出していない要求違反パター

ダ株式会社より，製品の品質とは一切関係のない研究

ンのうち，最も致命度が高いものを各ラウンドの検出用のプロトタイプとして提供を受けた．

目的としている．さらに初期の優先付けも考慮せずに，常にすべての要求を検出対象として探索し続ける

参 考 文 献場合を EMOO としている．またランダムにテスト[1] Luo, Y., Zhang, X.-Y., Arcaini, P., Jin, Z., Zhao,H., Ishikawa, F., Wu, R., and Xie, T.: Targeting Requirements Violations of Autonomous Driving Systems by Dynamic Evolutionary Search, The
36th IEEE/ACM International Conference on Automated Software Engineering (ASE 2021), November 2021, pp. 295–305.

入力を生成する Random も比較対象に含めている．
図 2 で は ，追 い 抜 き (Overtake) と 右 折 (TurnRight) の双方において，検出した要求違反パターンの致命度の和を比較している．提案手法の各構成要素により，より致命度が高い要求違反パターンをより