オートマトンと状態遷移/ペトリネット、自動計画と数え上げ問題

オートマトン理論

オートマトン理論は、計算理論の分野の1つであり、コンピュータ科学において重要な理論の1つとなる。オートマトン理論は、有限状態機械（FSM）やプッシュダウンオートマトン、チューリングマシンなどの抽象的な計算機モデルを研究することによって、形式言語、形式文法、計算能力、計算可能性、自然言語処理などの問題を解決するために応用される。

オートマトン理論の中心的な概念は、オートマトンと状態遷移であり、オートマトンは、入力を受け取り、状態を変更して出力を生成する計算機の抽象的なモデルとなる。

オートマトン理論では、オートマトンの種類に応じて、計算能力や表現能力が異なる。有限状態オートマトン（FSM）は、有限個の状態を持ち、入力を受け取ることで状態を変更し、出力を生成する計算機となる。

オートマトン理論は、形式言語理論と密接に関連しており、特定のオートマトンが受け入れることができる言語のクラスや、ある形式言語を生成するオートマトンの存在や構築方法を決定することができる。また、計算理論やアルゴリズムの分野でも重要であり、オートマトンを用いたアルゴリズムの設計や、プログラムの検証などに適用される。さらに自然言語処理、認知科学などの分野で広く使用される。オートマトン理論には、オートマトンの理論的解析方法や、特定のオートマトンが受け入れることができる言語のクラスを決定することができる言語階層など、重要な概念が含まれている。

オートマトン

オートマトンは、計算機科学の分野で、入力を受け取り、内部状態を変更して出力を生成する計算機モデルの抽象的な形式となる。オートマトンは、有限状態オートマトン（FSM）、プッシュダウンオートマトン、チューリングマシンなど、異なる種類がある。

有限状態オートマトン（FSM）は、最も基本的なオートマトンの一つであり、有限個の状態を持ち、入力を受け取ることで状態を変更し、出力を生成します。FSMは、以下の3つの要素から構成される。

• 入力アルファベット：オートマトンが受け付ける入力の集合。
• 状態集合：オートマトンが取りうる状態の集合。
• 遷移関数：オートマトンが現在の状態と入力を受け取り、次の状態に移行するための関数。

FSMは、様々なアプリケーションで使用される。たとえば、通信プロトコルやハードウェア回路の設計、テキスト処理、自然言語処理、音声認識などが挙げられる。

プッシュダウンオートマトン（PDA）は、FSMにスタック（LIFOデータ構造）を追加したものであり、

チューリングマシンは、FSMに無限に長いテープと状態遷移に基づく計算機モデルとなる。

これらのオートマトンは、FSMよりも表現能力が高く、より複雑な問題を解決することができる。

有限オートマトン

有限オートマトン (Finite Automaton, FA) は、入力された文字列を受け取ってそれをある規則に従って処理する、計算モデルの一つとなる。有限オートマトンは、入力文字列を受け取って、ある状態から別の状態に移行していく、有限状態遷移図 (Finite State Diagram, FSD) を用いて表現される。

有限オートマトンは、主に以下の2つのタイプに分類される。

• 決定性有限オートマトン (Deterministic Finite Automaton, DFA)
• 非決定性有限オートマトン (Non-deterministic Finite Automaton, NFA)

DFAは、現在の状態と入力文字によって次の状態が決定的に決まる有限オートマトンとなる。つまり、入力された文字列が認識されるかどうかは、常に同じ状態遷移図によって決まる。一方、NFAは現在の状態と入力文字によって複数の状態に移行することができ、認識されるかどうかは、複数の可能性がある。

有限オートマトンは、自然言語処理やコンパイラ、データベースなどの分野で例えば、正規表現を用いた文字列の検索や、プログラミング言語の構文解析などに利用される。また、半導体設計の自動化、通信プロトコル設計、構文解析などの工学面での応用や、生物学や人工知能研究では状態機械（群）を使って神経系をモデル化し、言語学では自然言語の文法をモデル化したりする場合もある。

FSM

有限状態マシン (Finite State Machine, FSM) は、入力シーケンスに対して状態を遷移させる計算機の一種となる。FSMは、入力として与えられたシーケンスを読み込み、ある状態から別の状態へと移動する有限状態遷移図を用いて表現される。FSMは、状態遷移図を使って、入力を受け取ると現在の状態を変更し、適切な出力を生成することができる。

