私のブックマーク
プランニングとスケジューリング
はじめに
今回はプランニングやスケジューリングに関するWebサイトで、皆さんの研究開発に役立ちそうなものをピックアップしてみました。ただ、ここで紹介するプランニングやスケジューリングは応用対象に応じて特化したものではなく、なるべく一般的なものに限定致しました。具体的には、まずプランニングやスケジューリングに関する基礎知識や先端知識が学べるサイトを紹介し、次に実際に動作可能なプランニングやスケジューリングのプログラムが入手できるサイトを、そしてプログラムの性能比較のために有用な様々なベンチマーク問題のサイトを紹介した後、最後にプランニングやスケジューリングに関連したメイリングリストのアーカイブサイトについて紹介します。
基礎、最新情報
現在のAIプランニングに関する知識を基礎から系統的に得るための大変充実した内容を持つサイトとしてアリゾナ州立大学の Subbarao Kambhampati 教授のホームページ[1]があります。Kambhampati 教授は半順序プランニングに関する著名な研究者ですが、彼のホームページには彼自身の研究グループの成果のみならず、プランニングに関するチュートリアルや講義資料などプランニングに関する最新の知識を得るのに非常に有用な情報が満載されています。
UK Planning and Scheduling SIGのホームページ[2]には、ヨーロッパを中心としたプランニング関連の研究情報などがまとめられています。論文や会議の情報、関連リンクなどの広範な情報が整理されており、ヨーロッパにおけるプランニング研究に関する情報を得たいときには重宝します。
ヨーロッパにおけるプランニング・スケジューリング関連の研究をコーディネイトする取り組むに関するサイトとしては、PLANET:European Network of Excellence in AI Planning[3]もあり、種々のアプリケーション領域や技術分野に応じた分科会の活動の様子がWebで紹介されており、過去の会議における発表スライドなども参照できるようになっています。
Electronic Transactions on Artificial Intelligence, ETAIのプランニング・スケジューリング研究領域[4]では、AIに関する電子ジャーナル(ETAI: Electric Transaction on Artificial Intelligence)におけるプランニング・スケジューリング領域に関する論文を収録しています。JAIRなどに比べるとマイナーな感は否めませんが、Web上で論文に対する質問やコメントのやりとりができるなどユニークな特徴もあります。
システム
プランニングやスケジューリングに関しては、Web上で様々なシステムが入手可能で、それを用いて実際に問題を解いてみたり、更にはそれらを拡張して新しいアルゴリズムをインプリメントすることができます。
まず、プランニングシステムに関しては、AI Planning Resources[5]に、インターネットを介してアクセス可能なAIプランナのリストがまとめられています。そこでは、既に歴史的なプランナから、最新のグラフプランに基づくシステムや不確実性のもとでのプランナに至るまで広範囲なシステムがカバーされています。他の同様のサイトとしては、集められているプランなの種類は少ないのですが、CS 541: Planner Software and Resources[6]と言った南カリフォルニア大学での授業用のページがあります。このページでは、実際にいくつかのプランナを動かしてみるための手順も含めてまとめてありますので、大変便利です。
スケジューリングに関しては、残念ながらオープンにされているシステムは少なく、それらをまとめたサイトはないのではないかと思います。
そのような状況で、法政大学の西岡靖之助教授の取り組みは特筆すべきものです。西岡先生は、 生産スケジューリング・ライブラリー[7]で、フリーのスケジューリングパッケージ、スケジューリング問題記述言語を提供すると共に、スケジューリング問題のサンプルを広く実業界から集める取り組みを行って、情報公開を行っています。また、スケジューリングパッケージのメーカであるアスプローバ[8]は、教育機関に限定ではありますが、自社の製品を無償で提供する取り組みを行っています。
問題例、ベンチマーク
自分で開発したプランナやスケジューラと、既存の他のシステムとの性能比較をするためには、ベンチマーク問題の存在が不可欠です。
AI Planning and Scheduling Systems: Domain Repository[9]は、AIプランニングシステムやスケジューリングシステムのドメイン、オペレータ記述仕様や具体的な問題記述の例をまとめてあり、開発したアルゴリズムの検証や他のシステムとの性能比較には有用です。
2000年に開催されたAIPS(The International Conference on Artificial Intelligence Planning and Scheduling Systems)[10]では、共通問題を用いたプランニングシステムの性能比較コンテストが行われて、その結果が公開されています。
スケジューリング関連では、Planning & Scheduling Benchmarks[11]には、種々のスケジューリング問題に関するベンチマーク問題がいくつか置かれていますが、近年は更新されていないようです。また、資源制約下のプロジェクトスケジューリングのベンチマーク問題を集めたサイトとしてはPROJECT SCHEDULING PROBLEM LIBRARY – PSPLIB[12]があります。また、OR関連ではスケジューリング問題など広範な問題を集めたサイトとして OR-Library[13]が有名です。
メイリングリスト・アーカイブ
AI Planning and Scheduling Mailing List Archive[14]では、UK Planning and Scheduling SIGが運営するメイリングリストの過去の記事を閲覧できます。また、Knowledge Based Scheduling archive[15]では、知的スケジューリングシステムの話題を中心 にしたメイリングリストの記事を見ることができます。
おわりに
以上のように、Web上ではプランニングやスケジューリングに関する多くの有用な情報が入手することができ、最新の研究成果のソースコードまでを手にいれて実際に動かしてみることもできます。残念ながら、それらのサイトの情報の多くは英語ですが、本稿が皆さんにプランニングやスケジューリングの最先端の研究に興味を持って頂くきかっけになれば幸いに思います。
References
- Prof. Subbarao Kambhampati
http://rakaposhi.eas.asu.edu/ - UK Planning and Scheduling SIG
http://www.research.salford.ac.uk/plansig/ - PLANET:European Network of Excellence in AI Planning
http://planet.dfki.de/ - ETAIのプランニング・スケジューリング研究領域
http://www.ida.liu.se/ext/etai/pas/index.html - AI Planning Resources
http://www.csc.ncsu.edu/faculty/stamant/planning-resources.html - Planner Software and Resources
http://www.isi.edu/~blythe/cs541/planners/ - 生産スケジューリング・ライブラリー
http://www.img.k.hosei.ac.jp/pslib/Default.htm - アスプローバ
http://www.asprova.com/jp/home/index.html - AI Planning and Scheduling Systems: Domain Repository
http://www.cs.umd.edu/projects/planning/index.html - AIPS2000(The International Conference on Artificial Intelligence
Planning and Scheduling Systems)
http://www.cs.toronto.edu/aips2000/ - Planning & Scheduling Benchmarks
http://www.NeoSoft.com/~benchmrx/ - PROJECT SCHEDULING PROBLEM LIBRARY – PSPLIB
http://halfrunt.bwl.uni-kiel.de/bwlinstitute/Prod/psplib/ - OR-Library
http://mscmga.ms.ic.ac.uk/info.html - AI Planning and Scheduling Mailing List Archive
http://www.research.salford.ac.uk/plansig/archive.htm - Knowledge Based Scheduling archive
http://www.dbai.tuwien.ac.at/marchives/sched-l/