（アジャイルvsウォーターフォール）重要なアルゴリズムの開発：設計

滝を想像してみてください。パワフル。申し分のない。常に差し迫った降下に向かって前進します。宇宙のいくつかの基本的な力の1つによって駆動されます。



滝はその性質上素晴らしいので、エンジニアが滝に夢中になっているのも当然です。ウォーターフォールモデルの使用を推奨する古いDOD-STD-2167A標準、および私のレガシーエンジニアリングの背景はフェーズゲートモデルに基づいていました。これは、私の見解ではウォーターフォールモデルにかなり似ています。一方、大学でコンピュータサイエンスを研究していた私たちは、ウォーターフォールモデルが何らかの形でアンチパターンであることを知っているでしょう。アカデミックな象牙の塔にいる私たちの友人は、いいえ、いいえ、アジャイルを教えてくれます成功への道であり、業界はその主張が真実であると証明したようです。



では、開発者は老朽化したウォーターフォールモデルと新しくできたアジャイルのどちらを選択するべきでしょうか？アルゴリズムの開発に関して、方程式は変わりますか？または、いくつかのセキュリティクリティカルなソフトウェア？



いつものように、答えはその中間にあります。

ハイブリッド、スパイラル、Vパターン

ハイブリッド開発は真ん中にある答えです。ウォーターフォールモデルが前に戻って要件を変更することを許可しない場合、ハイブリッドモデルは許可します。また、アジャイルに先行設計の問題がある場合、ハイブリッド開発はその余地を残します。さらに、ハイブリッド開発の目的は、最終製品の欠陥の数を減らすことです。これは、セキュリティが重要なアプリケーションのアルゴリズムを設計するときにおそらく必要なことです。



良さそうに聞こえますが、どれほど効果的ですか？



この質問に答えるために、NDTローカリゼーションアルゴリズムに取り組みながら、ハイブリッド開発に賭けています。... ローカリゼーションは、純粋な反応制御を超える自動運転スタックの重要な部分です。私を信じない、またはローカリゼーションに不慣れな場合は、このプロセスを通じて開発された設計ドキュメントをいくつか確認することを強くお勧めします。



要するに、ハイブリッド開発とは何でしょうか。私のアマチュアの観点からは、これは理想的なV字型またはスパイラルモデルであると言えます。計画、設計、実装、およびテストを行い、その間に学んだ教訓とその間に得た新しい知識に基づいて、プロセス全体を繰り返します。

実用

具体的には、我々は、Autoware.AutoでNDTワーキンググループで、準備のために（つまり、私たちは設計段階を通じて最初の反復を行っている）V-モデルの左カスケードダウン我々の最初の降下を完了したロンドンのAutowareハッカソン（で実行Parkopedia！）。設計フェーズの最初のパスは、次のステップで構成されていました。

1. 文献展望
2. 既存の実装の概要
3. 高レベルのコンポーネント、ユースケース、要件の設計
4. 障害分析
5. 指標の定義
6. APIのアーキテクチャと設計

似たようなものに興味がある場合は、結果の各ドキュメントを確認できますが、この記事の残りの部分では、それらのいくつかを分析して、これらの各段階で何が、どのようにして生まれたのかを説明します。

文献と既存の実装のレビュー

きちんとした取り組み（つまり、NDT実装を分類する方法）の最初のステップは、他の人が何をしたかを確認することです。結局のところ、人間は社会的な存在であり、私たちのすべての業績は巨人の肩の上に立っています。



ほかに、「過去の芸術」を検討する際に考慮すべき重要な領域が2つあります。それは、学術文献と機能の実現です。



貧しい大学院生が飢饉の最中に何に取り組んでいたのかを調べることは常に役に立ちます。せいぜい、独自のアルゴリズムの代わりに実装できる完全に優れたアルゴリズムがあることがわかります。最悪の場合、ソリューションの空間とバリエーション（情報アーキテクチャに役立ちます）の理解が得られ、アルゴリズムの理論的基盤（したがって、注意が必要な不変条件）について学ぶこともできます。