FSMは、主に以下の3つのタイプに分類される。

• メモリを持たないFSM (Moore型) : 現在の状態だけを出力として返す。
• メモリを持ったFSM (Mealy型) : 現在の状態と入力に基づいて出力を生成する。
• 決定的FSM (DFA) : 現在の状態と入力に基づいて、一意に次の状態に移行する。

FSMは、状態遷移図を作成することで設計される。この状態遷移図は、状態と遷移の関係を表したグラフであり、入力に応じて状態が移行するための規則を表す。

FSMは、デジタル回路やプログラミング言語、通信プロトコルなどの設計に広く利用される。これは例えば、ファイルシステムの制御、エレクトロニクスの制御、言語処理、データ圧縮などに利用される。また、FSMは、オートマトン理論や計算理論の基本的なツールであり、機械学習や人工知能などの分野でも利用されるものとなる。

ペトリネット

ペトリネットは、オートマトン理論の一種であり、並行システムのモデリングに使用されるグラフィカルなモデリング言語の一つとなる。ペトリネットは、1962年にカール・アダム・ペトリによって考案され、工業制御やソフトウェアエンジニアリングなどの分野で広く使用されている。

ペトリネットは、二種類の要素から構成されます。1つはプレース（場所）で、もう1つはトランジション（遷移）となる。

プレースは、マーキングと呼ばれるトークンの数を持つ状態を表す。トークンは、例えば、製品、部品、データなどを表すことができる。トランジションは、プレースからトークンを取り、他のプレースにトークンを置くことができる状態変化を表す。トランジションは、入力と出力の両方を持つことができる。

ペトリネットは、以下のような性質を持っている。

• 直交性：トランジション間に制約がないため、複数のトランジションが同時に発火することができる。
• 可逆性：マーキングが前の状態に戻ることができる。
• 構成性：複数のサブシステムを含む複雑なシステムをモデル化することができる。

ペトリネットは、並行システムのモデル化や、分散システム、通信プロトコル、データベーストランザクションなど、多くの分野で使用されている。また、ワークフローモデルやビジネスプロセスモデルとしても使用されており、業務プロセスの効率化に活用されることがある。

自動計画

自動計画 (Automated Planning) は、ある目標状態に到達するためのアクションのシーケンスを自動的に生成する技術となる。自動計画は、コンピューターサイエンス、人工知能、ロボット工学などの分野で研究されている。

自動計画は、一般的に以下の3つの要素から成り立っている。

• 状態 (State) : 問題の現在の状態を表す。状態は、オブジェクトやリソース、その状態などの属性から構成される。
• アクション (Action) : 問題を解決するために取られる行動を表す。アクションには、前提条件と効果がある。前提条件は、アクションを実行するための必要条件であり、効果はアクションによって変化する状態を表す。
• 目標 (Goal) : 問題の解決に必要な最終状態を表す。

自動計画は、上記の要素をもとに、現在の状態から目標状態に到達するためのアクションのシーケンスを生成する。具体的には、自動計画は、現在の状態から目標状態に至るために必要なアクションのシーケンスを計算するものとなる。

自動計画は、スケジューリング、制御、問題解決、ロボットの動作計画、ビジネスプロセスの自動化、医療診断など幅広い分野で利用されている。また人工知能分野で最も基本的な問題の一つでもあり、機械学習、最適化などと組み合わせて応用されることもある。

本ブログではこれらオートマトンと状態遷移/ペトリネットと自動計画に関して、理論、具体的な活用事例と実装など様々な情報を記載している。

数え上げ問題と組み合わせ最適化

数え上げ問題（counting problem）は、組み合わせ論や確率論などの数学の分野で頻繁に取り組まれる問題の一つであり、これは、ある条件を満たす対象の総数を数え上げる問題として、しばしば組み合わせの数や順列の数を求めることに関連しているタスクとなる。

これらの問題は、数学的な原則や公式を使用して解決され、順列や組み合わせ、二項係数などの概念がよく使われ、問題によっては問題の性質に合わせてそれぞれの公式を選択する必要がある。

