経営課題にAIを!ビジネスインフォマティクス研究会 (第18回)
JSAI Special Interest Group on Business Informatics (SIG-BI #18)

Study of Factory Automated Guided Vehicles Systems
by using Multi-agent System and Contract Net Protocol
加藤大望

矢田昇平

倉橋節也

Daimotsu Kato, Shohei Yada and Setsuya Kurahashi
筑波大学University of Tsukuba
Abstract: 近年、生産性の向上等を目的とし、工場の Internet of things (IoT)化、スマート化が検討されている。このような工場では、加工中の製品が一方向に流れていく、従来型のベルトコンベア等を用いた生産システムとは異なり、Automated guided vehicles (AGV)を用いて複数工程を行き来しながら生産を行うフレキシブルなジョブショップ型の生産方式となる。本生産方式の課題は、タスクの適切なスケジューリングであり、最適解を保証することが難しい Non-deterministic
Polynomial time-hard (NP-hard)となることにある。加えて、本論文がモチーフとする半導体製造工
程では、微細な加工を行うことから大気中のごみによる汚染や搬送時の振動が製造歩留まりに大きな影響を与えるため、工場内の AGV は決められた搬送路上を通行し、搬送車を追い越すことができない制約条件が存在する。この制約により、AGV の空間干渉が生じるため、搬送路上の AGV は渋滞が生じ、その結果、適切な時機での製造装置に加工製品の受渡しができず、納期遅れが発生する等の課題が生じる。このような課題に対し、本論文では、Multi-agent system (MAS)を用いることで、搬送車の空間干渉モデルを考慮した交通流量に関する解析モデルの検討を行った。MAS を用いることで、搬送車の空間干渉をモデリングすることが可能となる。加えて、主問題を分割し、副問題として処理を行う Contract Net Protocol (CNP)を解析モデルに適用し、加工装置をタスク管理者、AGV は契約者として扱い、動的に契約交渉を行うとした。CNP を用いることで、AGV の割当てエージェントとタスク管理者エージェントで協調し、さらに、工場内におけるドメイン知識である渋滞の時系列情報を利用することで、AGV の渋滞緩和が可能か検討を行った。検討の結果、搬送車の空間干渉モデルのみを用いた計算では、単位時間あたり n =0.4台/s で流入した場合に渋滞が生じていたが、CNP を用いること、および AGV の車間距離 Lh を適切に調節することで、渋滞を緩和させられることを見出した。

1

研究背景、および目的

近年、生産性の向上等を目的とし、工場の IoT 化、スマート化が検討されている [1, 2]。このような工場では、加工中の製品が一方向に流れていく、従来型のベルトコンベア等を用いた生産システムとは異なり、AGV を用いて複数工程を行き来しながら生産を行うフレキシブルなジョブショップ型の生産方式となる。本生産方式の課題は、タスクの適切なスケ
ジ ュ ー リ ン グ で あ り 、 こ れ は Flexible Job ShopScheduling Problem (FJSSP)と呼ばれ、チューリングマシンでは最適解を保証することが難しい NP-hard になることにある [3, 4]。加えて、本論文がモチーフとする半導体製造工場では、微細な加工を行うことから大気中のごみによる汚染や搬送時の振動が製造歩留まりに大きな影響を与えるため、工場内の AGV は決められた搬送路上を通行し、搬送車を追い越すことができない制約条件が存在する [5, 6]。この制約により、AGV の空間干渉が生じるため、搬送路上のAGV は渋滞が生じ、適切な時機での製造装置に加工製品の受渡しができず、納期遅れが発生する等の課題が生じる。
このような課題に対し、本論文では、MAS を用いることで、搬送車の空間干渉モデルを考慮した交通流量に関する解析を行い、加えて、主問題を分割し、副問題として処理を行う Contract Net Protocol (CNP)を本解析モデルに適用し、解析を行った。

経営課題にAIを!ビジネスインフォマティクス研究会 (第18回)
JSAI Special Interest Group on Business Informatics (SIG-BI #18)

2AGV の空間干渉を考慮した解析
モデル

工場内 AGV システムでは、図 1 に示すような全長 L [m]である AGV が速度 v [m/s] で走行し、前方車との車間距離 Lh [m] を検知し、Lh を一定に保つように v を調整しながら走行する。この AGV の交通流量を最大化し、搬送路での渋滞発生を抑えるた
め、本研究においては MAS を用いた解析を行った。
解析では、各 AGV をエージェントとして扱い、AGVを生産ラインに単位時間あたり n [台/s] で流入した場合に流出する交通流量が AGV の車間距離 Lh に対し、どのように変化するかを解析した。解析では、
図 2 のような工場の製造ラインの一部を想定し、単位時間あたり n で搬送経路から加工装置の存在するイントラベイに AGV が流入し、反時計回りに搬送路を走行しているとした[7]。

図1

図2る。これは、イントラベイに流入または流出するAGV が搬送路の交差点において、車間距離 Lh を一定に保つために速度 v を調整するためであると考えられる。一方、交通流量は一度ピークを付けた後は一定の値を示すか、徐々に低下することが確認できる。図 3(a) では、時間 800 sec における交通流量の値を比較すると、車間距離 Lh に関しては、Lh = 3, 5m において約 0.35 台/s 示すが、Lh = 7, 9 m では、交通流量の低下が明確に確認できる。図 3(b)に示すように Lh = 7, 9 m では AGV 総数が時間 200 sec を超えると低下していくことが確認できる。
これは AGV が流入量 n = 0.4 では、搬送路から出ていく交通流量よりも高いことから搬送路上で渋滞が発生した結果、交通流量が低下したと考えられる。

AGV 間の関係

図3 (a) 交通流量の時間変化 (n = 0.4)(b) 搬送路上に存在する AGV 総数の時間変化 (n = 0.4)

工場内レイアウトイントラベイの搬送路の両側には、加工装置を配置し、流入した AGV が加工装置に製品の受渡しを行い、再び搬送路から流出するとした。本解析では、イントラベイから流出する際の単位時間あたりのAGV の台数を交通流量とし、Lh と n を変化させ、交通流量の解析を行った。n = 0.4 とした際の結果を図3 に示す。ここで、Lh を 1 ~ 9 m で変化させた場合における交通流量の時間変化を図 3(a)に、搬送路上に存在する AGV 総数の時間変化を図 3(b)に示している。
図 3 に示すように横軸が時間に対し、縦軸の交通流量は約 100 sec の時点でピークを持つことがわか

3

解析モデルへの CNP の適用

2 節では AGV の流量のみに着目したが、実際にはFJSSP を考慮する必要がある。タスク割当においては、交渉エージェント等を用いたタスク割当システムが検討されており、このシステムでは本研究で検討した渋滞情報（図 3 に示したような搬送路上に存在する AGV 総数の時間変化等）を各 AGV に与えることで、AGV が自律的に行動し、効率的なタスク処理を行う事が重要になると考えられる。そこで、本研究では、AGV に自律的な行動を与える検討を行い、

経営課題にAIを!ビジネスインフォマティクス研究会 (第18回)
JSAI Special Interest Group on Business Informatics (SIG-BI #18)

各 AGV に交渉エージェントの機能を与え、CNP に従い、タスクを交渉で各 AGV に割当てることを検討した[8]。本研究の場合、契約交渉の際には、タスクを与えるエージェントを管理者、入札するエージ
ェントを契約者とし、AGV は契約者として扱い、動的に契約交渉を行うとした。また、交渉の際には 契
約ネットプロトコルに基づいたメッセージがマネージャと 契約者の間でやり取りされる。タスク管理者と契約者の間の交渉の流れを図 4 に示す。

行っている。搬送炉内の AGV 数が増大した場合に、CNP を適用し、Lh を変更した場合において、渋滞が生じないことが確認できる。

図5 交通流量の時間変化

4結論

CNP を用いて装置をタスマネージャ、AGV を契約者として扱い、AGV の空間干渉を考慮した MASによる解析モデルを実証した。さらに契約交渉では、交通情報を用いて AGV 間の距離を動的に調整するとした。このモデルを用いることで、空間干渉モデルでは渋滞が生じる n = 0.4 の場合においても、輸送路上の AGV 総数の増加を抑制できることを確認した。本研究で検討したモデルは、AGV の空間干渉が生じる工場等において、AGV の交通流量解析が可能となるため、非常に有益であると考えられる。

参考文献[1] 内閣府『第 5 期科学技術基本計画』平成 28 年 1 月 22 日
[2] M. Hermann et al., “Design Principles for Industrie 4.0 Scenarios”49th Hawaii International Conference on System Sciences (HICSS),

図 4 タスク管理者と契約者の間の交渉の流れ

2018[3] M. R. Garey and David S. Johnson, “Computers and Intractability:

図 4 (a)に示すように、まず、タスク管理者は AGV にタスクを送信し、次に AGV はそのタスクを入札するかの判断を行い、入札が可能である場合は入札を行う。つづいて、タスク管理者は複数の入札に対し、落札者を選定する。落札者は、各 AGV の異質性（例えば、目的とする装置と AGV の距離など）を考慮し、落札者の AGV に結果を報告する。最後にタスクを落札した AGV は、自己の状況を考慮し、タスクを実行するかの判断を行う。なお、落札されたタスクが実行されなかった場合は、タスク管理者は別の契約者にタスクを割り当てるとした。加えて、図 4 (b)に示すように工場内におけるドメイン知識である渋滞の時系列情報を利用し、その値に伴い Lh を変更するとした。このアルゴリズムを AGV の空間干渉を考慮した解析モデルに適用した結果を図 5 に示す。
図 5 では図 3 で渋滞が生じた n = 0.4 の場合で計算を

A Guide to the Theory of NP-Completeness” W.H. Freeman. ISBN 07167-1045-5 (1979).
[4] P. Brucker and R. Schlie, “Job-Shop Scheduling with Multi-Purpose
Machines” Compu-ting, Volume: 45, p369-375 (1990).
[5] J. Tung et al., “Optimization of AMHS design for a semicon-ductor
foundry fab by using simulation modeling” Proceedings of the 2013
Winter Simulation Conference, 3829.
[6] K. Kumagai et al., “Maximizing traffic flow of automated guidedvehicles based on Jamolo-gy and applications” Advances in MechanicalEngineering, Volume: 10, Issue: 12, p1 (2018).
[7] 加藤 大望他 『マルチエージェントシミュレーションを用いた 工
場内無人搬送車システムの解析』 SIG-BI #14 (2019)[8]

R.G.Smith, ”The Contract Net Protocol: High-Level Commu-nication and Control in a Distributed Problem Solver,” IEEE Trans. on
Computers, Vol.C-29, pp.1104-1113 (1980)