一方、他の人が何をしているかを確認することも同様に役に立ちます。結局のところ、開始プロンプトで何かを始めるのが常に最も簡単です。優れたアーキテクチャのアイデアを無料で借りられるだけでなく、アルゴリズムを実際に機能させるために必要な推測やダーティなトリックを発見することもできます（それらをアーキテクチャに完全に統合することもできます）。NDTの文献のレビュー



から、以下の有用な情報を収集しました。

• NDTファミリーのアルゴリズムにはいくつかのバリエーションがあります。
  
  -P2D
  
  -D2D-
  
  制限付き
  
  -セマンティック
• アルゴリズムのパフォーマンスを向上させるために使用できるダーティなトリックがたくさんあります。
• NDTは通常ICPと比較されます
• NDTは少し高速で、信頼性が少し高くなっています。
• NDTは、定義された領域内で確実に動作します（高い成功率を持っています）

驚くべきことは何もありませんが、この情報は、設計と実装の両方で後で使用するために保存できます。



同様に、既存の実装の概要から、具体的な手順だけでなく、興味深い初期化戦略もいくつか見ました。

ユースケース、要件、メカニズム

設計または計画優先の開発プロセスの不可欠な部分は、高レベルで解決しようとしている問題に対処することです。広義では、機能安全の観点（私は告白しますが、専門家とは程遠いです）の観点から、「問題の高レベルな見方」はおおよそ次のように構成されています。

1. どのようなユースケースを解決しようとしていますか？
2. 上記のユースケースを満たすソリューションの要件（または制限）は何ですか？
3. 上記の要件を満たすメカニズムは何ですか？

上記のプロセスは、問題の統制のとれた高レベルのビューを提供し、徐々に詳細になります。



これがどのように見えるかを理解するために、NDTの開発に備えてまとめた高レベルのローカリゼーションプロジェクトドキュメントをご覧ください。寝る前に読む気分がない場合は、読み続けてください。

ユースケース

私はユースケースへの3つの思考アプローチが好きです（注意、私は機能安全の専門家ではありません）。

1. コンポーネントは何をすることになっていますか？（SOTIFを思い出してください！）
2. コンポーネントに入力を入力する方法は何ですか？（入力ユースケース、私はそれらを上流に呼びたい）
3. 出力を取得する方法は何ですか？（週末またはトップダウンの使用例）
4. おまけの質問：このコンポーネントは、システムアーキテクチャ全体に常駐できますか？

すべてをまとめると、次のことがわかりました。

• ほとんどのアルゴリズムはローカリゼーションを使用できますが、最終的にはローカルとグローバルの両方で機能するフレーバーに分割できます。
• ローカルアルゴリズムは、変換履歴の継続性を必要とします。
• ほぼすべてのセンサーをローカリゼーションデータのソースとして使用できます。
• ローカリゼーションメソッドを初期化してトラブルシューティングする方法が必要です。

考えられるさまざまなユースケースとは別に、非常に厳しい一般的なユースケースについても考えたいと思います。これを行うには、完全に無人のオフロード旅行のオプション（またはタスク）があり、キャラバンで交通のあるいくつかのトンネルを通過します。この使用例には、オドメトリエラーの累積、浮動小数点エラー、ローカリゼーションの修正、機能停止など、いくつかの不都合があります。

必要条件

ユースケースを開発する目的は、解決しようとしている問題を一般化することに加えて、要件を定義することです。ユースケースを実行する（または満足させる）には、おそらく実現または可能でなければならないいくつかの要因があります。つまり、各ユースケースには特定の要件セットがあります。



結局、ローカリゼーションシステムの一般的な要件はそれほど怖いものではありません。

• ローカルアルゴリズムの変換を提供する
• グローバルアルゴリズムに変換を提供する
• 相対ローカリゼーションアルゴリズムの初期化メカニズムを提供する
• コンバージョンが波及しないようにする
• REP105コンプライアンスを確保

資格のある機能安全の専門家は、さらに多くの要件を策定する可能性があります。この作業の価値は、メカニズムと同様に、アルゴリズムの操作に関する要件を満たす設計の特定の要件（または制限）を明確に定式化しているという事実にあります。

メカニズム

あらゆる種類の分析の最終結果は、実践的なレッスンまたは教材のセットになるはずです。分析の結果、その結果を使用できない場合（負の結果でも！）、分析は無駄になります。



