(57)【要約】【課題】収容器における物品の最適配置を提示するシステムの構築を目的とする。【解決手段】有限の内部空間を有する収容器内において複数の物品の配置態様を決定するための方法が提示される。方法は、収容器内に今回配置されるべき複数の物品に関する物品情報にして、少なくとも物品の種別の個数を示す物品情報をコンピューターが取得又は受信するステップと、収容器内の配置場所に対する物品の配置関係を定める解をコンピューターが生成するステップと、収容器内での物品同士の干渉に関する空間制約に照らして生成された解が実行可能か否かをコンピューターが判断するステップと、実行可能と判断された解の評価に基づいてコンピューターが候補解を決定するステップを含む。【選択図】図１
2017137195.tif 000002
【特許請求の範囲】
【請求項１】
有限の内部空間を有する収容器内において複数の物品の配置態様を決定するための方法であって、
前記収容器内に今回配置されるべき前記複数の物品に関する物品情報にして、少なくとも物品の種別の個数を示す物品情報をコンピューターが取得又は受信するステップと、
前記収容器内の配置場所に対する前記物品の配置関係を定める解をコンピューターが生成するステップと、
前記収容器内での前記物品同士の干渉に関する空間制約に照らして前記生成された解が実行可能か否かをコンピューターが判断するステップと、
実行可能と判断された解の評価に基づいてコンピューターが候補解を決定するステップを含む、方法。
【請求項２】
前述の収容器内の配置場所に対する前記物品の配置関係を定める解をコンピューターが生成するステップは、
前記コンピューターが複数の第１世代の解を生成し、
前記コンピューターが前記複数の第１世代の解の間で交叉処理を実行して複数の第２世代の解を生成することを含む、請求項１に記載の方法。
【請求項３】
前記複数の第１世代の解の少なくとも一方は、前記物品の配置可能個数が少ない前記配置場所から順に前記物品を配置する規則に基づいて生成される、請求項２に記載の方法。
【請求項４】
前記複数の第１世代の解の少なくとも一方は、少なくとも部分的にランダムに構築された解である、請求項２又は３に記載の方法。
【請求項５】
前述の収容器内の配置場所に対する前記物品の配置関係を定める解をコンピューターが生成するステップは、
Ｎ−１（但し、Ｎは３以上の自然数）世代の解と少なくとも部分的にランダムに構築された解の間で交叉処理を実行して複数のＮ世代の解を生成することを含む、請求項２乃至４のいずれか一項に記載の方法。
【請求項６】
前述の前記収容器内での前記物品同士の干渉に関する空間制約に照らして前記生成された解が実行可能か否かをコンピューターが判断するステップは、少なくとも１回の交叉処理を介して生成された所与の世代の解が生成される度に実行され、実行不可能な解がコンピューター上で消去され、又はコンピューター上で記憶されない、請求項２乃至５のいずれか一項に記載の方法。
【請求項７】
前記交叉処理は、一点交叉処理を含む、請求項２乃至６のいずれか一項に記載の方法。
【請求項８】
前述の実行可能と判断された解の評価に基づいてコンピューターが候補解を決定するステップは、
候補解として決定されたＮ−１（但し、Ｎは３以上の自然数）以下の世代の解よりも実行可能と判断されたＮ世代の解が優れているかコンピューターが判定することと、
前記Ｎ世代の解が前記候補解よりも優れている時、前記Ｎ世代の解を候補解としてコンピューターが決定することを含む、請求項２乃至６のいずれか一項に記載の方法。
【請求項９】
前記収容器内の配置場所に対する前記物品の配置関係を定める解をコンピューターが生成するステップは、ある種類の物品がある配置場所に配置可能であるか否かを示すブール値が記憶されたテーブルの参照に基づいて実行される、請求項１乃至８のいずれか一項に記載の方法。
【請求項１０】
前記収容器内での前記物品同士の干渉に関する空間制約に照らして前記生成された解が実行可能か否かをコンピューターが判断するステップは、前記収容器に設定された座標における各物品の位置及び／又は範囲を示す座標値が記憶されたテーブルの参照に基づいて実行される、請求項１乃至９のいずれか一項に記載の方法。
【請求項１１】
前記物品の優先度に照らして前記解同士が評価される、請求項１乃至１０のいずれか一項に記載の方法。
【請求項１２】
前記収容器内に収容可能な前記物品の最大数に照らして前記解同士が評価される、請求項１乃至１１のいずれか一項に記載の方法。
【請求項１３】
新たな解が生成される度に、この生成された解が実行可能か否かが判断され、また、実行可能と判断されるならば、現時点の候補解と比較され、候補解の更新の有無が決定される、請求項１乃至１２のいずれか一項に記載の方法。
【請求項１４】
前記収容器が食洗機であり、前記物品が食器である、請求項１乃至１３のいずれか一項に記載の方法。
【請求項１５】
請求項１乃至１４のいずれかに記載の方法をコンピューターに実行させるためのプログラム。
【請求項１６】
請求項１乃至１４のいずれかに記載の方法を実行する装置又はシステム。
【請求項１７】
有限の内部空間を有する収容器内において複数の物品の配置態様を決定するための装置であって、
前記収容器内に今回配置されるべき前記複数の物品に関する物品情報にして、少なくとも物品の種別の個数を示す物品情報を取得又は受信し、
前記収容器内の配置場所に対する前記物品の配置関係を定める解を生成し、
前記収容器内での前記物品同士の干渉に関する空間制約に照らして前記生成された解が実行可能か否かを判断し、
実行可能と判断された解の評価に基づいて候補解を決定するように構成される、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、有限の内部空間を有する収容器内における複数の物品の配置態様を決定するための方法及び装置に関する。
【背景技術】
【０００２】
近年、高齢者世帯や共働き世帯が増加している。これに伴い、生活をサポートするためのロボットやシステムなどが数多く研究開発されている。その中に家事作業の軽減を目的とした食器洗いに関する研究がある。非特許文献１は、ロボットが食後の食器片付けを行う際に必要な食器の位置・種類の情報を得る画像処理システムの提案を行う。また、非特許文献２は、ロボットハンドによる食器の把持戦略を提案し、キッチンに置かれた食器を食洗機へ配置するシステムの実現を行う。
【０００３】
他にも様々な研究が行われているが、多くは食器洗いの自動化を目的とし、非特許文献１のような画像中の食器認識に関する研究や非特許文献２のような食器の把持戦略に関する研究である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】佐藤知正,門脇啓太,森武俊,杉正夫,福井類:“食器片付けロボットのための画像処理システム,”第27回日本ロボット学会学術講演会,2009-9-1517.
【非特許文献２】水内郁夫、藤本純也、袖山慶直、山本邦彦、岡田慧、稲葉雅幸:“近接覚・触覚によるなぞり形状推定に基づく多種食器操作キッチンアシスタントシステムの実現,”日本ロボット学会誌、Vol.30,No.9,pp.889-898,2012.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
一方、人が食洗機を使用するときは「食洗機へ食器を配置する作業」だけでなく「食洗機を上手く使用するためには、どこにどの食器を配置するか考える作業」の方も手間であると考えられる。つまり、後者の作業を自動化するだけでも家事の手間をある程度削減できると考えられる。しかし、従来研究の多くは前者の作業に注目している。本出願は、「食洗機を上手く使用するためには、どこにどの食器を配置するか考える作業」について検討し、食洗機における食器の最適配置を提示するシステムの構築を目的とする。
【０００６】
本願発明者らは、有限の内部空間を有する収容器内における複数の物品の配置態様の最適化を促進するという新たな課題を見出した。
【課題を解決するための手段】
【０００７】
本開示の一側面に係る発明は、有限の内部空間を有する収容器内において複数の物品の配置態様を決定するための方法であって、
前記収容器内に今回配置されるべき前記複数の物品に関する物品情報にして、少なくとも物品の種別の個数を示す物品情報をコンピューターが取得又は受信するステップと、
前記収容器内の配置場所に対する前記物品の配置関係を定める解をコンピューターが生成するステップと、
前記収容器内での前記物品同士の干渉に関する空間制約に照らして前記生成された解が実行可能か否かをコンピューターが判断するステップと、
実行可能と判断された解の評価に基づいてコンピューターが候補解を決定するステップを含む。
【０００８】
幾つかの実施形態においては、前述の収容器内の配置場所に対する前記物品の配置関係を定める解をコンピューターが生成するステップは、
前記コンピューターが複数の第１世代の解を生成し、
前記コンピューターが前記複数の第１世代の解の間で交叉処理を実行して複数の第２世代の解を生成することを含む。
【０００９】
幾つかの実施形態においては、前記複数の第１世代の解の少なくとも一方は、前記物品の配置可能個数が少ない前記配置場所から順に前記物品を配置する規則に基づいて生成される。
【００１０】
幾つかの実施形態においては、前記複数の第１世代の解の少なくとも一方は、少なくとも部分的にランダムに構築された解である。
【００１１】
幾つかの実施形態においては、前述の収容器内の配置場所に対する前記物品の配置関係を定める解をコンピューターが生成するステップは、
Ｎ−１（但し、Ｎは３以上の自然数）世代の解と少なくとも部分的にランダムに構築された解の間で交叉処理を実行して複数のＮ世代の解を生成することを含む。
【００１２】
幾つかの実施形態においては、前述の前記収容器内での前記物品同士の干渉に関する空間制約に照らして前記生成された解が実行可能か否かをコンピューターが判断するステップは、少なくとも１回の交叉処理を介して生成された所与の世代の解が生成される度に実行され、実行不可能な解がコンピューター上で消去され、又はコンピューター上で記憶されない。
【００１３】
幾つかの実施形態においては、前記交叉処理は、一点交叉処理を含む。単純な交叉処理によって次世代への移行が促進され得る。
【００１４】
幾つかの実施形態においては、前述の実行可能と判断された解の評価に基づいてコンピューターが候補解を決定するステップは、
候補解として決定されたＮ−１（但し、Ｎは３以上の自然数）以下の世代の解よりも実行可能と判断されたＮ世代の解が優れているかコンピューターが判定することと、
前記Ｎ世代の解が前記候補解よりも優れている時、前記Ｎ世代の解を候補解としてコンピューターが決定することを含む。
【００１５】
幾つかの実施形態においては、前記収容器内の配置場所に対する前記物品の配置関係を定める解をコンピューターが生成するステップは、ある種類の物品がある配置場所に配置可能であるか否かを示すブール値が記憶されたテーブルの参照に基づいて実行される。
【００１６】
幾つかの実施形態においては、前記収容器内での前記物品同士の干渉に関する空間制約に照らして前記生成された解が実行可能か否かをコンピューターが判断するステップは、前記収容器に設定された座標における各物品の位置及び／又は範囲を示す座標値が記憶されたテーブルの参照に基づいて実行される。
【００１７】
幾つかの実施形態においては、前記物品の優先度に照らして前記解同士が評価される。
【００１８】
幾つかの実施形態においては、前記収容器内に収容可能な前記物品の最大数に照らして前記解同士が評価される。
【００１９】
幾つかの実施形態においては、新たな解が生成される度に、この生成された解が実行可能か否かが判断され、また、実行可能と判断されるならば、現時点の候補解と比較され、候補解の更新の有無が決定される。
【００２０】
幾つかの実施形態においては、前記収容器が食洗機であり、前記物品が食器である。
【００２１】
本開示の一態様に係るプログラムは、上述のいずれかに記載の方法をコンピューターに実行させるためのプログラムであり得る。
【００２２】
本開示の一態様に係る装置又はシステムは、上述のいずれかに記載の方法を実行する装置又はシステムであり得る。
【００２３】
本開示の一態様に係る装置は、有限の内部空間を有する収容器内において複数の物品の配置態様を決定するための装置であって、
前記収容器内に今回配置されるべき前記複数の物品に関する物品情報にして、少なくとも物品の種別の個数を示す物品情報を取得又は受信し、
前記収容器内の配置場所に対する前記物品の配置関係を定める解を生成し、
前記収容器内での前記物品同士の干渉に関する空間制約に照らして前記生成された解が実行可能か否かを判断し、
実行可能と判断された解の評価に基づいて候補解を決定するように構成される。
【発明の効果】
【００２４】
本発明の一側面によれば、有限の内部空間を有する収容器内における複数の物品の配置態様の最適化を促進することができる。
【図面の簡単な説明】
【００２５】
【図１】本開示の一態様に係る方法に関する概略的なフローチャートである。
【図２】本開示の一例の実験におけるシミュレーション配置結果図及び写真である。
【図３】本開示の一例の実験におけるシミュレーション配置結果図及び写真である。
【図４】本開示の一例の実験における探索時間と食器枚数の関係を示すグラフである。
【図５】本開示の一態様に係る方法に関する概略的なフローチャートであり、遺伝的アルゴリズム（Genetic Algorithm（通称GA））に基づいて第２世代までの候補解を決定することを示す。
【図６】食器情報、ブール値、座標値、及び食器モデルが記憶されたテーブルの非限定の一例を示す概略図である。
【図７】食洗機の内部空間の配置場所の非限定の一例を示す概略図である。遺伝的アルゴリズム（Genetic Algorithm（通称GA））に基づく処理において配置場所が遺伝子座と呼ばれる。
【図８】食洗機の内部空間の配置場所の遺伝子座の非限定の一例を示す概略図である。
【図９】図８の遺伝子座に食器種が割り当てられた第１世代の第１解の非限定の一例を示す概略図である。
【図１０】図８の遺伝子座に食器種が割り当てられた第１世代の第２解の非限定の一例を示す概略図である。
【図１１】本開示の一態様に係る方法に関する概略的なフローチャートであり、遺伝子座に食器種を割り当てる非限定の一例の方法が示される。
【図１２】図９及び図１０の第１世代の第１及び第２解に対する１サイクル目の交叉処理を模式的に示す概略図である。
【図１３】図１２の交叉処理により生成される第２世代の第１及び第２解を示す概略図である。
【図１４】図９及び図１０の第１世代の第１及び第２解に対する２サイクル目の交叉処理を模式的に示す概略図である。
【図１５】図１４の交叉処理により生成される第２世代の第３及び第４解を示す概略図である。
【図１６】本開示の一態様に係る方法に関する概略的なフローチャートであり、遺伝的アルゴリズム（Genetic Algorithm（通称GA））に基づいて第Ｎ世代までの候補解を決定及び更新することを示す。
【図１７】本開示の一態様に係る方法に関する概略的なフローチャートであり、候補解の更新に併せて候補解に対して突然変異処理を実行することを示す。
【図１８】図１７のフローチャートで行われる突然変異処理を模式的に示す概略図である。
【図１９】図１８の突然変異処理により生成された改変解を模式的に示す概略図である。
【図２０】本開示の方法を実行するためのシステムの概略図である。
【発明を実施するための形態】
【００２６】
以下、図面を参照しつつ、本発明の非限定の例示の実施の形態について説明する。開示の１以上の実施形態及び実施形態に包含される各特徴は、個々に独立したものではない。当業者は、過剰説明を要せず、各実施形態及び／又は各特徴を組み合わせることができ、また、この組み合わせによる相乗効果も理解可能である。実施形態間の重複説明は、原則的に省略する。参照図面は、発明の記述を主たる目的とするものであり、作図の便宜のために簡略化されている場合がある。
【００２７】
以降の開示では、食洗機における食器の最適な配置場所を考える問題(以下、食器配置問題)を組合せ最適化問題と見なして最適配置を求める。しかしながら、食洗機は、収容器の一例であり、何らの限定を構成するものではない。別の収容器内に別の物品を配置することにも本願の開示例が適用可能であり、本願の特許請求の範囲の範囲内に在るものと理解される。
【００２８】
ある家庭にn種類の食器があり、食器種類の集合D={1,…、n}を定義する。また食洗機には食器を配置できる場所がm箇所あり、配置場所の集合P={1,…、m}を定義する。食器配置問題の解は食洗機のm箇所それぞれに、どの種類の食器を配置するのかを示すベクトルzで与えることができる。つまり、解zは要素数mで、要素jの値zjは配置場所j(j∈P)に配置する食器の種類zj(zj∈D)を示す。なお、配置場所jにいずれの食器も配置しない場合はzj=0とする。
【００２９】
食器配置問題の目的関数は「食洗機を上手く使用している食器配置かどうか」を評価すべきである。この「上手い」の定義は「食洗機により多く食器を配置すること」や「洗いたい食器を優先してより多く配置すること」または「より確実に洗える配置にすること」など作業者や状況に応じて変化してくると考えられる。つまり、目的関数は「上手い」の定義ごとに応じて設定する必要がある。以上を考慮して食器配置問題を定義すると以下のように書ける。
【００３０】
−入力−
食器種類の集合D、配置場所の集合P、各食器形状Mi(i∈D)、食洗機形状T、配置場所の位置情報tj(j∈P)，「上手い」の定義(目的関数の指定)、食器の種類と枚数(以下、食卓情報ベクトル)x。但し、xは要素数nで、要素iの値xiは食器i(i∈D)の枚数を示す。また、D・P・Mi・T・tjは食器と食洗機によって一意に定まるが食卓情報ベクトルxは食事ごとに変化する。xは毎回直接入力するか、もしくは従来研究にもあるように食卓の画像から食器を認識する方法が考えられる。
【００３１】
幾つかの例においては、スマートフォーンやネットワーク接続されたカメラが用いられ、食卓上の食器の画像が取得される。この取得画像がコンピューターにより処理され、端的には画像処理され、各食器の種類と枚数が決定される。幾つかの場合、コンピューターは、食器形状のマッチングに基づいて、今回食洗機により洗浄されるべき各食器の種類及び枚数を決定する。例えば、画像取得された食器と、予め登録された浅皿、深皿、大皿、小皿等の食器種のモデルの適合度を算出する。コンピューターは、算出された適合度に応じて今回の食器の種類を判別する。このマッチング処理において、コンピューターは、各種類の食器の枚数も決定できる。なお、食器に対するカメラレンズの角度に応じて取得される食器の輪郭が変動する。幾つかの場合、撮像方法について教育が施される。別の場合、同一種の食器に関して複数種のモデルが用意され、カメラレンズの角度に起因する撮像される食器の輪郭の相違が対処される。別例においては、スマートフォーン等のモバイル電子機器の画面上において食器種及び枚数が手入力され、無線又は有線ネットワークを介して入力された情報がコンピューターに送信される。
【００３２】
幾つかの場合、食器の種類の特定により、食器の材質、食器の大きさ、食器の形状、及び食器の重量が特定できる。例えば、コンピューターは、食器種毎にこれらの詳細な情報が割り当てられたテーブルを有することができる。
【００３３】
なお、コンピューターは、ＣＰＵ等の演算処理部と、半導体メモリ、ハードディスク、光学又は磁気ディスク等の記憶部を含み、記憶部に記憶されたプログラムが演算処理部で実行され、様々な機能又は処理を具現化する。なお、コンピューターは、ネットワーク接続された２以上のコンピューターを意味する場合がある。つまり、ある処理がコンピューターにより実行される時、処理される情報がネットワークを介してコンピューター間を伝送される工程を含む。ネットワークは、例えば、電気又は光基準のネットワークである。ネットワークは、ＬＡＮ、ＣＡＮ、ＷＡＮ等の様々なネットワークであり得る。なお、コンピューターは、クライアントコンピューター、各種のサーバー、各種のアプリケーションサーバー他を含む。場合により、コンピューターが、装置と理解される。
【００３４】
−出力−
制約条件を満たす解の中で作業者が指定した目的関数を最大(または最小)にする解z
【００３５】
−制約条件−
食洗機と食器が干渉しない解，
2017137195.tif 000003
ここで、Mi(tj)は配置場所jに配置したときの食器Miの食洗機系での占める領域を表している。
食器同士が干渉しない解，
2017137195.tif 000004
食卓情報ベクトルxで構成できる解
2017137195.tif 000005
ここでyiは配置枚数指定ベクトルyの要素iの値である。
配置枚数指定ベクトルyとは要素数nで、要素iの値yiは解zにある食器iの枚数を示す。
【００３６】
−目的関数−
合計配置枚数を評価する関数、優先食器枚数を評価する関数、洗浄効率を評価する関数など
【００３７】
次のように食器配置問題の簡略化を行っても良い。
制約条件内の二つの干渉条件は入力情報である各食器形状・食洗機形状・配置場所の位置情報が分かれば求められると考えられるが本研究では簡単のため食洗機形状・配置場所の位置情報に代わり、全食器コンフィグレーションを入力とした。食器コンフィグレーションとはある食器がある配置場所に入るか否かのbool値と、入る場合の食洗機座標系での食器の位置・姿勢の情報と定義する。全食器コンフィグレーションは、食器種類数と配置場所数を掛け合わせた数の食器コンフィグレーション情報のことである。
【００３８】
本開示例では、目的関数を合計配置枚数を評価する関数と優先食器枚数を評価する関数の二つを用意した。合計配置枚数とは食洗機に配置する食器の合計枚数である。
2017137195.tif 000006
優先食器枚数とは食洗機に配置する優先順位の高い食器の枚数である。
2017137195.tif 000007
ここでyprikは優先食器枚数ベクトルypriの要素kの値である。優先食器枚数ベクトルypriとは要素数nで、要素kの値yprikは解zにある優先順位kの食器枚数を示す。この関数は、fpri1(z)からkの小さい順に優先して評価していく。なお、優先食器枚数を目的関数にする場合、入力に食器の順位情報が合わせて必要になる。
【００３９】
−最適解探索アルゴリズムの概要−
本開示例では、図１のような流れで最適解探索アルゴリズムを構築した。まず、入力情報を取得し、解を一つずつ作成して行く。解の列挙方法については後で述べる。初めの実行可能解(制約条件を満たす解)が発見できたらそれを候補解とする。以降、発見できた実行可能解は目的関数を用いて候補解と比較し、より適した解の場合は候補解を更新する。解の探索(列挙)が終了した時点の候補解を最適解とする。
【００４０】
−実験内容−
本開示例では、335[mm]×440[mm]の段ボールに食洗機カゴ「PANASONIC-SEP1N4590」を入れてカゴの約半分を計算に用いた。また5種類の食器を用い、洗いたい食器が各2枚ずつから各5枚ずつの4通りをそれぞれ目的関数が合計配置枚数の場合と優先食器枚数の場合で実験を行った。
【００４１】
−実験結果−
図２（ａ）は食器が各２枚ずつで目的関数が合計配置枚数の場合の探索結果と、得られた解通りに食器を食洗機に配置したときの様子である。そして、図２（ｂ）は目的関数が優先食器枚数の場合(大きい食器優先)の様子である。また、食器が各３枚ずつから各５枚ずつの場合は目的関数が合計配置枚数の場合と優先食器枚数の場合(大きい食器優先)で同じ結果になった。図３（ａ）は食器が各５枚ずつで目的関数が優先食器枚数の場合(大きい食器優先)の様子である。図３（ｂ）は目的関数が優先食器枚数の場合（小さい食器優先）の様子である。これらから、目的関数に応じて適した解が得られることが示せた。
【００４２】
−解の探索方法−
解は最大で(n+1)のm乗通りある。しかし、これを探索するには計算量が膨大になるため困難である。そこで、食卓情報ベクトルxを用いて、これに関する制約条件を満たす解の全探索をすることで計算量の削減を図る。以後、本研究ではこの探索方法を全探索とする。さらに本研究で用いる目的関数の場合、評価の高い解からの列挙が可能である。そこで、食卓情報ベクトルxに関する制約条件のみ満たし、目的関数による評価の高い解を順に探索していき、実行可能解が見つかり次第、探索終了する方法を試みた。なお、解の探索に際しては、スタンドアロン又はネットワーク接続されたコンピューターが用いられる。コンピューターは、リモートコンピューターであり得る。換言すれば、解の探索には、クラウドコンピューティングが用いられる。解の探索は、アルゴリズムに対して上述の「入力」に関して説明した食卓情報ベクトルを与えることにより実行される。幾つかの場合、アルゴリズムには、上述の「制約条件」、「目的関数」が組み込まれる。アルゴリズムは、コンピュータープログラムに記述され、コンピューターにより実行される。
【００４３】
図１を参照して予備的に説明すれば、物品情報の取得が、上述の「−入力−」の記述に照らして実行される。この過程で、コンピューターは、食洗機内に今回配置されるべき複数の食器に関する複数の食器情報にして、各食器情報が少なくとも各食器の種類と個数を示す複数の食器情報を取得する。次に、コンピューターは、食洗機内の配置場所に対する食器の配置関係を定める解を生成する。コンピューターにより実行されるプログラム／アルゴリズムの解は、上述の記述から理解できるように、食洗機のｍ箇所それぞれに、どの種類の食器を配置するのかを示すベクトルｚである。次に、コンピューターは、食洗機と食器との干渉に関する第１空間制約、及び／又は食洗機内での食器同士の干渉に関する第２空間制約に照らして、生成された解が実行可能か否かを判断する。次に、コンピューターは、所定の基準（目的関数）に即して、実行可能と判断された解同士を比較し、いずれを候補解とするかを決定する。
【００４４】
図１のように、実行可能な解が初回の解であれば候補解とされる。今回生成され、実行可能と判断された解が、現時点の候補解よりも目標関数に照らして優れているならば、今回生成された解により現時点の候補解が更新される。探索は、少なくとも２回以上行われる。幾つかの場合、規定の回数に到達した時の候補解が最終解となる。
【００４５】
幾つかの場合、所定の基準は、食器の種類の優先度に関する。今回の実行可能と判断された解における優先される種類の食器数が、現時点の候補解における優先される種類の食器数よりも大きければ、今回の解により現時点の候補解が更新される。幾つかの場合、所定の基準は、食洗機内に収容される食器の数を最大化することに関する。今回の実行可能と判断された解における食器数が、現時点の候補解における食器数よりも大きければ、今回の解により現時点の候補解が更新される。別の形態においては、別の基準が採用され、これに即して候補解の更新の有無が決定される。
【００４６】
図１に示す例においては、新しい解の生成の度に、制約条件を満足するか否かが判断され、これを満足するとすれば、続いて現時点の候補解との比較が行われる。
【００４７】
図４は食器が各２枚ずつから各５枚ずつの食卓情報ベクトルのときの全探索（目的関数：合計配置枚数）、合計配置枚数順の探索（目的関数：合計配置枚数）、優先食器枚数順の探索（目的関数：優先食器枚数）に要した時間を示している。優先食器枚数順の探索の場合、探索時間は１０秒程度になった。これは探索空間が狭くなったことで計算時間が短くなったと考えられる。全探索と合計配置枚数順の探索では同じ解が得られていることを確認した。
【００４８】
−結論−
食洗機における食器の最適配置を提示するシステムの構築を目指し、食器配置問題の定義を行い、解探索のプログラムを作成した。そして、実際に食器と食洗機の配置箇所を数カ所用いた簡単な場合に適切な解が得られることを確認した。また、目的関数と解の列挙方法によっては高速に最適解を導けることが分かった。
【００４９】
以下、図５乃至図２０を参照してより具体的に説明する。図５は、本開示の一態様に係る方法に関する概略的なフローチャートであり、遺伝的アルゴリズム（Genetic Algorithm（通称GA））に基づいて第２世代までの候補解を決定することを示す。図６は、食器情報、ブール値、座標値、及び食器モデルが記憶されたテーブルの非限定の一例を示す概略図である。図７は、食洗機の内部空間の配置場所の非限定の一例を示す概略図である。遺伝的アルゴリズム（Genetic Algorithm（通称GA））に基づく処理において配置場所が遺伝子座と呼ばれる。図８は、食洗機の内部空間の配置場所の遺伝子座の非限定の一例を示す概略図である。図９は、図８の遺伝子座に食器種が割り当てられた第１世代の第１解の非限定の一例を示す概略図である。図１０は、図８の遺伝子座に食器種が割り当てられた第１世代の第２解の非限定の一例を示す概略図である。図１１は、本開示の一態様に係る方法に関する概略的なフローチャートであり、遺伝子座に食器種を割り当てる非限定の一例の方法が示される。図１２は、図９及び図１０の第１世代の第１及び第２解に対する１サイクル目の交叉処理を模式的に示す概略図である。図１３は、図１２の交叉処理により生成される第２世代の第１及び第２解を示す概略図である。図１４は、図９及び図１０の第１世代の第１及び第２解に対する２サイクル目の交叉処理を模式的に示す概略図である。図１５は、図１４の交叉処理により生成される第２世代の第３及び第４解を示す概略図である。図１６は、本開示の一態様に係る方法に関する概略的なフローチャートであり、遺伝的アルゴリズム（Genetic Algorithm（通称GA））に基づいて第Ｎ世代までの候補解を決定及び更新することを示す。図１７は、本開示の一態様に係る方法に関する概略的なフローチャートであり、候補解の更新に併せて候補解に対して突然変異処理を実行することを示す。図１８は、図１７のフローチャートで行われる突然変異処理を模式的に示す概略図である。図１９は、図１８の突然変異処理により生成された改変解を模式的に示す概略図である。図２０は、本開示の方法を実行するためのシステムの概略図である。
【００５０】
以下、本開示の方法、例えば、図５、図１５及び図１６の方法が、図２０に示したシステム１００により実行されるものとして記述される。もちろん、図２０に示した以外の構成のシステムによっても本開示の方法は実行され得る。従って、図２０の直接的又は間接的な参照に基づく記述は、図２０以外の構成のシステムにおいても完全又は実質的に同一の態様（又はシステム構成の相違に起因する必要な変更を伴う態様）で実行され得るものと理解される。
【００５１】
図２０に示したシステム１００は、携帯端末１１０と、情報処理サーバー１２０を含む。携帯端末１１０と情報処理サーバー１２０は、いずれもコンピューターであり、少なくとも一つのＣＰＵと、ＣＰＵがアクセス可能な少なくとも一つのメモリーを含む。携帯端末１１０と情報処理サーバー１２０それぞれは、液晶表示パネルといった表示部又は表示装置、Ｉ／Ｏ回路、バス、ストレージ、画像処理回路、及び通信制御回路といった他のコンポーネントを含み得る。携帯端末１１０と情報処理サーバー１２０は、有線又は無線接続され、又は、１以上の中継器を介して接続され、又は、１以上のネットワークを介して接続される。携帯端末１１０は、例えば、スマートフォン、タブレットといった電子機器であり得る。携帯端末１１０は、より大型な持ち運びに適さない装置（デスクトップパソコン、ノートパソコン）により置換され得る。
【００５２】
情報処理サーバー１２０は、食洗機内に今回配置されるべき複数の食器に関する食器情報（物品情報）にして、少なくとも食器の種別の枚数を示す食器情報を取得又は受信する。例えば、携帯端末１１０がカメラを有する場合、携帯端末１１０のカメラが撮像した食卓上の画像が情報処理サーバー１２０に転送され得る。情報処理サーバー１２０は、この受信した画像を画像処理し、今回食洗機により洗われるべき食卓上の食器の種類と枚数を決定し得る。画像処理としては上述のマッチング処理が例示されるが、これに限られるべきものではない。別例においては、上述のように食器の種別の枚数がユーザーにより手入力される。ユーザーは、携帯端末１１０のアプリケーションを操作し、今回食洗機により洗われるべき食卓上の食器種毎の枚数を入力する。ユーザーにより携帯端末１１０に入力された情報が情報処理サーバー１２０に転送される。このようにして情報処理サーバー１２０は、今回食洗機により洗われるべき食器に関する情報を取得又は受信する。今回食洗機により洗われるべき食器に関する情報は、食器の種別の枚数を示す情報に加えて、優先的に洗われるべき食器の順位を示す情報を含み得る。
【００５３】
情報処理サーバー１２０は、次に、食洗機内の配置場所に対する食器の配置関係を定める解を生成する。食洗機の配置場所に対する食器の配置関係を定める解は、様々な手法により生成され得る。従って、図５及び図１６に示す遺伝的アルゴリズム（Genetic Algorithm（通称GA））が非限定の一例として把握される。しかしながら、以下、理解の更なる促進を図るため、遺伝的アルゴリズムの非限定の一例が詳細に記述される。
【００５４】
図５及び図１６を参照して情報処理サーバー１２０による候補解を決定する処理を説明する前に、図６を参照して情報処理サーバー１２０により参照されるテーブルについて記述する。図６の非限定の一例のテーブルは、食器情報を含む。食器情報は、今回食洗機により洗われるべき食器の種類別の枚数を含む。図示例のテーブルには、食器種Ｄ１〜Ｄ３が図示され、食器種Ｄ４以降の図示が省略されている。食器種は有限であり、例えば、１６種類の食器が用意される。一回の食事に際して用いられる食器の種類とその枚数は変動し得る。テーブルの食器情報は、上述の画像処理及び／又はユーザー入力に基づいて更新され得る。
【００５５】
テーブルには、ある種類の食器がどの配置場所に配置でき、どの配置場所に配置できないのかを示す情報が記憶される。前提として、図７に示すように、食洗機の内部空間の複数の配置場所には識別値が付与される。図７に示すように、図示例では、Ｐ０〜Ｐ１５の識別値が、配置場所に付与される。必ずしもこの限りではないが、食洗機の内部空間の配置場所は、例えば、食洗機の内部空間に配されるカゴによって決定付けられる。カゴは、食器を縦に保持するための１以上の保持部を有し得る。カゴは、洗浄に適するように底部に複数の穴を有し、また横壁に複数の穴を有し得る。
【００５６】
図示例を含む幾つかの場合、ある配置場所に対してある食器が配置可能であることと、ある配置場所に対してある食器が配置不可能であることがブール値により示される。図６の食器種Ｄ１は、図７の配置場所Ｐ０〜Ｐ２に配置することができ、従って、ブール値＝０である。図６の食器種Ｄ１は、図７の配置場所Ｐ３〜Ｐ８に配置することができず、従って、ブール値＝１である。図６の食器種Ｄ２は、図７の配置場所Ｐ０〜Ｐ２に配置することができず、従って、ブール値＝１である。図６の食器種Ｄ２は、図７の配置場所Ｐ３〜Ｐ８に配置することができ、従って、ブール値＝０である。他の食器種についても同様に理解される。配置可能な場合と配置不可能な場合の間でブール値を反転させることは当然に予期される。
【００５７】
テーブルには、ある種類の食器がある配置場所に配置される時のその食器の空間情報が記憶され得る。なお、ある種類の食器がある配置場所に配置できない時、その食器は、その配置場所において空間情報を持ち得ない。図６の食器種Ｄ１は、図７の配置場所Ｐ０〜Ｐ２に配置することができ、その場所で空間情報を持ち得る。図６の食器種Ｄ１は、図７の配置場所Ｐ３〜Ｐ８に配置することができず、従って、その場所で空間情報を持ち得ない。
【００５８】
図示例を含む幾つかの場合、ある配置場所に配置されたある種類の食器の空間情報が座標値を含む。図示例を含む幾つかの場合、ある配置場所に配置されたある種類の食器の空間情報が食洗機に設定された座標における座標値を含む。幾つかの場合、食洗機に設定された座標における座標値は食器の中心点又は干渉判断に際して参照される参照点であり得る。図示例では、空間情報を持たないことが、（０，０，０）により表される。
【００５９】
図示例を含む幾つかの場合、テーブルは、食器の種類別のモデルを含み得る。モデルは、３次元情報であり得る。モデルは、食器の最大幅、最大高さ（厚み）といった情報を含み得る。
【００６０】
ある配置場所に配置された食器と別の配置場所に配置された食器の干渉の有無は、座標値に基づいて、及び／又は座標値とモデルの組み合わせに基づいて判断され得る。例えば、図７の配置場所Ｐ３に第１種の食器が配され、図７の配置場所Ｐ１１に（第１種とは異なる）第２種の食器が配される時、配置場所Ｐ３の食器と配置場所Ｐ１１の食器の干渉の有無は、配置場所Ｐ３の食器の中心点とそのモデルから定まる空間領域と、配置場所Ｐ１１の食器の中心点とそのモデルから定まる空間領域の干渉の有無で判断される。配置場所Ｐ３の食器の空間領域と配置場所Ｐ１１の食器の空間領域の間に共通の座標空間が存在するならば、干渉有りと判断できる。配置場所Ｐ３の食器の空間領域と配置場所Ｐ１１の食器の空間領域の間に共通の座標空間が存在しなければ、干渉無しと判断できる。他の場所と他の食器の様々な組み合わせにおいても同様の説明が当てはまり得る。
【００６１】
ある配置場所にある種類の食器が配置される時、他の配置場所に配置される他の食器との干渉が生じるか否かは事前に検証可能であり得る。例えば、ある配置場所に配置されるある種類の食器について、食洗機の座標における座標値として、干渉判断に際して参照される参照点が設定され得る。対比される食器の参照点ベクトルの交差の有無により干渉の有無が判断され得る。参照点ベクトルは、食洗機の座標（０，０，０）から参照点（ｘ，ｙ，ｚ）に向かうベクトルである。
【００６２】
テーブルは、複数のテーブルに分割され得る。例えば、テーブルにおいて毎回更新されるべき情報を含む領域が更新テーブルとして用意される。テーブルにおいて毎回更新されない情報を含む領域が固定テーブルとして用意される。テーブルは、情報処理サーバー１２０に記憶され、又は、情報処理サーバー１２０とは異なる別の装置に記憶され得る。情報処理サーバー１２０は、サーバーの記憶領域に対してアクセスし、若しくは、無線、有線、又はネットワークを介して別の装置の記憶領域に対してアクセスし、テーブルを更新又は参照することができる。
【００６３】
図５及び図１６の例を含む幾つかの場合、遺伝的アルゴリズム（Genetic Algorithm（通称GA））に基づいて候補解が決定される。配置場所が遺伝子座と呼ばれ、図７に示した合計１６カ所の配置場所は、図８に示すような１６個の遺伝子座として単純化される。遺伝子座に対して食器種が割り当てられ、これにより、食洗機の配置場所に対する食器の配置関係を定める解が得られる。一つの遺伝子座が一つの配置場所に対応し、一つの遺伝子座に対して一つの食器が配置される。
【００６４】
図９及び図１０は、図８の遺伝子座に食器種が割り当てられた第１世代の第１解の非限定の一例を示す概略図である。図１０は、図８の遺伝子座に食器種が割り当てられた第１世代の第２解の非限定の一例を示す概略図である。情報処理サーバー１２０といったコンピューター上において図９及び図１０に例示される解は、食器種を示す情報（食器種に割り当てられた識別値、以下食器種ＩＤと呼ぶ）の集合として取り扱われ得る。例えば、２値信号の４ビットにより食器種ＩＤが指定される時、４ビット×１６＝６４ビットの信号列として解が取り扱われる。なお、配置場所にどの食器も配置されない場合、その配置場所の遺伝子座に００００といった固有値が割り当てられ得る。
【００６５】
図５から分かるように、情報処理サーバー１２０は、まず、第１世代の第１解を生成し得る（Ｓ５１）。情報処理サーバー１２０は、第１世代の第２解を生成し得る（Ｓ５２）。第一世代の解は、幾つかの場合、実行可能な解であり、別の場合、実行不可能な解であり得る。第１解よりも第２解が時間的に先に生成され、又は第１解と第２解が時間的に同時に生成される別例も想定される。
【００６６】
情報処理サーバー１２０（又はそのＣＰＵ（以下、同様））は、幾つかの場合、遺伝子座への食器種ＩＤの割り当て及び判定を繰り返すことにより解を生成する。情報処理サーバー１２０は、幾つかの場合、いずれの食器種ＩＤも配置することができない遺伝子座に食器ゼロを意味する識別値（この識別値は、図示例ではＤ０と表示されている）を付与し得る。
【００６７】
非限定の一例としては、情報処理サーバー１２０は、図１１に示す方法に即して第一世代の解を生成し得る。まず、情報処理サーバー１２０は、ある遺伝子座にある食器種ＩＤを割り当てる（Ｓ１１１）。次に、情報処理サーバー１２０は、その遺伝子座にその食器種ＩＤを割り当て可能であるか判定する（Ｓ１１２）。ある遺伝子座にある食器種ＩＤを割り当て可能であるか否かは、テーブルのブール値の参照、及び／又は、干渉の有無の判定に基づいて決定され得る。割り当て可能であれば、情報処理サーバー１２０は、次の遺伝子座に食器種ＩＤを割り当てる（Ｓ１１３）。続いて、次に、情報処理サーバー１２０は、その遺伝子座にその食器種ＩＤを割り当て可能であるか判定する（Ｓ１１４）。次に、情報処理サーバー１２０は、全遺伝子座へ食器種ＩＤを割り当てたか否か判断する（Ｓ１１５）。全遺伝子座に食器種ＩＤが割り当てられていない場合、ステップＳ１１３に戻る。全ての遺伝子座に食器種ＩＤが割り当てられている場合、解の生成を終了する（Ｓ１１６）。
【００６８】
情報処理サーバー１２０は、ステップＳ１１２で割り当て不可能と判定すると、次に、ステップＳ１１１で対象とした遺伝子座に対して今回の食洗の対象の全ての食器種ＩＤで割り当てを試したか否か判定する（Ｓ１１５）。換言すれば、情報処理サーバー１２０は、今回の食洗の対象の全ての食器種ＩＤでステップＳ１１１，Ｓ１１２を実行したか否か判定する。今回の食洗の対象の全ての食器種ＩＤで割り当てを試していない場合、ステップＳ１１１に戻り、その遺伝子座に別の食器種ＩＤが割り当てられる。今回の食洗の対象の全ての食器種ＩＤで割り当てを試した場合、食器ゼロを意味する識別値、Ｄ０がその遺伝子座に割り当てられる。
【００６９】
情報処理サーバー１２０は、ステップＳ１１４で割り当て不可能と判定すると、次に、ステップＳ１１３で対象とした遺伝子座に対して今回の食洗の対象の全ての食器種ＩＤで割り当てを試したか否か判定する（Ｓ１１７）。換言すれば、情報処理サーバー１２０は、今回の食洗の対象の全ての食器種ＩＤでステップＳ１１３，Ｓ１１４を実行したか否か判定する。今回の食洗の対象の全ての食器種ＩＤで割り当てを試していない場合、ステップＳ１１３に戻り、その遺伝子座に別の食器種ＩＤが割り当てられる。今回の食洗の対象の全ての食器種ＩＤで割り当てを試した場合、食器ゼロを意味する識別値、Ｄ０がその遺伝子座に割り当てられる。
【００７０】
幾つかの場合、第１世代の解の少なくとも一方は、食器の配置可能個数が少ない配置場所から順に食器を配置する規則に基づいて生成される。例えば、図７から分かるように、配置場所Ｐ３の空間は、配置場所Ｐ１３の空間よりも狭く、従って、配置場所Ｐ３には配置場所Ｐ１３よりも少ない種類の食器しか配置できない可能性がある。ある配置場所に配置可能な食器の種類が多いか少ないかは、用いられる食器と食洗機の内部構造（幾つかの場合、食洗機内に配置されるカゴの構造）に依存し得る。食器の配置可能個数が少ない配置場所から順に食器を配置する規則に則ることにより、できる限り短い時間及び／又は小さい計算コストで第一世代の解が生成され得る。
【００７１】
どの遺伝子座からどの食器種ＩＤを割り当てるかによって解に含まれる食器数や解に含まれる優先順位の高い、例えば、優先順位１位から３位までの食器数が変化する。かかる観点から、情報処理サーバー１２０は、配置場所（遺伝子座）の優先順位を示すテーブルを参照し得る。代替的又は追加的に、情報処理サーバー１２０は、食器種の優先順位を示すテーブルを参照し得る。
【００７２】
情報処理サーバー１２０は、次の表１に例示される、配置場所（遺伝子座）の優先順位を示すテーブルを参照し得る。なお、表１に示した配置場所は、図７の食洗機の内部空間の配置場所とは無関係であり得る。情報処理サーバー１２０は、表１のチャートの参照により配置場所（遺伝子座）の優先順位を知ることができる。優先順位の高い遺伝子座に食器種を割り当てることにより、一つの解に含まれる食器の数を最大化することが促進される。
【表１】
2017137195.tif 000008
【００７３】
ある配置場所に複数の食器種が配置可能な場合、後述の表２の食器種の優先順位が参照され、より優先順位の高い食器種ＩＤがその遺伝子座に割り当てられ得る。代替的又は追加的に、食器種の番号が小さい順、食器種の番号の大きい順、又はランダムに選択される食器種ＩＤが遺伝子座に割り当てられ得る。
【００７４】
幾つかの場合、情報処理サーバー１２０は、表２に例示される、食器種の優先順位を示すテーブルを参照し得る。情報処理サーバー１２０は、表２のチャートの参照により食器種の優先順位を知ることができる。優先順位が高い食器種ＩＤから遺伝子座への割り当てを行うことにより、一つの解に含まれる優先順位の高い食器数を最大化することが促進される。
【表２】
2017137195.tif 000009
【００７５】
ある食器種が複数の配置場所に配置可能な場合、前述の表１の優先順位が参照され、その食器種ＩＤが、より優先順位の高い遺伝子座に割り当てられ得る。代替的又は追加的に、配置場所の番号が小さい順、配置場所の番号の大きい順、又はランダムに選択される遺伝子座に食器種ＩＤが割り当てられ得る。
【００７６】
幾つかの場合、情報処理サーバー１２０は、一つの解を生成するに際して表１及び表２の両方のテーブルを参照し得る。
【００７７】
図１１のステップＳ１１１，Ｓ１１３で遺伝子座に割り当てられる食器種ＩＤは、ランダムに決定されたものであり得る。代替的又は追加的に、図１１のステップＳ１１１，Ｓ１１３で選択される遺伝子座は、ランダムに決定されたものであり得る。情報処理サーバー１２０は、ステップＳ１１１，Ｓ１１３で乱数生成器により出力される乱数により特定される食器種ＩＤを割り当て得る。情報処理サーバー１２０は、ステップＳ１１１，Ｓ１１３で乱数生成器により出力される乱数により特定される遺伝子座に食器種ＩＤを割り当て得る。情報処理サーバー１２０は、ステップＳ１１１，Ｓ１１３で、乱数生成器により出力される乱数により特定される遺伝子座に、乱数生成器により出力される乱数により特定される食器種ＩＤを割り当て得る。すなわち、幾つかの場合、第１世代の解の少なくとも一方は、少なくとも部分的にランダムに構築された解であり得る。乱数生成器は、ソフトウェア又はハードウェア又はこれらの組み合わせにより任意に構築され得る。
【００７８】
図９が示す解は、情報処理サーバー１２０により、（図１１の方法に即して、又は表１の参照により）優先順位の高い配置場所の遺伝子座にランダムに食器種ＩＤを割り当てることにより生成された実行可能な解である。図１０が示す解は、情報処理サーバー１２０により、（図１１の方法に即して）ランダムに指定される配置場所の遺伝子座にランダムに指定される食器種ＩＤを割り当てることにより生成された実行可能な解である。図９の解は、８つの食器を食洗機内に配置可能であることを示す。図１０の解は、７つの食器を食洗機内に配置可能であることを示す。食洗機内に配置される食器数を最大化することが目標であれば、図９の解が図１０の解よりも優れることになる。別の目標、例えば、食洗機内に配置される優先順位が高い、例えば、第１〜第３位の食器の数を最大化する目標に照らすと、図１０の解が図９の解よりも優れ得る。
【００７９】
幾つかの場合、第一世代の解の少なくとも一方又は両方とも実行可能であり、以降の世代の解が実行可能であることの確率を高めることに寄与し得る。
【００８０】
このように様々な方法で第一世代の解が生成され得る。
【００８１】
次に、情報処理サーバー１２０は、候補解を決定する（Ｓ５３）。第１解又は第２解が候補解として決定される。一例としては、図９の解が図１０の解よりも最大食器数が大きいため、図９の解が候補解として決定される。情報処理サーバー１２０は、候補解を任意の場所にあるメモリー又はレジスタに記憶し得る。情報処理サーバー１２０は、候補解が決定又は更新される度、携帯端末１１０に候補解を送信し得る。これにより、ある時間における最適な候補解がユーザーに提示されることが実現される。
【００８２】
次に、情報処理サーバー１２０は、（図５に示すように）第１世代の第１及び第２解に基づいて第２世代の第１及び第２解を生成する（Ｓ５４）。幾つかの場合、情報処理サーバー１２０は、第１世代の第１及び第２解の間で交叉処理を実行し、これにより、第２世代の第１及び第２解を生成する。交叉処理とは、一組の第１世代の解の一方の解の一部を、一組の第１世代の解の他方の解の一部で置換することを意味し得る。交叉処理は、図示例を含む幾つかの場合、一点交叉である。別例においては、複数点交叉、例えば、２点交叉が実行される。様々な種類の交叉がＧＡ分野で知られており、様々な種類の１以上の交叉が採用され得る。
【００８３】
図示例を含む幾つかの場合、情報処理サーバー１２０は、ステップＳ５４の一回の実行に際してサイクルカウント値を変化させる。幾つかの場合、第一世代の第１及び第２解に基づく交叉処理の合計回数が事前に設定されている。情報処理サーバー１２０がサイクルカウント値を更新することにより第Ｎ世代（Ｎは、３以上の自然数）への移行を判定することができる。一例としては、一つの解が図８のような１６個の遺伝子座を基礎とする場合、図１２乃至図１５を参照して後述するように１６回の交叉処理が実行され得る。サイクルカウント値の初期値がゼロの時、交叉処理の度にサイクルカウント値が＋１インクリメントされる。サイクルカウント値が１５に更新されると、情報処理サーバー１２０は、サイクルカウント値を初期値にリセットし得る。
【００８４】
第一世代の第１及び第２解が情報処理サーバー１２０のメモリー又はレジスタに記憶される時、情報処理サーバー１２０のＣＰＵは、メモリー又はレジスタにアクセスし、第１世代の第１及び第２解を読み出す。次に、情報処理サーバー１２０は、上述の交叉処理を実行し、新たに生成された第２世代の解をメモリー又はレジスタに記憶し得る。
【００８５】
次に、情報処理サーバー１２０は、第２世代の第１及び第２解のいずれかが実行可能か否か判定する（Ｓ５５）。実行可能であるかの判定は、干渉の有無の判定を含み得る。第２世代の第１解及び第２解のいずれかが実行可能であれば、第２世代のいずれかの解が候補解よりも優れているか判定する（Ｓ５６）。この判定は、様々な基準に照らして実行され得る。一例としては、解に含まれる最大食器数である。第２世代の解が候補解よりも優れているならば、情報処理サーバー１２０は、候補解を更新する（Ｓ５７）。これにより、第２世代の解が候補解となる。ステップＳ５６，Ｓ５７は、実行可能と判断された解の評価に基づいて候補解を決定するステップと理解することができる。
【００８６】
次に、情報処理サーバー１２０は、所定サイクル数実行したか否か判定する（Ｓ５８）。所定サイクル実行した場合、第Ｎ世代の処理に移行する（Ｓ５９）。所定サイクル数実行していない場合、ステップＳ５４に戻る。情報処理サーバー１２０は、サイクルカウント値の参照に基づいて、所定サイクル数を実行したか否か判定し得る。
【００８７】
情報処理サーバー１２０は、ステップＳ５５において第２世代の解のいずれもが実行可能でない場合、これらの第２世代の解を消去する（Ｓ５９１）。これにより、情報処理サーバー１２０におけるメモリー空間が無駄なデータで占められることが回避又は抑制される。ステップＳ５９１の後、ステップＳ５４に戻る。ステップＳ５６において第２世代の実行可能な解が候補解よりも劣る場合、ステップＳ５４に戻る。第２世代の実行可能な解は、情報処理サーバー１２０のメモリー又はレジスタに記憶され得る。第２世代の実行不可能な解は、情報処理サーバー１２０のメモリー又はレジスタに記憶されない又は（任意の適切なタイミングで）消去される。
【００８８】
図１２は、図９及び図１０の第１世代の第１及び第２解に対する１サイクル目の交叉処理を模式的に示す概略図である。図１３は、図１２の交叉処理により生成される第２世代の第１及び第２解を示す概略図である。図１２から分かるように、１回目の交叉処理により、第１世代の第１解の配置場所Ｐ０の遺伝子座に割り当てられた食器種ＩＤと第１世代の第２解の配置場所Ｐ０の遺伝子座に割り当てられた食器種ＩＤが置換される。これにより、第１世代の第１解の配置場所Ｐ０の遺伝子座に割り当てられた食器種ＩＤが第１世代の第２解の配置場所Ｐ０の遺伝子座に割り当てられた食器種ＩＤで置換された第２世代の第１解が生成される。また、第１世代の第２解の配置場所Ｐ０の遺伝子座に割り当てられた食器種ＩＤが第１世代の第１解の配置場所Ｐ０の遺伝子座に割り当てられた食器種ＩＤで置換された第２世代の第２解が生成される。
【００８９】
図１４は、図９及び図１０の第１世代の第１及び第２解に対する２サイクル目の交叉処理を模式的に示す概略図である。図１５は、図１４の交叉処理により生成される第２世代の第３及び第４解を示す概略図である。図１４から分かるように、１回目の交叉処理により、第１世代の第１解の配置場所Ｐ０，Ｐ１の遺伝子座に割り当てられた食器種ＩＤと第１世代の第２解の配置場所Ｐ０，Ｐ１の遺伝子座に割り当てられた食器種ＩＤが置換される。これにより、第１世代の第１解の配置場所Ｐ０，Ｐ１の遺伝子座に割り当てられた食器種ＩＤが第１世代の第２解の配置場所Ｐ０，Ｐ１の遺伝子座に割り当てられた食器種ＩＤで置換された第２世代の第３解が生成される。また、第１世代の第２解の配置場所Ｐ０，Ｐ１の遺伝子座に割り当てられた食器種ＩＤが第１世代の第１解の配置場所Ｐ０，Ｐ１の遺伝子座に割り当てられた食器種ＩＤで置換された第２世代の第４解が生成される。
【００９０】
図１２乃至図１５に示される解のうち、図１５の第２世代の第４解の最大食器数が最大である。従って、第１世代の解に対する交叉処理における２回目のサイクルが終了した時点では、第２世代の第４解が候補解になる。サイクルの進展に従って、より優れた候補解が決定されることが理解できよう。
【００９１】
情報処理サーバー１２０は、続いて、第２世代の解と、少なくとも部分的にランダムに構成されたランダム解の間で交叉処理を実行して複数の第３世代の解を生成する。第３世代の解が、第１又は第２世代の解である候補解よりも優れていれば、第３世代の解が候補解になる。以下同様にして第４、第５、第６・・・世代の解が生成され、より優れた解が探索される。
【００９２】
図１６は、Ｎが３以上の自然数とする場合の情報処理サーバー１２０の処理を概略的に示す。まず、情報処理サーバー１２０は、Ｎ−１世代の実行可能な解を読み出す（Ｓ１６１）。Ｎ−１世代の実行可能な解として候補解が読み出され得る。Ｎ−１世代の実行可能な解としてメモリー又はレジスタに記憶された実行可能な解がランダムに読み出され得る。次に情報処理サーバー１２０は、ランダム解を生成する（Ｓ１６２）。幾つかの場合、ランダム解は、実行可能なランダム解である。図１１を参照して記述したようにステップＳ１１１，Ｓ１１３において、ランダムに指定された遺伝子座にランダムに指定された食器種ＩＤが割り当てられ得る。
【００９３】
次に、情報処理サーバー１２０は、ステップＳ１６１，Ｓ１６２で得られた第Ｎ−１世代の実行可能解とランダム解に基づいて第Ｎ世代の解を生成する（Ｓ１６３）。幾つかの場合、Ｓ１６３は、Ｓ５４と同様、第Ｎ−１世代の実行可能解とランダム解の間の交叉処理を実行し、これにより、第Ｎ世代の解（２つの解）を生成する。図５と同様、情報処理サーバー１２０は、ステップＳ１６３の実行の度にサイクルカウント値を更新し得る。
【００９４】
続いて、情報処理サーバー１２０は、第Ｎ世代の解が実行可能な判断する（Ｓ１６４）。第Ｎ世代の解が実行可能であるならば、情報処理サーバー１２０は、その第Ｎ世代の解が候補解よりも優れているか判定する（Ｓ１６５）。第Ｎ世代の解が候補解よりも優れているならば、情報処理サーバー１２０は、候補解を更新する（Ｓ１６６）。これにより、第Ｎ世代の解が候補解となる。次に、情報処理サーバー１２０は、所定サイクル数実行したか否か判定する（Ｓ１６７）。所定サイクル実行した場合、第Ｎ＋１世代の処理に移行する（Ｓ１６８）。所定サイクル数実行していない場合、ステップＳ１６３に戻る。情報処理サーバー１２０は、サイクルカウント値の参照に基づいて、所定サイクル数を実行したか否か判定し得る。
【００９５】
情報処理サーバー１２０は、ステップＳ１６４において第Ｎ世代の解のいずれもが実行可能でない場合、この第Ｎ世代の解を消去する（Ｓ１６９）。これにより、情報処理サーバー１２０におけるメモリー空間が無駄なデータで占められることが回避又は抑制される。ステップＳ１６９の後、ステップＳ１６３に戻る。ステップＳ１６５において第Ｎ世代の実行可能な解が候補解よりも劣る場合、ステップＳ１６３に戻る。第Ｎ世代の実行可能な解は、情報処理サーバー１２０のメモリー又はレジスタに記憶され得る。第Ｎ世代の実行不可能な解は、情報処理サーバー１２０のメモリー又はレジスタに記憶されない又は（任意の適切なタイミングで）消去される。Ｎ＋１世代の処理は、図１６を参照して記述したＮ世代の処理と同等であり得る（従って、冗長説明は省略する）。
【００９６】
上述した各特徴について様々なバリエーションが想定され、また、上述した各特徴の様々な組み合わせが想定される。全ての組み合わせについて記載することは当業者には冗長であり、従って、個々の組み合わせの記述が省略される。
【００９７】
最後に図１７乃至図１９を参照して突然変異処理について記述する。図１７は、本開示の一態様に係る方法に関する概略的なフローチャートであり、候補解の更新に併せて候補解に対して突然変異処理を実行することを示す。図１８は、図１７のフローチャートで行われる突然変異処理を模式的に示す概略図である。図１９は、図１８の突然変異処理により生成された改変解を模式的に示す概略図である。
【００９８】
図示例を含む幾つかの場合、情報処理サーバー１２０は、候補解の更新（Ｓ１７１）に際して、候補解の部分的な改変を行い（Ｓ１７２）、これにより得られた改変解が実行可能であるか判定する（Ｓ１７３）。情報処理サーバー１２０は、改変解が実行可能である時、改変解が候補解よりも優れるか否か判定し（Ｓ１７４）、優れるならば、候補解を更新する（Ｓ１７５）。この場合、改変解が候補解になる。
【００９９】
ステップＳ１７３で改変解が実行不可能であれば、改変解が消去される（Ｓ１７６）。ステップＳ１７４で改変解が候補解よりも優れていなければ、改変解が消去される（Ｓ１７６）。ステップＳ１７６に続いてステップＳ１７２が実行される。
【０１００】
候補解の部分的に改変は、例えば、図１８に示すように、ランダムで指定された遺伝子座、図１８では配置場所Ｐ６に対応の遺伝子座の食器種Ｄ０（Ｄ０は、食器無しを示す固有値である）をランダムに指定された食器種Ｄ３で置換する。これにより、図１９に示す改変解は、最大食器数が増加する。図１９の改変解が、ステップＳ１７３で実行可能と判定されることを条件として、図１８の候補解が図１９の改変解により置換される。
【０１０１】
上述の開示を踏まえると、当業者をすれば、各実施形態に対して様々な変更を加えることができる。請求の範囲に盛り込まれた符号は、参考のためであり、請求の範囲を限定解釈する目的で参照されるべきものではない。
【符号の説明】
【０１０２】
１１０  端末装置
１２０  情報処理サーバー
【図１】
2017137195.tif 000010
【図２】
2017137195.tif 000011
【図３】
2017137195.tif 000012
【図４】
2017137195.tif 000013
【図５】
2017137195.tif 000014
【図６】
2017137195.tif 000015
【図７】
2017137195.tif 000016
【図８】
2017137195.tif 000017
【図９】
2017137195.tif 000018
【図１０】
2017137195.tif 000019
【図１１】
2017137195.tif 000020
【図１２】
2017137195.tif 000021
【図１３】
2017137195.tif 000022
【図１４】
2017137195.tif 000023
【図１５】
2017137195.tif 000024
【図１６】
2017137195.tif 000025
【図１７】
2017137195.tif 000026
【図１８】
2017137195.tif 000027
【図１９】
2017137195.tif 000028
【図２０】
2017137195.tif 000029