2024年度学院等開講科目工学院システム制御系システム制御コース

計画アルゴリズム

開講元: システム制御コース
担当教員: 倉林大輔
授業形態: 講義 (対面型)
メディア利用科目: -
曜日・時限 (講義室): 月3-4 (WL1-401(W541))
クラス: -
科目コード: SCE.A503
単位数: 100
開講時期: 2024年度
開講クォーター: 1Q
シラバス更新日: 2025年3月14日
使用言語: 英語

シラバス

授業の目的（ねらい）、概要

計画アルゴリズムのツールとなるグラフ理論・グラフ探索，サンプリング理論を概観した後，空間の構造化表現であるコンフィグレーション空間とそのクラス，サンプリング規範の探索アルゴリズムを学び，計画アルゴリズムの基本を修得します．さらに不確定性の表現と取り扱い，これを勘案した最適化手法について理解し，現実の計画問題に対する解法アルゴリズム設計のための基礎を修得します．

到達目標

本講義を履修することによって，計画アルゴリズムの基礎を理解することを到達目標とします。空間のモデル化，探索アルゴリズム，サンプリング規範アルゴリズム，不確定性の取り扱いについて理解でき，行動計画のアルゴリズム設計ができるようにすることを目標とします。

キーワード

計画問題，グラフ，コンフィグレーション空間，サンプリング，組み合わせ，不確実性，計算量

学生が身につける力

専門力
教養力
コミュニケーション力
展開力 (探究力又は設定力)
展開力 (実践力又は解決力)

授業の進め方

毎回の講義では，計画アルゴリズムに関する話題について，１回の講義で完結できる内容を抽出・整理し講義する．原則として座学講義とするが，適宜口頭試問等を行う．

授業計画・課題

	授業計画	課題
第1回	計画問題とは何か	計画問題の意味するところを理解するととに，計算量の概念を把握する．
第2回	位相とコンフィグレーション空間	計画問題で多用される抽象化された空間について，位相とコンフィグレーションを理解する．
第3回	サンプリング規範アルゴリズム	計画問題の解法のうち，サンプリングを規範とする方法について概念と解法を理解する．
第4回	組み合わせ計画アルゴリズム	計画問題の解法のうち，組み合わせ計画を規範とする方法について概念と解法を理解する．
第5回	行動決定と不確実性	計画問題への対処にあたって，行動主体および環境の不確実性についての概念と取り扱いを理解する．
第6回	フィードバック型計画	計画問題への対処にあたって，状態の計測に対するフィードバックとしての取り扱いを理解する．
第7回	計算の複雑さと計画問題	計画問題の性質としての計算量とソフトコンピューティングによる解法を理解する．

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。

教科書

Steven M. LaValle (2006) Planning Algorithms. Cambridge University Press.

参考書、講義資料等

特になし．講義各回において必要な資料は配布する．

成績評価の方法及び基準

成績評価は講義中の試問(30%)および期末のレポート(70%)により行う．

履修の条件・注意事項

線形システム，確率システムの基礎知識を有することが望ましい．