高レベルのエンジニアリングドキュメントの場合、一連のメカニズムまたはこれらのメカニズムをカプセル化するコンストラクトについて説明します。これらは、ユースケースに適切に対応できます。



この特定の高レベルのローカリゼーション設計により、ローカリゼーションシステムのアーキテクチャを構成するソフトウェアコンポーネント、インターフェース、および動作のセットが可能になりました。提案されたアーキテクチャの簡単なブロック図を以下に示します。







アーキテクチャやデザインに関する詳細情報に興味がある場合は、ドキュメントの全文。

障害分析

セキュリティが重要なシステム上にコンポーネントを構築しているため、障害は回避するか、少なくとも軽減する必要があります。したがって、何かを設計または構築しようとする前に、少なくとも物事がどのように壊れるかを認識しておく必要があります。



障害を分析する場合、ほとんどの場合と同様に、コンポーネントを複数の角度から見ると便利です。NDTアルゴリズムの失敗を分析するために、一般的な（相対的な）ローカリゼーションメカニズムとして、特にNDTアルゴリズムのインスタンスとして、2つの異なる方法でそれを検討しました。



ローカリゼーションメカニズムの観点から見ると、主な障害モードは次のように定式化されます-「入力が誤ったデータである場合の対処方法」。実際、個々のコンポーネントの観点からは、システムの妥当性に関する基本的なチェックを行う以外に、ほとんど何もできません。システムレベルでは、追加のオプション（たとえば、セキュリティ機能の有効化）があります。



NDTを単独のアルゴリズムとして考える場合、適切な数の側面を強調することにより、アルゴリズムから抽象化することは有用です。アルゴリズムの疑似コードバージョンに注意を払うと役立ちます（これは、開発者がアルゴリズムをよりよく理解するのに役立ちます）。この場合、アルゴリズムを詳細に分析し、アルゴリズムが破損する可能性のあるすべての状況を調査しました。



実装エラーは完全に妥当なエラーですが、適切なテストで修正できます。数値アルゴリズムに関するいくつかのニュアンスは、もう少し頻繁に、そしてより陰湿に現れ始めました。特に、逆行列を見つけること、またはより一般的には、数値誤差につながる可能性がある線形方程式のシステムを解くことについて話します。これは非常にデリケートな障害シナリオであり、対処する必要があります。



私たちが特定した他の2つの重要な障害は、特定の式の大きさが無制限でないことの検証（浮動小数点精度制御）と、入力の大きさまたはサイズが常に監視されていることの検証です。



合計で、15の推奨事項を作成しました... それらに慣れることをお勧めします。



また、この方法は使用しませんでしたが、フォールトツリー分析は、障害分析の問題を構造化および定量化するための優れたツールです。

指標の定義

「測定対象は管理可能」

-管理者の人気のフレーズ

残念ながら、専門能力開発では、肩をすくめて何かに取り組んでいるときに「完了」と言うだけでは不十分です。基本的に、ワークパッケージ（これもNDT開発です）には受け入れ基準が必要です。受け入れ基準は、顧客とサプライヤーの両方が同意する必要があります（顧客と販売者の両方の場合は、この手順をスキップしてください）。これらの側面をサポートするための法学はすべて存在しますが、エンジニアとして、コンポーネントの可用性を判断するためのメトリックを作成することで、仲介者を簡単に排除できます。結局のところ、数値は（ほとんど）明確であり、反駁できないものです。



受け入れ基準が不要または無関係である場合でも、プロジェクトの品質とパフォーマンスを特徴づけ、改善する明確に定義されたメトリックのセットがあることは、それでも素晴らしいことです。結局、測定されているものは制御可能です。



以下のために私たちのNDTの実装、我々は4つの大きなグループにメトリックを分割しました：

1. 一般的なソフトウェア品質指標
2. 一般的なファームウェア品質指標
3. アルゴリズムの一般的なメトリック
4. ローカリゼーション固有のメトリック

これらの指標はすべて比較的標準的なものであるため、詳細には触れません。重要なことは、特定の問題についてメトリックが定義および識別されていることです。これは、オープンソースプロジェクトの開発者としておおよそ達成できることです。最終的に、受け入れの基準は、システムを展開する人によるプロジェクトの詳細に基づいて決定する必要があります。