オートマトン

• オートマトン理論の概要と実装、参考図書

オートマトン理論は、計算理論の分野の1つであり、コンピュータ科学において重要な理論の1つとなる。オートマトン理論は、有限状態機械（FSM）やプッシュダウンオートマトン、チューリングマシンなどの抽象的な計算機モデルを研究することによって、形式言語、形式文法、計算能力、計算可能性、自然言語処理などの問題を解決するために応用される。ここでは、このオートマトン理論の概要とアルゴリズムおよび様々な適用事例と実装について述べている。

• エイヒンホルツアルゴリズム (Aho-Hopcroft-Ullman Algorithm)の概要と関連アルゴリズム及び実装例について

エイヒンホルツアルゴリズム（Aho-Hopcroft-Ullman Algorithm）は、文字列検索やパターンマッチングなどの文字列処理問題において、効率的なアルゴリズムとして知られているものとなる。このアルゴリズムは、文字列処理における基本的なデータ構造であるトライ（Trie）と有限オートマトン（Finite Automaton）を組み合わせて、文字列のパターン検索を効率的に行い、主に文字列マッチングに用いられるが、コンパイラやテキスト検索エンジンなど幅広い分野で応用されているものとなる。

有限状態マシン(FSM:Finite State Machine)技術

• 有限状態マシン(FSM:Finite State Machine)の概要と実装、参考図書

有限状態マシン (Finite State Machine, FSM) は、入力シーケンスに対して状態を遷移させる計算機の一種となる。FSMは、入力として与えられたシーケンスを読み込み、ある状態から別の状態へと移動する有限状態遷移図を用いて表現される。FSMは、状態遷移図を使って、入力を受け取ると現在の状態を変更し、適切な出力を生成することができる。

• Behavior Tree(行動木)とUnityでの実装 

Behavior Tree(動作ツリー)は、ゲームAIにも登場する複雑なAI行動を構築するためのフレームワークとなる。これはは元々ロボット工学を目的として開発されたものが、FPS等のゲームの中のノンプレイヤーキャラクター(NPC)のAIを設計する為の階層ステートマシーンの改良として用いられるようになったもので、利点として、設計と実装が容易で再利用性と移植性が高い為、大きく複雑なロジックに対応可能としたものにある。

ペトリネット技術

• ペトリネット技術の概要と人工知能技術との組み合わせ、各種実装について

ペトリネットとは、ペトリが1962年に提案した離散事象システムの記述モデルで、事象駆動型のシステムにおいて，非同期・並行な事象と，それを導く状態との関係を表現するものとなる。ペトリネットは，状態と遷移のグラフィカルモデルであり、四つの構造要素，すなわちプレースP，トランジションT，入力関係I，出力関係Oの組み（PTIO）と，マーキングMから構成される非常に柔軟で一般的なモデリング言語となる。今回はこのペトリネットの概要と適用事例、具体的な実装と参考図書について述べる。

自動計画(AutoPlanning)技術

• 自動計画問題の概要と参考図書

自動計画問題とは、ある目標を達成するために必要な一連の行動を計画する問題となる。具体的には、ある状態から出発し、目標状態に至るための行動の順序を決定するアルゴリズムで、自動計画問題は、人工知能やロボット工学などの分野で広く用いられるものとなる。

• 動的計画法の概要と適用事例とpythonによる実装例

動的計画法(Dynamic Programming)は、最適化問題を解くための数学的手法の一つであり、特に重複する部分問題を持つような問題に適用される手法を指す。動的計画法は、一度計算した結果を保存して再利用することで、指数的な計算量を劇的に減らすことができるため、効率的な解法を提供する。ここでは、この動的計画法に対して、様々なアルゴリズムとpythonによる具体的な実装方法について述べている。

• 混合整数最適化の概要とアルゴリズム及びpythonによる実装

混合整数最適化は、数理最適化の一種であり、連続変数と整数変数を同時に扱う問題のことを指す。この分野は、さまざまな産業やビジネス領域で現実的な問題を解決する際によく用いられ、混合整数最適化の目標は、目的関数を最大化または最小化する際に、制約条件の下で最適な変数の値を見つけることとなる。ここでは、この混合整数最適化に関して、様々なアルゴリズムと実装について述べている。

