(57)【要約】      （修正有）【課題】複数のアイテムが積載される初期状態と目標状態が与えられたとき、その積み替えコストを小さく（好ましくは最小）にする操作系列、コストと前工程又は後工程のスケジューラとを高速に求める。【解決手段】所定条件の下で積載可能な複数のアイテムの初期状態から目標状態への遷移経路をコンピュータにより探索する。前記初期状態から前記目標状態に至るまで、それぞれ一回の操作で遷移可能な状態間をエッジで繋ぎ、状態空間グラフを生成するステップと、ある状態から前記目標状態への操作コストの下限値を、前記ある状態における前記複数のアイテムの積載順序と、前記目標状態における前記複数のアイテムの積載順序とに基づいて、評価するステップと、前記下限値に基づいて、前記状態空間グラフ上の前記初期状態から前記目標状態までの操作コストが最小となる経路をヒューリスティック探索アルゴリムにより探索するステップとを備える。【選択図】図４
2014055037.tif 000002
【特許請求の範囲】
【請求項１】
所定条件の下で積載可能な複数のアイテムの初期状態から目標状態への遷移経路をコンピュータにより探索する方法であり、 
前記初期状態から前記目標状態に至るまで、それぞれ一回の操作で遷移可能な状態間をエッジで繋ぎ、状態空間グラフを生成するステップと、 
ある状態から前記目標状態への操作コストの下限値を、前記ある状態における前記複数のアイテムの積載順序と、前記目標状態における前記複数のアイテムの積載順序とに基づいて、評価するステップと、
前記下限値に基づいて、前記状態空間グラフ上の前記初期状態から前記目標状態までの操作コストが最小となる経路をヒューリスティック探索アルゴリムにより探索するステップとを備える方法。
【請求項２】
前記評価するステップにおいて、前記下限値を、前記ある状態における前記複数のアイテムの積載順序と、前記目標状態における前記複数のアイテムの積載順序とが異なる箇所の数に基づいて評価する請求項１に記載の方法。
【請求項３】
前記目標状態が、前記複数のアイテムを、複数の場所のうちの特定の場所に積載させた状態であるか、複数の場所のうちの任意の場所に積載させた状態であるかに応じて、前記異なる箇所の数のカウント方法が変更される請求項２に記載の方法。
【請求項４】
前記評価するステップに先立って、前記複数のアイテムよりも少ない数のアイテムが採り得る積載順序とその最適な部分操作コストとを前記コンピュータの記憶手段に記憶するステップを更に備え、
前記評価するステップにおいて、前記部分操作コストに基づいて前記下限値を演算する請求項１に記載の方法。
【請求項５】
前記評価するステップは、
前記ある状態における前記複数のアイテムを複数の部分に分割するサブ・ステップと、
前記分割された部分毎に、前記コンピュータの記憶手段から、対応する部分操作コストを読み出すサブ・ステップと、
前記部分操作コストの和に基づいて、前記下限値を演算するサブ・ステップと
を備える請求項４に記載の方法。
【請求項６】
前記下限値を演算するサブ・ステップは、
前記分割された部分同士の接続性に基づいて、前記下限値を演算する請求項５に記載の方法。
【請求項７】
前記複数の部分に分割するサブ・ステップは、
前記コンピュータの記憶手段に記憶されている限度において、一つの部分により多くのアイテムが含まれるように分割する請求項５に記載の方法。
【請求項８】
前記操作コストは操作回数である請求項１に記載の方法。
【請求項９】
前記ヒューリスティック探索アルゴリズムは、Ａ*（エー・スター）アルゴリズムである請求項１に記載の方法。
【請求項１０】
前記下限値は、ヒューリスティック関数の評価値である請求項９に記載の方法。
【請求項１１】
前記所定の条件として、前記複数のアイテムの積載を制限する条件を含み、
前記状態空間グラフを生成するステップは、前記積載を制限する条件に基づいて、前記状態空間グラフを生成する請求項１に記載の方法。
【請求項１２】
前記所定の条件として、一回の操作で移動可能なアイテムの数又は重量を制限する条件を含み、
前記状態空間グラフを生成するステップは、前記数又は重量を制限する条件に基づいて、前記状態空間グラフを生成する請求項１に記載の方法。
【請求項１３】
前記所定の条件として、積載可能なアイテムの総高さを制限する条件を含み、
前記状態空間グラフを生成するステップは、前記総高さを制限する条件に基づいて、前記状態空間グラフを生成する請求項１に記載の方法。
【請求項１４】
前記アイテムが、製鋼工程後、かつ熱延工程前の鉄鋼製品であり、
前記初期状態が、製鋼工程後の複数の前記鉄鋼製品の積載状態であり、
前記目標状態が、前記熱延工程に好適な複数の前記鉄鋼製品の積載状態である請求項１に記載の方法。
【請求項１５】
前記操作がクレーン操作であり、
前記探索するステップにより得られた前記操作コストが最小となる経路を、前記クレーン操作系列として出力するステップを更に備える請求項１４に記載の方法。
【請求項１６】
前記探索するステップにより得られた前記操作コストを、鉄鋼製造スケジューラへ出力するステップを更に備える請求項１４に記載の方法。
【請求項１７】
前記探索するステップにより得られた前記操作コストを、鉄鋼製造スケジューラからの前記初期状態及び目標状態を含む問い合わせに応答して、出力するステップを更に備える請求項１４に記載の方法。
【請求項１８】
コンピュータにより実行されると、前記コンピュータに請求項１に記載の方法を実行させるコンピュータ・プログラム。
【請求項１９】
鉄鋼製造スケジューラの一部として機能する請求項１８に記載のコンピュータ・プログラム。
【請求項２０】
所定条件の下で積載可能な複数のアイテムの初期状態から目標状態への遷移経路を探索するコンピュータであり、 
前記初期状態から前記目標状態に至るまで、それぞれ一回の操作で遷移可能な状態間をエッジで繋ぎ、状態空間グラフを生成する手段と、 
ある状態から前記目標状態への操作コストの下限値を、前記ある状態における前記複数のアイテムの積載順序と、前記目標状態における前記複数のアイテムの積載順序とに基づいて、演算する手段と、
前記下限値に基づいて、前記状態空間グラフ上の前記初期状態から前記目標状態に至るまでの操作コストが最小となる経路をヒューリスティック探索アルゴリムにより探索する手段とを備えるコンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、積載操作技術に関し、特に、積載可能な複数のアイテムを初期状態から目標状態に積み替える際に、そのコストをできるだけ小さくする積載操作系列を、より高速に求めるための技術に係る。
【背景技術】
【０００２】
産業界では、様々な場面で積載可能な複数のアイテムを初期状態から目標状態に積み替える必要が生じる場合がある。例えば、製鉄所では、連続する２つの工程である製鉄行程と熱延工程などにおいて、1つが10トン以上ある製品や半製品が中間在庫として山積みされている。これらの製品や半製品（以後、アイテムと呼ぶ）は、基本的に全てユニークであり、製鉄工程のアイテムの出力順と、圧延工程の入力順は一般に異なるため、積まれたアイテムを熱延工程で処理される順序にクレーンで並べ替える必要がある。その並べ替えのコスト（通常、クレーンの稼働回数として定義される）を減らすことは、コスト削減はもちろん、前後の工程のスループット向上にもつながり非常に重要である。現状では、このクレーン操作系列の作成は、クレーンオペレータ（人間）の勘と経験に委ねられており、ここで大きな潜在的ロスが発生している。
【０００３】
また、一般に熱延工程などはコンピュータによる生産スケジュールの自動生成が可能になっている。コンピュータによる生産スケジュール作成の際には、無数の生産スケジュール候補が生成される。その際、それぞれの候補について熱延工程前の並べ替えのコストも考慮できることが望ましい。これを実現するには、高速に近似解（具体的な操作系列は必要ではなく、そのコストのみを近似計算できれば十分）を計算する必要がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１１−１０５４８３号公報
【特許文献２】特開平０７−２９０１２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、複数のアイテムが積載される初期状態と目標状態が与えられたとき、その積み替えコストを小さく（好ましくは最小）にする操作系列を求める方法を提供することを目的とする。また、前工程又は後工程のスケジューラで必要となる、近似解（操作系列そのものではなく、そのコストのみ）を高速に計算する方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明を方法として把握すると、所定条件の下で積載可能な複数のアイテムの初期状態から目標状態への遷移経路をコンピュータにより探索する方法であり、前記初期状態から前記目標状態に至るまで、それぞれ一回の操作で遷移可能な状態間をエッジで繋ぎ、状態空間グラフを生成するステップと、ある状態から前記目標状態への操作コストの下限値を、前記ある状態における前記複数のアイテムの積載順序と、前記目標状態における前記複数のアイテムの積載順序とに基づいて、評価するステップと、前記下限値に基づいて、前記状態空間グラフ上の前記初期状態から前記目標状態までの操作コストが最小となる経路をヒューリスティック探索アルゴリムにより探索するステップとを備える方法である。
【０００７】
ここで、前記評価するステップにおいて、前記下限値を、前記ある状態における前記複数のアイテムの積載順序と、前記目標状態における前記複数のアイテムの積載順序とが異なる箇所の数に基づいて評価することができる。また、前記目標状態が、前記複数のアイテムを、複数の場所のうちの特定の場所に積載させた状態であるか、複数の場所のうちの任意の場所に積載させた状態であるかに応じて、前記異なる箇所の数のカウント方法が変更されてもよい。
【０００８】
また、前記評価するステップに先立って、前記複数のアイテムよりも少ない数のアイテムが採り得る積載順序とその最適な部分操作コストとを前記コンピュータの記憶手段に記憶するステップを更に備え、前記評価するステップにおいて、前記部分操作コストに基づいて前記下限値を演算することもできる。より具体的には、前記評価するステップは、前記ある状態における前記複数のアイテムを複数の部分に分割するサブ・ステップと、前記分割された部分毎に、前記コンピュータの記憶手段から、対応する部分操作コストを読み出すサブ・ステップと、前記部分操作コストの和に基づいて、前記下限値を演算するサブ・ステップとを備えることができる。なお、前記下限値を演算するサブ・ステップは、前記分割された部分同士の接続性に基づいて、前記下限値を演算することができ、前記複数の部分に分割するサブ・ステップは、前記コンピュータの記憶手段に記憶されている限度において、一つの部分により多くのアイテムが含まれるように分割することができる。
【０００９】
また、前記操作コストは単純に操作回数とすることができるし、操作の難易度等に基づく関数とすることもできる。また、前記ヒューリスティック探索アルゴリズムは、Ａ*（エー・スター）アルゴリズムを採用することができる。ここで、前記下限値は、ヒューリスティック関数の評価値とすることができる。
【００１０】
また、前記所定の条件として、前記複数のアイテムの積載を制限する条件、一回の操作で移動可能なアイテムの数又は重量を制限する条件、積載可能なアイテムの総高さを制限する条件を含み、前記状態空間グラフを生成するステップは、これらの条件に基づいて、前記状態空間グラフを生成することができる。
【００１１】
前記アイテムが、製鋼工程後、かつ熱延工程前の鉄鋼製品であり、前記初期状態が、製鋼工程後の複数の前記鉄鋼製品の積載状態であり、前記目標状態が、前記熱延工程に好適な複数の前記鉄鋼製品の積載状態とすることもできる。この場合、前記操作がクレーン操作であり、前記探索するステップにより得られた前記操作コストが最小となる経路を、前記クレーン操作系列として出力するステップを更に備えることができる。また、前記探索するステップにより得られた前記操作コストを、鉄鋼製造スケジューラへ出力するステップを更に備えることもできる。さらに、前記探索するステップにより得られた前記操作コストを、鉄鋼製造スケジューラからの前記初期状態及び目標状態を含む問い合わせに応答して、出力するステップを更に備えることもできる。
【００１２】
本発明をこれらコンピュータ・プログラム、コンピュータ・システムとして把握した場合にも、上述した本発明を方法として把握した場合と実質的に同一の技術的特徴を備える事ができる。
【発明の効果】
【００１３】
本発明によれば、複数のアイテムが積載される初期状態と目標状態が与えられたとき、その積み替えコストを小さく（好ましくは最小）にする操作系列を求める方法を提供することができる。また、前工程又は後工程のスケジューラで必要となる、近似解（操作系列そのものではなく、そのコストのみ）を高速に計算することができる。
【図面の簡単な説明】
【００１４】
【図１】図１は、本実施形態に係るコンピュータ１の利用態様を示す模式図である。
【図２】図２は、本実施形態に係るコンピュータ１のハードウェア構成を示すブロック図である。
【図３】図３は、コンピュータ１の機能モジュールを説明するブロック図である。
【図４】図４は、このコンピュータ１が実行する処理を説明するフローチャートである。
【図５】図５は、生成された状態空間グラフの概念図である。
【図６】図６は、評価する手順を説明する模式図である。
【図７】図７は、評価関数h(1)のカウントの仕方を説明する模式図である。
【図８】図８は、各状態の評価値を計算する際のフローチャートである。
【図９】図９は、評価関数h(2)の計算方法を上位概念的に説明する図である。
【図１０】図１０は、ブロック分割とパターン・データベース107の参照アルゴリズムについて説明する概念図である。
【図１１】図１１は、評価関数h(2)が最適解の下限になっていることを更に説明する模式図である。
【図１２】図１２は、αの計算について更に説明する模式図である。
【図１３】図１３は、実験１の結果を説明する図である。
【図１４】図１４は、実験２の結果を説明する図である。
【発明を実施するための形態】
【００１５】
実施形態
図１は、本実施形態に係るコンピュータ１の利用態様を示す模式図である。ここで、コンピュータ１は、製鉄業で利用される。製鉄業においては、一般に、製鉄工程で製造された半製品（以下、アイテムという）を次工程である熱延工程（熱間圧延工程）へ送るため、これらを一時的に保管する中間在庫置場が設けられる。ここで、製鉄工程から搬出されたアイテムの状態（初期状態）から、次工程である熱延工程に適したアイテムの状態（目標状態）へ、アイテムを積み替える必要があるが、この積み替え操作を行う最適な操作系列をコンピュータ１が計算する。また、製鉄工程や熱延工程などはコンピュータ・システムによる生産スケジュールの自動生成が可能になっている。コンピュータ・システムによる生産スケジュール作成の際には、無数の生産スケジュール候補が生成される。ここで、コンピュータ１は、それぞれの候補について製鉄工程後、熱延工程前の積み替えのコストについて、高速にその近似解を計算することができる。その結果、コンピュータ・システムはより適切な生産スケジュールを作成することができる。この場合、コンピュータ１は、コンピュータ・システムと一体的に構成されてもよいし、別々に構成されてもよい。
【００１６】
図２は、コンピュータ１のハードウェア構成を示すブロック図である。コンピュータ１のハードウェア構成は、（低速及び高速の）バス１０、バス１０に接続されるＣＰＵ（演算制御装置）１１、ＲＡＭ（ランダム・アクセス・メモリ：記憶装置）１２、ＲＯＭ（リード・オンリ・メモリ：記憶装置）１３、ＨＤＤ（ハード・ディスク・ドライブ：記憶装置）１４、通信インタフェース１５、入出力インタフェース１６を備えている。さらに、入出力インタフェース１６に接続されるマウス（ポインティング装置）１７、フラット・パネル・ディスプレイ（表示装置）１８、キーボード１９等を備えている。なお、コンピュータ１は一般的なパーソナル・コンピュータ・アーキテクチャを採用するものとして説明したが、例えば、より高いデータ処理能力や可用性を求めて、ＣＰＵ１１やＨＤＤ１４等を多重化することができる。また、デスクトップ型の他、ラップトップ型やタブレット型のパーソナル・コンピュータなど、様々なタイプのコンピュータ・システムを採用することができる。
【００１７】
このコンピュータ１のソフトウェア構成は、基本的な機能を提供するオペレーティング・システム（ＯＳ）と、OSの機能を利用するアプリケーション・ソフトウェアと、入出力装置のドライバ・ソフトウェアとを備えている。これらの各ソフトウェアは、各種データと共にRAM１２上にロードされ、CPU１１等により実行され、コンピュータ１は全体として、図３に示す機能モジュールを構成し、図４に示す処理を実行する。
【００１８】
図３は、コンピュータ1の機能を説明する機能ブロック図である。このコンピュータ1は、入力モジュール（入力手段）101、生成モジュール（生成手段）102、評価モジュール（評価手段）103、探索モジュール（探索手段）104、出力モジュール（出力手段）105を備えている。更にコンピュータ1は、事前演算モジュール（事前演算手段）106、パターンDB（記憶手段）107を備えている。
【００１９】
図４は、コンピュータ1の処理を説明するフローチャートである。以下、このフローチャートに従って、コンピュータ1が行う処理を詳細に説明する。
【００２０】
まず、入力モジュール101が入力を受け付ける（S101）。入力される情報としては、アイテムの初期状態及び目標状態を示す情報（図５参照）、各種制限情報を含むことができる。制限情報としては、例えば、複数のアイテムの積載を制限する情報、一回のクレーン操作で移動可能なアイテムの数又は重量を制限する情報、積載可能な複数のアイテムの総高さを制限する情報などを含むことができる。なお、複数のアイテムの積載を制限する情報としては、安全上の観点から、例えば、下になるアイテムの大きさと上になるアイテムの大きさの関係が挙げられる。また、一回のクレーン操作で移動可能なアイテムの数又は重量を制限する情報としては、例えば、クレーンの仕様や安全上の観点から、最大個数や最大重量が挙げられる。さらに、積載可能な複数のアイテムの総高さを制限する情報としては、安全上の観点から、例えば、一カ所に積載可能な最大高さが挙げられる。その他、運用上の様々な要件について、制限情報として入力を受け付けることができる。例えば、中間在庫置場の場所の数の制限、中間在庫置場の使用率の向上、各積載されるアイテムの高さの平準化などを挙げることができる。
【００２１】
このように入力される情報は、ユーザ（操作者）からキーボード19やマウス17を用いてコンピュータ1に入力されてよいし、製鉄工程や熱延工程などのスケジューリングを行う生産スケジューラから入力されてもよい。この生産スケジューラが他のコンピュータ・システム上に存在する場合には、通信インタフェース15を介して情報が入力され、この生産スケジューラがコンピュータ1上に存在する場合には、例えば、ファイル交換により、情報が入力される。なお、ここで入力される全部の情報がユーザ又は生産スケジューラから入力されるものであってもよいし、一部の情報がユーザから入力され、他の一部の情報が生産スケジューラから入力されるものであってもよい。さらに、一部の情報がデフォルトで設定されていてもよい。
【００２２】
次に、生成モジュール102が先に受け付けた初期状態から目標状態に至るまで、それぞれ一回のクレーン操作で遷移可能な状態間をエッジで繋ぎ、状態空間グラフを生成する（S102）。図５は、生成された状態空間グラフの概念図である。前提として、ここでは中間在庫置場に、場所A、場所B、場所Cが存在する。また、初期状態では、場所Aに下から順に「*,5,1,*,2,7,8」のアイテムの山が、場所Bには下から順に「6,3,4,*,*」のアイテムの山が存在し、場所Cにはアイテムが存在しない。一方、目標状態では、場所A及び場所Bにはそれぞれ「*,*」のアイテムの山が、場所Cには下から順に「1,2,3,4,5,6,7,8」のアイテムの山が存在する。ここで、各数字はそれぞれユニークなアイテムを意味し、「*」は任意のアイテムを意味する。また、生成モジュール102は、状態空間グラフを生成する過程において、上述の各種制限情報に基づいて、状態空間グラフを生成する。例えば、クレーンのつり上げ最大個数等を考慮して、状態空間グラフが生成される。
【００２３】
次に、評価モジュール103が、先の状態空間グラフにおいて、ある状態から目標状態への操作コストの下限値を、ある状態における複数のアイテムの積載順序と、目標状態における複数のアイテムの積載順序とに基づいて、評価する（S103）。図６は、評価する手順を説明する模式図である。ここで、先の状態空間グラフ上で、初期状態から目標状態までの最短経路を求めることで最適なクレーンの操作系列を求めることができる。後述する通り、グラフ上の最短経路はA*などのヒューリスティック探索アルゴリズムで求めることができるが、より高速に最短経路を求めるには各状態から目標状態までの推定距離を計算する精度の良い評価関数が必要となる。なぜなら、初期状態から状態nまでのコストがg(n)、状態nから目標状態までの推定コストがh(n)で与えられるとき、A*はg(n)+h(n)の順に探索し、したがってh(n)が実際のコストに近ければ近いほど、探索する状態数が減り、より高速に最短経路を求める事ができる為である。評価関数とはこのhのことである。以下、本実施形態では、二種類の評価関数h(1)とh(2)と用いて、それぞれ操作コストの下限値を求める方法を説明する。なお、最適解を計算するヒューリスティックをh*としたとき、任意の状態ｘで、h(1)(x) ≦h(2) (x)≦h* (x)が成り立つ。
【００２４】
実施例１：評価関数h(1)
実施例１では、目標状態に含まれる各アイテムに関し、その上下のアイテムを目標状態と比較し、上下が異なる場所にカット（図中点線で示す）を入れる。このカットは、少なくとも一回はこの場所でクレーン操作により分断する必要があることを意味しており、カットの数は真の最適解の下限になっている。例えば、図６を参照し、ある状態（ここでは初期状態）における、場所Aに積載されているアイテム「7」に着目する（図中星印を付した）。一方、目的状態における場所Cに積載されているアイテム「7」に着目する（図中星印を付した）。両者を比較して、目標状態におけるアイテム「7」の上にはアイテム「8」、下にはアイテム「6」が存在する。一方、ある状態における「7」の上にはアイテム「8」が存在し、目標状態と一致するためカットは入らない。他方、ある状態における「7」の下にはアイテム「2」が存在し、目標状態と一致しないためカットが入る。同様に、すべてのアイテムについて検討し、この場合、8カ所のカットが入り、評価関数h(1)＝「8」を得る。
【００２５】
上述の通り、中間在庫置場には、場所A、場所B、場所Cが存在するが、目標状態における積載位置が限定される場合と、されない場合における評価関数h(1) のカウントの仕方を説明する。図７は、評価関数h(1) のカウントの仕方を説明する模式図である。図７（a）は目標状態において積載場所が場所Cに限定されている場合を、図７（b）は目標状態において積載場所が場所A乃至Cのいずれでもよい場合を示している。
【００２６】
図７（a）に示すように、目標状態の積載場所を限定したい場合は、所望の積載場所の下に仮想的なアイテム「T」があり、他の積載場所の下に仮想的なアイテム「*」があると見なし、同様の規則でカットを入れればよい。例えば、状態Xにおいて、場所Aに積載されているアイテム「1」に着目する（図中星印を付した）。一方、目的状態における場所Cに積載されているアイテム「1」に着目する（図中星印を付した）。両者を比較して、目標状態におけるアイテム「1」の下にはアイテム「T」が存在する。一方、状態Xにおける「1」の下にはアイテム「*」が存在し、目標状態と一致しないためカットが入る。同様に、状態Xにおいて、場所Bに積載されているアイテム「3」に着目する（図中丸印を付した）。一方、目的状態における場所Cに積載されているアイテム「3」に着目する（図中丸印を付した）。両者を比較して、目標状態におけるアイテム「3」の下にはアイテム「2」が存在する。一方、ある状態Xにおける「3」の下にはアイテム「*」が存在し、目標状態と一致しないためカットが入る。同様に、すべてのアイテムについて検討し、この場合、合計５カ所のカットが入り、評価関数h(1) ＝「5」を得る。
【００２７】
図７（b）に示すように、目標状態の積載場所を限定しない場合は、すべての積載場所の下に仮想的なアイテム「T」があると見なし、同様の規則でカットを入れればよい。例えば、状態Yにおいて、場所Aに積載されているアイテム「1」に着目する（図中星印を付した）。一方、目的状態における場所A乃至Cに積載されているアイテム「1」に着目する（図中星印を付した）。両者を比較して、目標状態におけるアイテム「1」の下にはアイテム「T」が存在する。一方、状態Xにおける「1」の下にもアイテム「T」が存在し、目標状態と一致するため、カットが入らない。同様に、状態Yにおいて、場所Bに積載されているアイテム「3」に着目する（図中丸印を付した）。一方、目的状態における場所A乃至Cに積載されているアイテム「3」に着目する（図中丸印を付した）。両者を比較して、目標状態におけるアイテム「3」の下にはアイテム「2」が存在する。一方、ある状態Xにおける「3」の下にはアイテム「T」が存在し、目標状態と一致しないためカットが入る。同様に、すべてのアイテムについて検討し、この場合、合計４カ所のカットが入り、評価関数h(1) ＝「4」を得る。
【００２８】
実施例２：評価関数h(2)
実施例１では、目標状態に含まれる各アイテムに関し、その上下のアイテムを目標状態と比較し、上下が異なる場所にカットを入れ、そのカットの数をカウントすることで、評価関数の評価値（下限値）を得たが、実施例２では、前処理をすることで、さらに効率的に評価値を得ることを可能にした。
【００２９】
すなわち、目標状態のアイテム数が一定数（例えば、５）以下の問題について、それらのアイテムが取り得る全ての並び（パターン）について事前演算モジュール106が事前に最適解を計算し、パターン・データベース107に記録しておく。各状態の評価値を計算する際には、図８のフローチャートが示すように、ある状態における複数のアイテムの山をあるアルゴリズム（後述）に従ってブロック（部分）に分割し（ステップS31）、各ブロックの評価値はパターン・データベース107を参照することで設定する（ステップS32）。元のアイテムの山全体の評価値（下限値）は、各ブロックの評価値の和、及びブロック間の接続性により計算することで（ステップS33）、よりよい評価関数h(2)とすることができる。
【００３０】
図９は、評価関数h(2) の計算方法を上位概念的に説明する図である。目標状態として、下から順に、「1,2,3,4,5,6,7,8,9」のアイテムの山を想定する。一方、ある状態において、下から順に「7,2,5,4,3,6,1,8,9」のアイテムの山が存在する。これを上から順に、b1からb4の４つのブロックに分割する（後述する）。パターン・データベース107には、目標状態のアイテム数が５つ以下の問題について、それらのアイテムが取り得る全ての並び（パターン）について最適解の操作回数（ステップ数）が記憶されており、ブロックb1からb4に対して、それぞれ部分最適解h(b1)=1,h(b2)=1,h(b3)=7,h(b4)=1を得る。一方、各ブロック間の接続性に応じて０又は１をとるα1からα4が定義される（後述する。ここでは、いずれも０）。そして、評価関数h(2)=Σ(h(bi)-αi)=10を得る。
【００３１】
図１０は、ブロック分割とパターン・データベース107の参照アルゴリズムについて説明する概念図である。事前に、1〜kの全ての順列について、最適値を計算し、パターン・データベース107に記録する（この実施例ではk=5とする）。すなわち、アイテムの山の並びが「1」、「1,2」、「2,1」・・・「5,4,3,2,1」の全ての最適解を計算し、記録しておく（図中（１）参照）。次に、目標状態に関係のないアイテムがある場合は、事前にその場所で分割し、以下の処理は分割したそれぞれの部分について適用する（図中（２）参照）。次に、パターンDBで参照可能な最長のブロックを探索するために、山の一番上のアイテムから順番に以下の処理A,Bを繰り返す（図中（３）参照）。A：下方向にスキャンしていき、アイテムの最大値と最小値と、及び”最大値−最小値＋１”の値を計算する。B：先頭からの個数と、計算した値が等しくなるアイテムは、先頭から当該アイテムまでが連番を構成すると評価できる（図１０では丸印で表記）。次に、全ての場所でチェックし、最大のブロックを探す（図中（４）参照）。ここでは、上から4番目から8番目の5つのアイテムが最長の連番でブロックを構成できることが分かる。次に、その部分をパターン・データベース107で検索する（図中（５）参照）。このとき、全ての値に関し、最小値を引くことで正規化する（連番を1から始まるようにする）。すなわち、「6,3,4,5,2」を1から始まるように正規化し、その結果の「5,2,3,4,1」をパターン・データベース107に問い合わせ、h(b3)=7を得る。次に、最大ブロックを得た後の残りの部分は、本アルゴリズムを再帰的に適用しても良いし（評価関数h(2)）、実施例１として説明した通常の評価関数h(1)に切り替えても良い（図中（６）参照）。次に、ブロックの分割部分については、上側のブロックの一番下のアイテムと、下側のブロックの一番上のアイテムが、目標状態において連続している場合α＝1とし、それ以外はα＝0とする（図中（７）参照）。ここでは、α3＝0である。
【００３２】
図１１は、評価関数h(2)が最適解の下限になっていることを更に説明する模式図である。まず、biがある状態のアイテム列で、bi’がbiを整列したアイテム列とする（図中（１）参照）。次に、元問題をdisjointな複数の部分問題に分割することを考える（図中（２）参照）。次に、パターン・データベース107に最適解を問い合わせる（図中（３）参照）。ここで、ブロックb1をb1’に整列させる最小コストはパターン・データベース107に記憶されている。また、その整列の際のオペレーションは、他のブロック（b2,b3）の並びに影響を与えないので、独立に計算し和をとっても下限の性質は維持される。なお、パターン・データベース107にはこのインスタンスの最適解の操作回数が記憶されている（図中（４）参照）。ここで、パターン・データベース107に登録するインスタンスについては、目標状態の山の位置は1つに限定し、初期状態はその山以外に設定する。また、緩和問題としての性質を維持するため、置き場の数や同時に運べる数は元問題以上にする必要がある。
【００３３】
図１２は、αの計算について更に説明する模式図である。α2の場合、ブロックb2の一番下のアイテムとb3の一番上のアイテム目標状態で連続しているならα2=1とし、それ以外の場合はα2=0とする（斜線の部分が目標状態でも同じアイテムならα2=0とする）。これは、パターン・データベース107では、目標状態は初期状態とは別の山の場所であることを前提にしている。そのため、元々連続している部分で分割した場合には最適解のコストが1多くなってしまうのでそれを補正するために1を引く必要があるということである。
【００３４】
以上、実施例１、実施例２の評価関数について説明した。
【００３５】
探索モジュール104は、実施例１又は実施例２の評価関数により得られた下限値に基づいて、先の状態空間グラフ上の初期状態から目標状態までの操作コストが最小となる経路をヒューリスティック探索アルゴリムにより探索する（ステップS104）。本実施形態では、A*アルゴリズムを用いて、初期状態から状態nまでのコストがg(n)、状態nから目標状態までの推定コストがh(n)で与えられるときg(n)+h(n)の順に探索する。なお、採用するヒューリスティック探索アルゴリムとしては、A*アルゴリズムの他、例えば、IDA* (Iterative Deepening A*)、SMA* (Simplified Memory-Bounded A*)、A* with Partial Expansionなどを挙げることができる。これらの具体的な経路探索方法については、周知であるので、その詳細な説明は省略する。
【００３６】
出力モジュール105は、探索結果を出力する（ステップS105）。出力される情報としては、初期状態から目標状態に至るまでの最適経路をクレーンの操作系列としてディスプレイ18上に出力することができる。また、初期状態から目標状態に至るまでの最適経路の最適ステップ数（操作回数）の情報を生産スケジューラへ出力することもできる。これらの一部の情報をユーザへ出力し、他の一部の情報を生産スケジューラへ出力してもよい。
【００３７】
以上、本発明の実施形態を詳細に説明した。なお、本発明の技術的範囲は実施形態に限定して解釈すべきでないことは勿論である。
【００３８】
本発明者らは本発明完成に至るまで数々の実験を繰り返してきたが、ここではその一部を紹介し、本発明の従来技術に対する有利な効果を確認する。
【００３９】
実験１
図１３は、実験１の結果を説明する図である。実施態様の方法が、一般的な従来技術であるダイクストラのアルゴリズム（以下、Dijkstra法とする）と比較して、どの程度探索空間を絞る効果があるのかを検証する実験を行った。実験条件としては、初期状態をランダムに生成し、各インスタンス、及び各種法ごとに、展開済みノード数、未展開ノード数、及び計算時間を測定した。ここで、アイテム（アイテム）数は7とした（これはDijkstra法で現実的に求解可能な最大サイズである）。山の置き場の数は5、クレーンで一度に運べる最大数は4、目標状態の山の位置は初期状態とは異なる場所とした。“Instance 初期状態”は、初期状態における、アイテムの並びを表している。実施例（1）はパターンDBを使わないヒューリスティックh(1)、実施例（2）はパターンDBを使うヒューリスティックh(2)である。展開済みノード数（#closednodes）、及び未展開ノード数（#open nodes）は、探索アルゴリズムの性能評価において、計算時間、及び必要メモリ量を評価する尺度として一般的に用いられる指標である。
【００４０】
この実験の結果、最適解を求めるのにDijkstra法では数分かかるインスタンスが、本発明の実施態様では1秒未満で求解可能となることが明らかとなった。また、探索空間の削減に関しては、展開済みノード数、及び未展開ノード数から、本発明の実施態様では従来手法に比べて、最大で1/1000の削減効果が認められる。
【００４１】
実験２
図１４は、実験２の結果を説明する図である。本実験では、Dijkstra法では現実的には解けない規模の大きなインスタンスを用い、パターンDBの効果の検証を行った。すなわち、「山の置き場の数」、「クレーンで一度に運べる最大数」は実験１と同一である。一方、パターンDB作成の際は、k=8とし、「山の置き場の数」と「クレーンで一度に運べる最大数」は十分大きな値を用いた。アイテムの数は16とし、最初の3インスタンスは完全にランダムに生成し、残りの3インスタンスは、より現実的なインスタンスを想定し、前半の8アイテムは1〜8をランダムにシャッフルし、後半の8アイテムは9〜16をランダムにシャッフルすることによって生成した（これは、現実的には、大域的にアイテムが散らばることはあまりなく、比較的局所的に散らばることが多いためである）。
【００４２】
この実験の結果、比較的簡単なインスタンス（求解時間が比較的短いもの）では、探索空間の大きさ（展開ノード数、未展開ノード数）に顕著な差は認められず、パターンDBを用いた方が探索空間が大きいものがあった（これは同一の評価値を持つノード間ではランダムに展開順が決定されるために生じる逆転現象であると考えられる）。一方、比較的難しいインスタンスでは、パターンDBの効果がうまく機能し、探索空間の大きさは最大で約1/4に、計算時間は最大で約1/3の削減が確認できた。
【符号の説明】
【００４３】
1…パーソナル・コンピュータ（コンピュータ・システム）、
11…ＣＰＵ（演算制御装置）、
12…ＲＡＭ（ランダム・アクセス・メモリ：記憶装置）、
13…ＲＯＭ（リード・オンリ・メモリ：記憶装置）、
14…ＨＤＤ（ハード・ディスク・ドライブ：記憶装置）、
17…マウス（ポインティング装置）、
18…フラット・パネル・ディスプレイ（表示装置）、
101…入力モジュール（入力手段）、
102…生成モジュール（生成手段）、
103…評価モジュール（評価手段）、
104…探索モジュール（探索手段）、
105…出力モジュール（出力手段）、
106…事前演算モジュール（事前演算手段）、
107…パターンDB（記憶手段）
【図１】
2014055037.tif 000003
【図２】
2014055037.tif 000004
【図３】
2014055037.tif 000005
【図４】
2014055037.tif 000006
【図５】
2014055037.tif 000007
【図６】
2014055037.tif 000008
【図７】
2014055037.tif 000009
【図８】
2014055037.tif 000010
【図９】
2014055037.tif 000011
【図１０】
2014055037.tif 000012
【図１１】
2014055037.tif 000013
【図１２】
2014055037.tif 000014
【図１３】
2014055037.tif 000015
【図１４】
2014055037.tif 000016