ここで最後に繰り返しますが、メトリックはテストするのに素晴らしいですが、実装の理解と使用法の要件をチェックする代わりにはなりません。

アーキテクチャとAPI

私たちが解決しようとしている問題を入念に定義し、ソリューションスペースの理解を構築した後、最終的に実装に接する領域に飛び込むことができます。



私は最近、テスト駆動開発のファンになっています。ほとんどのエンジニアと同様に、私は開発プロセスが大好きで、テストを書くという考えは、最初は面倒に思えました。私が専門的にプログラミングを始めたとき、私はまっすぐ進み、開発後にテストを行いました（大学の教授から反対のことを言われましたが）。研究実装前にテストを作成すると、バグが少なくなり、テストカバレッジが高くなり、一般にコードが改善される傾向があることを示しています。おそらくもっと重要なことは、テスト駆動開発がアルゴリズム実装の大きな問題に対処するのに役立つと私は信じています。



それはどのように見えますか？



「実装NDT」（テストを含む）と呼ばれるモノリシックチケットを導入する代わりに、数千行のコード（効果的に表示および調査できない）をもたらす代わりに、問題をより意味のあるフラグメントに分割できます。

1. アルゴリズムのクラスとパブリックメソッドを記述する（アーキテクチャを作成する）
2. 公開APIを使用してアルゴリズムのテストを記述します（失敗するはずです！）。
3. アルゴリズムのロジックを実装する

したがって、最初のステップは、アルゴリズムのアーキテクチャとAPIを記述することです。他の手順については別の投稿で説明します。



「アーキテクチャを作成する」方法については多くの作品がありますが、ソフトウェアアーキテクチャの設計は黒魔術と関係があるように思えます。個人的には、ソフトウェアアーキテクチャは概念の境界を描くことと考え、問題を提起する際の自由度と、概念の観点からそれを解決する方法を特徴付けることを考えたいと思います。



では、NDTの自由度とは何でしょうか。



文献をレビューすると、スキャンと観察結果を提示する方法はいくつかあることがわかります（例：P2D-NDTおよびD2D-NDT）。同様に、高レベルのエンジニアリングペーパーでは、マップを表現する方法がいくつかあると述べています（静的および動的）、これも自由度です。最近の文献では、最適化の問題を再検討することも提案されています。ただし、実際の実装と文献を比較すると、最適化ソリューションの詳細でさえ異なる場合があることがわかります。



そしてリストはどんどん続きます。初期設計の結果に



基づいて、次の概念を決定しました。

• 最適化の問題
• 最適化ソリューション
• スキャンビュー
• マップビュー
• 初期仮説生成システム
• アルゴリズムとノードのインターフェース

これらのアイテムの中にいくつかの細分化があります。



アーキテクチャの究極の期待は、それが拡張可能で保守可能でなければならないということです。私たちの提案するアーキテクチャがこの希望に応えるかどうかは、時間だけがわかります。

さらに

もちろん、設計後は実装の時間です。Autoware.AutoにおけるNDTの実施に関する公式の仕事はで行ったAutowareのハッカソンが主催Parkopedia。



このテキストに示されているのは、設計フェーズの最初のパスにすぎないことを繰り返します。知られている敵に立ち向かうまでの戦いの計画はありません。ソフトウェア設計についても同じことが言えます。ウォーターフォールモデルの最終的な失敗は、仕様と設計が完璧であるという前提で行われました。言うまでもなく、仕様も設計も完璧ではありません。実装とテストが進むにつれて、欠陥が発見され、ここで説明する設計とドキュメントに変更を加える必要があります。



そして、それは大丈夫です。私たちはエンジニアとして、私たちの仕事ではありませんし、それと同一視することもできません。 NDTの開発についてそれがすべて述べられた後、私は良い第一歩を踏み出したと思います。



チャンネル登録：

@TeslaHackers — Tesla-, Tesla

@AutomotiveRu — ,

---

:

• - Automotive, Aerospace, (50+)
• [] (, , )
• DEF CON 2018-2019
• [] Motornet —
• 16 , 8
• open source
• McKinsey: automotive
• …