• 体系的非線形計画(外部リンク)

本論文は、ドメインに依存しないSTRIPSプランニングのための、シンプルで健全、かつ完全で体系的なアルゴリズムを提示する。シンプルさは、基本的な手順から始めて、一般的で独立に検証可能な持ち上げ変換を適用することで達成される。これまでのプランナーは、持ち上げられた手順として直接設計されてきた。私たちの地上手順は、TateのNONLIN手順の地上版である。Tateの手続きでは、未完成のプランのステップの前提条件が、全ての線形化で成立することが保証されているかどうかを判断する必要はない。これにより、Tateの手続きはChapmanの様相真理基準の使用を避けることができる。系統性とは、同じ計画や部分計画が2回以上検討されることがないという性質である。

• 気づきと人工知能技術

「気づく」とは、何かを注意深く観察したり、認識したりすることを指し、また、人が状況や物事に対して気付くということは、その人がある情報や現象を認識し、それに関する気持ちや理解を持つことを意味する。気づくことは、外界の変化や出来事に注意を払うことによって、新たな情報を得たり、理解を深めたりする重要な過程となる。今回は、この気づきとそれらに対する人工知能技術の適用について述べてみたいと思う。

数え上げ問題と組み合わせ最適化

• 数え上げ問題の概要とアルゴリズム及び実装例について

数え上げ問題（counting problem）は、組み合わせ論や確率論などの数学の分野で頻繁に取り組まれる問題の一つであり、これは、ある条件を満たす対象の総数を数え上げる問題として、しばしば組み合わせの数や順列の数を求めることに関連しているタスクとなる。これらの問題は、数学的な原則や公式を使用して解決され、順列や組み合わせ、二項係数などの概念がよく使われ、問題によっては問題の性質に合わせてそれぞれの公式を選択する必要がある。

• 組合せ最適化の概要と実装の為のライブラリと参考図書

組合せ最適化理論は、輸送計画、スケジューリング、配置、組合せ問題、そして最適化問題など実世界の多くの問題に応用されている理論となる。この問題は、ある個数の要素から構成される集合の中から、制約条件を満たす部分集合を見つけ、その中で最も優れた解を求めることを目的としたもので、ある制約条件の下で最適な解を求める離散的な最適化問題を扱う数学的な手法の一つとなる。

• 整数線形プログラミング（ILP）による最適化の概要とアルゴリズム及び実装例について

整数線形プログラミング（Integer Linear Programming, ILP）は、数学的な最適化問題を解くための手法の一つであり、特に制約条件の下で整数解を求める場合に利用される手法となる。ILPは線形プログラミング（Linear Programming, LP）の一種で、目的関数および制約条件が線形であり、かつ変数が整数値を取るという条件が付加されている。

デジタルゲームAI

• デジタルゲームAIの歴史(1) 反射型AI、FSM、GA、BT

「人と機械」のインタラクションの知能化はゲームの世界で昔から行われている。今回はそれらを考えるためのベースとしてまずその歴史を「デジタルゲームの教科書　知っておくべきゲーム業界最新トレンド」からピックアップしてまとめてみた。

• デジタルゲームAIの歴史(2) 自律型エージェント、C4、階層型FSM

今回は最後の世代(00年度以降)に現れた自律型エージェントについて述べたいと思う。

• デジタルゲームAIの基本技術(空間認識) 知識表現

デジタルゲームキャラクタAIのクオリティは「そのAIが時間と空間をどれだけ支配しながら活動できるか」によって決まる。これはどれくらい周囲の環境を認識し、どれくらいの時間幅と時間スケールの中で行動を組み立てることができるかということでもある。このそれぞれについて対応する技術を述べる。

• デジタルゲームAIの基本技術(時間認織) 過去記憶、未来(プランニング)

次の重要な認識である時間について、デジタルゲームにおいてAIを時間から眺めることは非常に重要なポイントとなる。このAIに時間軸の認識を与えるには、まずAIに過去(記憶)を与える必要がある。AIに記憶を与えるには、記憶領域(メモリ)の確保と、その記憶の形式を決定することが必要で、記憶の形式がそのAIの知的基盤を決定する。