Saitekika

技術系のはなし

開発目的

身近なファミレスをお得で健康に楽しむ方法を開発する

システム概要

予算内で高カロリー・低塩分に注文するメニューの組み合わせを探す

システム詳細

1 . 対象店舗の決定

よりこのシステムを意義ものあるためにするには、対象店舗が多くの人々にとって馴染みのものにする必要性がある。そこで全国的に展開されていて日本人に最も親しみの深いファミレスの1つと言えるサイゼリヤを今回の対象とする。
サイゼリヤのグランドメニューがネット上で公開されているため、そこにj掲載されているメニューを本システムの対象として扱う。

www.saizeriya.co.jp

2 . 予算の設定

学生間で執り行われる飲み会代として一般的と考えられる

¥3,000

を今回の使用可能な予算に設定する。

3 . 定式化

この問題は以下のように定式化できる

上限金額 P_{max}=3,000[円]

上限塩分量 S_{max}=20.0[g]

i番目の注文メニューの金額 P_i[円]

i番目の注文メニューの塩分 S_i[g]

i番目の注文メニューのカロリー C_i[kcal]

としたとき

制約関数
\displaystyle{\sum_i P_i ≦ P_{max}}

\displaystyle{\sum_i S_i ≦ S_{max}}
において
評価関数
E(P_i,S_i,C_i)

を最大にする注文の組み合わせを見つける。

ここで評価関数E_i(P_i,S_i,C_i)について
・塩分量は少なく
・総カロリーは多く
・金額は多く使った方が多くの料理を注文できる
という点を考慮して以下のように定義した。

\displaystyle{E(P_i,S_i,C_i)=\frac{\sum_i P_i + \sum_i C_i}{\sum_i S_i}=\sum_i \frac{P_i + C_i}{S_i}}

4 . 使用するアルゴリズムの決定

ここで注文した各料理に対しての評価関数E_i(P_i,S_i,C_i)を

\displaystyle{E_i(P_i,S_i,C_i)=\frac{P_i + C_i}{S_i}}

と置くと

\displaystyle{E(P_i,S_i,C_i)=\sum_i E_i(P_i,S_i,C_i)}

と書ける。

ここまでを踏まえると以上は
重量制限を総金額,総塩分の制限に、
総価値の最大化を評価関数E_iの合計の最大化に置き換えたナップサック問題1の応用であるとみなすことが出来る。以下、サイゼリヤ問題と呼ぶこととする。

以上より、今回の問題は制約関数が一つ多いナップサック問題の応用に帰着することができた。ナップサック問題はNP困難2であるため、最適解を求めるのに今回は遺伝的アルゴリズムを用いて最適解に近い組み合わせを求めることに決める。

結果

上記で定めたサイゼリヤ問題を遺伝的アルゴリズムで解くとtable1のような近似最適解が得られた。

table1

考察

table1を見るとアルコールがあり実に楽しそうな結果が得られた。
このようになった理由は評価関数Eにあると考えられる。

いまEは以下のように定義されている。

\displaystyle{E(P_i,S_i,C_i)=\frac{\sum_i P_i + \sum_i C_i}{\sum_i S_i}}

塩分の総量が分母にあるため

\displaystyle{\sum_i S_i}= 0[g]

になるような注文方法だと評価関数Eが無限大に発散してしまう。

また、塩分のオーダーは高々10^1なのに対して金額やカロリーのオーダーは高々10^3である。
これでは評価関数内でそれぞれのパラメータを同等に扱えていない。
今回のケースでは、分母にあるオーダーの小さい塩分が他の二つよりも大きな影響を与えてしまっていることになる。

以上二つの理由より、評価関数の見直しが必要である。 ここで以下のように改めて評価関数E(P_i,S_i,C_i)を定める。

\displaystyle{E(P_i,S_i,C_i)=\sum_i C_i + \sum_i P_i - 100*\sum_i S_i}

こうすることにより ・0除算による評価関数の発散 ・金額/カロリー/塩分 のパラメータのオーダー違い を解決することが出来る。

上の場合と同様に

\displaystyle{E_i(P_i,S_i,C_i)=C_i + P_i - 100*S_i}

とすることで

\displaystyle{E(P_i,S_i,C_i)=\sum_i E_i(P_i,S_i,C_i)}

と書けるので、相変わらず遺伝的アルゴリズムによって近似解が求められる。サイゼリヤ問題に新しい評価関数を適用した問題をサイゼリヤ問題(改)と呼ぶことにする。

