tl/~vesper/resume

これは2003年度卒論発表用資料です。一部図が省略されています。

述語論理処理系上の工程スケジューリングの
定式化に関する研究

電気通信大学 知能機械工学科
宵 勇樹

研究の背景

私たちの住む社会において、自律型生産制御システムなどを対象とする状態空間が既知ではあるがあまりに広過ぎて、事前に全ての状態の対処法を準備できないケースや、惑星間の探査プローブなど未知の状況に適応する必要のあるシステムなどが存在する。これらの問題に対処するには知識をルールの形で蓄え、状況に応じて適切と判断されるルール群を用いた推論を行いながら、システム全体を制御していく能力が必要とされる。しかし知識を元にしたシステムは推論の実現が主に探索などによって行われるため、その処理に必要な時間の予測は困難になる。

このような状況のなかで、当研究室では実時間型の知識ベースシステムを用いて自律型生産システムや惑星間の探査などで用いるスケジューリング問題を解いている。

これまで当研究室では様々な問題を解決するためのスケジューラが個別に一から作られてきたが、これらスケジューラは問題は違っていても、統一できる部分があるのではないかと考えられる。もし共通部分をパッケージ化できれば、コードを書く手間が削減されスケジューラの作成が容易になるため、スケジューラで用いられる知識の取捨選択に時間を多く使うことが出来るようになる。

研究の目的・展開

本研究では実時間制御問題を解くために作られた7本のスケジューラを分析し、スケジューラの書き方の指針として提案する。さらにその中から共通部分をパッケージ化する。そしてパッケージ化の考察として、既存のスケジューラをパッケージに沿った形で書き直し、既存のものと同じ動作をするか確かめる。

実時間推論制御処理系RRCS

RRCS(Real-Time Reasoning Control System)とは、実時間の用途に対して述語論理に基づく問題解決を適用できるようにすることを目的として開発された、論理型プログラミング言語である。RRCSは、演算の行ない方を制御するためのメタ述語を備えている。この処理系を用いることで、推論に対して時間制限を与えたり推論に用いる知識の範囲を制限したりすることが可能となっている。

書き方の指針

既存の7本のスケジューラを分析した結果、共通している部分から、次のような書き方を提案した。

以上の内容からパッケージを作成した。

実装

パッケージ

パッケージは次のような仕様で作った。

メインループが前述の通り二つに分かれていて一本化出来ないため、メインループはパッケージに組み込まなかった。残りはデータ構造へのアクセスと、スケジューラ毎に異なる条件判定のみになったので、パッケージは結果としてデータ構造と、データ構造にアクセスするための述語の集まりになった。

データ構造

パッケージでは、次のデータ構造を定義した。

OrderList
OrderListはこれから行なってほしい要求を貯めたリストである。 このリストには、必要な要求のIDを格納しておき、詳しい情報はfactとして登録する。 factとは、''常になり立っている命題''のことであり、対義語として、''条件付きで成り立つ命題''である''rule''がある。
ExeQueue
ExeQueueはスケジューラが選択した行動を格納している。リストの要素としては、行動を行なった時間、行動の種類、行動の対象などがある。
EventList
EventListはスケジューラが行動した結果発生するイベント、または前もって予定されているイベントを格納している。リストの要素としては、行動を行なった時間、行動の種類、行動の対象などがあり、ExeQueueと同じ形ではあるが、ExeQueueは実際にスケジュールを実行するのに必要な最低限のスケジュールを扱い、EventListはスケジュールとして出力されない情報を扱う。
WorldState
現在の世界の状態を格納している変数群である。グローバルな変数によって構成される。WorldStateには、現在の世界の時間、各機械の状態(現在使われているかどうか等)、各加工物の状態(現在加工されているかどうか等)が含まれる。

実験

作成したパッケージを用いて、既存の7種類のスケジューラの中から2例を選び、それらのスケジューラと同等の処理を行なうスケジューラを作り、動作の確認を行なった。なおここではどちらのスケジューラも全解探索を行なっている。

実験1・総量規制を受ける工程スケジューラ

このスケジューラは、加工物のworkcellへの割り付け方を求める、電力・操作員・納期の制限を持った工程スケジューラである。

実験2・デブリ回収を目的とした軌道スケジューラ

このスケジューラは、宇宙ステーションから出た回収衛星が、衛星軌道上に散らばるゴミ(デブリ)を回収して再び宇宙ステーションに戻ってくるまでの道筋を求める軌道スケジューラである。

どちらの実験でも、既存のスケジューラと同じ答えを出すことができた。

考察

書き方に関する考察

今回既存のスケジューラを分析していった結果、メインループの書き方が二種類あることが分かった。並列型はメインループを構成する述語の数が直列型にくらべ少なく、見易い。しかし次の選択肢に移る際に余計な選択を、直列型よりも多く通ってしまうため効率は悪くなる。一方で直列型は並列型に比べ、余計な選択肢を通る必要がなく効率が良いが、述語の数が増加し見にくくなる。今回の実験では、2例のスケジューラに似た形であるという理由で直列型を採用した。しかし、この研究では直列型と並列型のどちらが良いか結論つけることはできなかったので、今後の課題としたい。

パッケージに対する考察

今回のパッケージ化では、時間の移動に、タスクの解放イベントをつかっているが、拘束条件が連続的に変化するスケジューラにはパッケージは利用しづらい。また、今回のパッケージを使うと、メモリ使用量が大幅に増加するため、今後メモリ使用量を減らす様にするとよい。

結論

この実験では、7本のスケジューラを分析し、そこから書き方の指針を提案した。さらに共通部分からパッケージを作成した。さらに書き方の指針やパッケージに沿った形で書いたスケジューラが既存のスケジューラと同じ動きをすることを確かめた。このパッケージを使えば、今までに比べ書かなければならないコード量が減少し、その結果今まで目につきにくかったバグにも気が付けるようになる。

参考文献

前に戻る