文献

J-GLOBAL ID：201002219811244168   整理番号：10A1611455

大規模タスク割当問題に対する協調的エージェントシミュレーション

A Cooperated Agent Simulation for Huge Task Allocation Problem

著者 (2件)： 高橋里司 (筑波大 大学院システム情報工学研究科) ,  松尾徳朗 (山形大 大学院理工学研究科)
資料名： 電気学会情報システム研究会資料  (電気学会研究会資料)
巻： IS-10  号： 73-75.77-82  ページ： 35-39  発行年： 2010年11月26日 
JST資料番号： L4571A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 車線が複数ある場合の除雪車による道路除雪作業は作業時間に依存したコストが発生するものとすると,複数除雪車の除雪経路を決定する問題といえる。本論文では,前記除雪問題を除雪作業の割当てを行うタスク割当て問題と,複数除雪車による除雪スケジュール問題を同時に最適化する問題として定式化した。前者はグラフとして与えられたタスクをいくつかの辺素な部分グラフに分割する作業が含まれる優モジュラ関数の最小化問題であり,最長有向路問題を用いたヒューリスティクスによって割当てを求める解法を示した。また,コスト最小となる部分グラフの割当てが与えられた場合に,他の除雪車と協調しながら経路を決定する必要があるのでエージェントシミュレーションによって割当てを改善しつつ,効率的な作業順序を求めるヒューリスティクスを提案した。具体的には,1)与えられた割当ての最短処理時間の計算,2)スタート地点から枝の向きに従う除雪,3)一定時間ごとに位置の報知,4)次の除雪作業タイミングの考慮,5)すべての除雪作業が終了したら作業終わり,6)作業時間短縮可能なタスクの交換といった行動規則に基づいて最適な作業順序を決定するものとした。

シソーラス用語： *エージェント ,  協調制御 ,  *資源割付 ,  *割当問題 ,  計算機シミュレーション ,  大規模系 ,  グラフ ,  発見的方法 ,  除雪 ,  作業時間
準シソーラス用語： エージェントシミュレーション ,  ヒューリスティクス

分類 (3件)： 人工知能  (JE08000Z) ,  オペレーティングシステム  (JD03020J) ,  その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (14件)：

• N. Katoh, and T. Ibaraki, Resource Allocation Problems. Handbook of Combinatorial Optimization (Vol.2), D. Z. Du, and P. M. Pardalos (Eds), pp. 159-260, 1998.
• 藤沢克樹, 梅谷俊治, 応用に役立つ50の最適化問題. 朝倉書店, 2009.
• 柳浦睦憲, 茨城俊秀, 組合せ最適化ーメタ戦略を中心としてー, 朝倉書店, 2006.
• E. M. Arkin and M. A. Bender and J. S. B. Mitchell The snowblower problem. Proc. of 7th International Workshop on the Algorithmic Foundations of Robotics, 2006.
• S. Iwata, A Fully Combinatorial Algorithm for Submodular Function Minimization. Journal of Combinatorial Theory, Series B, Vol.84, pp. 203-212, 2002.

タイトルに関連する用語 (5件)： 大規模 ,  タスク ,  割当問題 ,  協調 ,  エージェントシミュレーション