HOME    BRMSブログ  No.9 経路探索アルゴリズムをルールベースAIで実装する。

BRMS徹底活用ブログ

No.9 経路探索アルゴリズムをルールベースAIで実装する。

2016.11.25 Progress Corticon

本エントリーは株式会社アシスト様が寄稿したエントリー(https://www.ashisuto.co.jp/product/category/brms/progress_corticon/column/detail/brmstech09.html)を転載したものとなります。

No.9 経路探索アルゴリズムをルールベースAIで実装する。

2016年4月からProgress製品を担当しています棚橋浩志です。私はメインフレームでアセンブラ言語、フォートラン言語、コボル言語による開発から始まり、UnixでC言語、X-Windowsによる開発、最近はWindowsでVB、C#、java言語による開発を30年続けてまいりました。 プログラミング言語の特徴として低級言語を習得していれば他言語の習得それほど難しくはありませんでしたが、SQL言語は既存の概念が全く通用しませんでした。 ちょうど25年前Unixでの開発の時にOracleデータベースを使用する為に今までの手続き型プログラミング言語でもない、今主流のオブジェクト指向型プログラミング言語でもないSQL言語に初めて触れたました。
手続き型プログラミング言語であれば、処理の流れを想定して設計・開発して、処理に沿ったテストと漏れる場合のテストを実施、プログラムがAbendしたり異常終了すれば該当ラインからデータと処理の流れを遡っていけば原因が追及できてある種の安心感がありました。 しかしSQL言語は既存の開発手法では対応できずに、構文エラー以外は処理が見えず完全にデータ依存で、検証では可能な限りデータを作る作業が増え、本当に処理が正しいのかといつも不安に悩まされてきました。 今でもSQLの構文を作成する時には完全に思考を切り替えて考えているのですが、VisualStudioではC#はじめLINQという機能が搭載されていますが、開発では処理が見えないという点で使用を禁止しています。
そしてこの4月からProgress Corticonに携わっているのですが、ルール作成の場面ではオブジェクト指向型プログラミング言語の概念では対応できない事やさらには手続き型プログラミング言語の概念でも対応できない事や汎用化が難しい事が多々あり、SQL言語の概念が一番当てはまると思っていました。
そこで今回技術コラムを執筆するにあたって「Corticonは理解するにはSQL言語の概念で考える」と発想を転換して、SQL言語が優れている『再帰SQL(再帰的問合せ)』をCorticonで実装検証を記事にしてみたいと思います。

再帰SQL(再帰的問合せ)とは

再帰SQL(再帰的問合せ)とは、データベース等に階層構造をもつデータが格納されているテーブルに対して、再帰的に自分自身のテーブルに問合せを行う処理を指します。この時のポイントは完全にデータ依存であるために、再帰的に1回の問い合わせで終わる場合もあれば、数十回問い合わせても終わらない場合がある事です。
このために既存のプログラミング言語では処理が煩雑になり処理に含まれるバグも増えます。しかしSQL言語ではわずか数ステップで実装できてしまいます。

今回は飛行機での経路を例題に再帰SQL(再帰的問合せ)を作成してみましょう。
下記の図とテーブルは航空路線の出発地と到着地およびその費用を表しています。
[SQLはSAP SQLAnywhere v16を使用しています]

再帰SQL(再帰的問合せ)とは

このテーブルを使用して『札幌』から『石垣』までの経路と費用を計算したい場合どのようにしますか?

まず出発地が『札幌』のデータを抽出します。これは課題の出発地が『札幌』だからです。

SELECT 出発地,到着地,費用 FROM 航空路線 WHERE 出発地='札幌'

経路項目と搭乗回数項目を追加します。これを初期ブランチと呼ぶことがあります。

SELECT 出発地,到着地,費用,出発地||'/'||到着地 AS 経路,1 AS 搭乗回数 FROM 航空路線 WHERE 出発地='札幌'    ※赤字は追加部分(以下同じ)

次に再帰SQL(再帰的問合せ)の構文に変形します。

WITH RECURSIVE temp (出発地,到着地,費用,経路,搭乗回数)
AS
(
SELECT 出発地,到着地,費用,出発地||'/'||到着地 AS 経路,1 AS 搭乗回数 FROM 航空路線 WHERE 出発地='札幌'
)
SELECT 出発地,到着地,費用,経路,搭乗回数 FROM temp

次に再帰的問合せをUNION ALLで指定します。これを再帰ブランチと呼ぶことがあります。

WITH RECURSIVE temp (出発地,到着地,費用,経路,搭乗回数)
AS
(
SELECT 出発地,到着地,費用,出発地||'/'||到着地 AS 経路,1 AS 搭乗回数 FROM 航空路線 WHERE 出発地='札幌'
UNION ALL
SELECT temp.出発地,航空路線.到着地,temp.費用 + temp.費用,temp.経路||'/'||航空路線.到着地,temp.搭乗回数 + 1
FROM temp,航空路線
WHERE temp.到着地=航空路線.出発地

)
SELECT 出発地,到着地,費用,経路,搭乗回数 FROM temp

最後に到着地が『石垣』のレコードのみ抽出する条件を加えて終わりです。

WITH RECURSIVE temp (出発地,到着地,費用,経路,搭乗回数)
AS
(
SELECT 出発地,到着地,費用,出発地||'/'||到着地 AS 経路,1 AS 搭乗回数 FROM 航空路線 WHERE 出発地='札幌'
UNION ALL
SELECT temp.出発地,航空路線.到着地,temp.費用 + 航空路線.費用,temp.経路||'/'||航空路線.到着地,temp.搭乗回数 + 1
FROM temp,航空路線
WHERE temp.到着地=航空路線.出発地
)
SELECT 出発地,到着地,費用,経路,搭乗回数 FROM temp where 到着地='石垣'

実行結果結果を表示します。

実行結果結果を表示

SQLを使用すると僅か10ステップで該当する全データの抽出できました。

Cotrticonで実装する

Cortioconでの最初の作業は語彙ファイル sample.ecore を作成します。
様々な定義の仕方がありますが、SQL文に準じてデータの構造化を重視して以下の様に定義してみました。

3_Cotrticonで実装する

次にルールシートを作成します。SQLでの処理に準じて3つのルールシートを作成しました。

4_Cotrticonで実装する

sample01.ers と名付けたこのルールシートでは、「前提フィルタ」で航空路線テーブル.航空路線.出発地 入出力.出発地と同じデータのみ抽出します。条件はなく「前提フィルタ」を透過した全データを 0番の「アクション」にて temp.new[]で属性に必要なデータを格納して入出力.Tempに追加しています。「前提フィルタ」を使用しないで「条件」に記載する事も可能ですが、「前提フィルタ」を使用した方が様々な面で効率的です。

それでは18件のデータを登録して sample01.ers をテストしてみましょう。航空路線テーブルには表示されている先頭3件のデータのように18件のデータをセットしました。 そして入出力[1].出発地に『札幌』を、入出力[1].目的地に『石垣』をセットしてテストした結果は以下の図になりました。

5

この結果は下記SQLと同じになります。

SELECT 出発地,到着地,費用,出発地||'/'||到着地 AS 経路,1 AS 搭乗回数 FROM 航空路線 WHERE 出発地='札幌'

次に sample02.ers と名付けたこのルールシートでは再帰処理を作成します。ここでも様々なルールシートの作成方法がありますが、「前提フィルタ」でデータを抽出する方法かつ、 この sample02.ers を単純にループさせる方法を考慮して以下の図の様に作成しました。

6

まずは「前提フィルタ」で入出力.Temp.搭乗回数 =入出力.処理対象搭乗回数 + 1というデータのみ抽出します。 この「前提フィルタ」はまた透過するデータが0件になった時にループを中断させる役目もあります。
0番の「アクション」で 入出力.処理対象搭乗回数を+1カウントアップします。 そして条件を2つ設定します。入出力.Temp.乗継地 = 入出力.目的地入出力.目的地が検索された場合は処理を中断するために設定します。
他の「条件」と「アクション」は sample01.ers と似ています。入出力.Temp.乗継地 = 航空路線テーブル.航空路線.出発地で処理中の一時的な到着地である乗継地を航空路線の出発地から検索します。 また「条件」が満たされた時のアクションもtemp.new[]を実行していますが、 経路 = 入出力.Temp.経路 + '/' + 航空路線テーブル.航空路線.到着地、 搭乗回数 = 入出力.Temp.搭乗回数 + 1、 費用合計 = 入出力.Temp.費用合計 + 航空路線テーブル.航空路線.費用 と累積されているデータに、条件が満たされた航空路線テーブル.航空路線のデータを加えています。

ここまでの処理を確認する為にもルールフロー sample.erf を作成します。以下の図の様にしました。

7

こちらは sample01.ers と sample02.ers が処理順序に優先順位がある為に接続して作成しました。
それではテストしてみましょう。

8

紙面の関係で一部データを非表示にしていますが、搭乗回数1回と2回の全組み合わせ17通りが表示されました。

次にルールフロー sample.erfで再帰処理させるためにループを設定します。

9

それではテストしてみましょう。

10

こちらも紙面の関係で一部データを非表示にして各搭乗回数の最初のデータのみ表示していますが、搭乗回数1回から5回の全組み合わせ40通りが表示され正常終了しました。

ルールシート最後の処理は入出力.目的地 = 入出力.Temp.乗継地のデータのみ抽出する sample03.ers を作成します。 今回は抽出の代わりに入出力.目的地 <> 入出力.Temp.乗継地のデータを削除しました。このルールシートも「前提フィルタ」を使用しています。

11

最後にルールフローにsample03.ersを実装します。

12

いよいよ最後のテストをしてみましょう。

13

removeを実行している為に番号は歯抜けになりますが、SQLの時と同じ19通りが同じ値で抽出されました。

最後に

『Corticonで再帰SQL(再帰的問合せ)も簡単に実装できました。やはりSQLに似ていますね。』と締めくくりたかったですが、このルール作成に2.0MD試行錯誤しました。 Corticonの挙動が読めないことやCorticonのデータの処理実行順序が浮動的であること等はプログラミング言語で開発してきた私にとってSQLやLINQに共通する鬱屈(うっくつ)した気分になりました。またツールにありがちな『プログラミング言語なら簡単にできるのに!』と思う部分も多々ありました。

その一方でプログラミングなしでここまで実装できる事のメリットは大きいと思います。またルールを作成しながら都度テストで確認が取れる事のメリットも大きいと思います。
さらに期間によって費用が変わったり、航空路線の新設や廃止や期間による臨時便、経由地を抽出条件に加えたりする事もプログラミングなしの軽度な改修で拡張可能だと思われます。

今回は単純なデータを使いましたが、また機会がありましたら往復の航路を登録したり出発時間も取り入れた拡張可能版を作成・検証をしてみたいと思います。