このサイゼリヤ問題(改)に対して再度遺伝的アルゴリズムを適用して最適なメニューの組み合わせを求める。

結果 その2

サイゼリヤ問題(改)に対して遺伝的アルゴリズムを用いたところ、table2のような近似最適解が求められた。

table2

結論

サイゼリヤを健康に楽しむためには酒類と炭水化物を大量に注文することが有効であることが本システムによって解明された。

これは他のファミリーレストランチェーンに対しても言えるのではないかと考えられるが、その一般性についての検証は今後の課題としたい。


1 . ナップサック問題
重量と価値の2つのパラメータを持つ色々な種類のお宝が目の前にある。
重量制限があるナップサックを用意し、総重量の制限内で価値最大となるお宝の持ち帰りの組み合わせを求める問題である。
NP困難であることが証明されている。

2 . NP困難
正面から戦うと時間がかかり過ぎてとても解けない問題

Tracking Manipulator

技術系のはなし

開発目的

モーター動作によるリンク機構の制御を応用した実用的なシステムを作成する。

システム概要

手の動作を認識しマニピュレータの先端が前にある物体の動きに追従してく。
figure1にシステム全体と動作のイメージを示す。

figure1

システム詳細

システム全体は3つのモーターと平行四節リンクで構成されている。
また、マニピュレータの先端には距離センサが3つ付けられている。

1 . マニピュレータ先端の位置制御の仕組み

figure1はfigure2のように簡略化できる。
ここでモーター1,2とリンクの結合部を原点にとり右手座標系を採用している。

figure2


黒丸●はマニピュレータ先端を示す。
このうち\theta_0はfigure1のモーター0で制御する。
これをY-Q平面で見たときの図をfigure3に示す。

figure3


\theta_1はモータ1で、\theta_2はモータ2でそれぞれ制御する。
マニピュレータ先端P(x,y,z)に向けて逆運動学によって\theta_0,\theta_1,\theta_2を決定する。
マニピュレータの腕の長さをどちらもlとすると逆運動学より

\theta_0=tan^{-1} \dfrac{z}{x}

\theta_1=tan^{-1} \dfrac{x}{\sqrt{x^2+z^2}} + cos^{-1} \dfrac{\sqrt{𝑥^2+y^2+𝑧^2}}{l}

\theta_2=tan^{-1} \dfrac{x}{\sqrt{x^2+z^2}} - cos^{-1} \dfrac{\sqrt{𝑥^2+y^2+𝑧^2}}{l}

が求まる。

制御したい位置の座標P(x,y,z)から上の式を用いて\theta_0,\theta_1,\theta_2を計算し、PID方式によって各モータの角度を制御する。

2 . マニピュレータ先端のセンサの仕組み

上で述べたように、マニピュレータ先端には3つの距離センサが取り付けられている。
その様子をfigure4に示す。

figure4

各センサは、目の前に物体があるとき、その物体との距離を返す。
検出可能な範囲内に物体がないときは非常に大きな値を返す。

この特性を利用して、目の前にある物体が移動した方向を以下のような原理で検出する。

例えば、物体がfigure5のように現在位置から右に移動したとする。

figure5

移動前、全てのセンサからは物体との距離が返されている。
移動後、センサ1,2からは物体との距離が返されるが、センサ0の前には物体が無いのでそのことを表す"非常に大きな値"がセンサから返される。
これを検知し、物体は「右に動いた」と判断する。
そして、物体の動いた方向にマニピュレータの先端も動かす。

次に物体とセンサが一定距離を保つようにする動作原理を説明する。
マニピュレータ先端に取り付けているのは距離センサなのでこれを利用する。

figure6


figure6に示す平面\alphaはマニピュレータ先端の距離センサで構成される平面である。
物体が平面\alphaに近づくと距離センサが返す値は小さくなるので「近づいた」と判断し、物体から離れるために物体の動きと同じ方向にマニピュレータ先端を移動させる。

同様にして、センサから遠ざかるように動いたときは平面\alphaから距離が離れ、センサの値は大きくなるので、マニピュレータ先端は物体を追うように動く。

このふたつの仕組みによって、距離センサで物体の動きを追跡することが可能になる。

3 . OpenGLによるマニピュレータの可視化

センサが認識した物体の位置と、現在のマニピュレーターの状態とを、OpenGLを用いて可視化できるようにした。
figure7にその様子を示す。

figure7