階層的挟み撃ち探索を用いたAND/OR木探索の並列処理による高速化

点击翻译按钮获取中文摘要

探索問題は人工知能の基礎として盛んに研究されており、人間の思考・推論の表現など様々に用いられている。しかし、探索範囲が広いと解の発見に長時間必要となるため求解の高速化が望まれている。そこで、本研究では、AND/OR木として表される問題の探索を例として、並列処理・並行処理を用いて処理の高速化を図る。一般にヒューリスティック探索では、評価値の高い経路のみ探索することで早期に解を発見しようとするが、評価値の低い経路上に解がある場合には求解に非常に長い時間を要するという問題がある。本年は、AND/OR木の求解を情報家電組込用マルチコアプロセッサ上で高速に行うために、プロセッサコア数より多くの経路を並列・並行に深さ優先探索することで、メモリ量を小さく抑えつつプロセッサコア数にスケーラブルに速度向上する手法を提案し、評価した。本手法では、評価値の高い節点から探索する探索経路と評価値の低い節点を含む探索経路を並列探索し、さらに、少ないプロセッサコア数でより高速に求解するために、プロセッサコア数よりも多くの経路を並列・並行に探索する。また、各プロセッサコアの探索に深さ優先探索を用いることで、少ないメモリ環境での探索が可能となる。また、シングルプロセッサにおいても評価値の高い節点から探索する探索経路と評価値の低い節点を含む探索経路を複数同時に探索するために、並行処理を用いて探索する手法を提案し、評価した。本手法を用いることで、シングルプロセッサにおいても従来の評価値の高い節点からのみの探索よりも高速化が可能となる。シングルプロセッサ上で複数の経路を並行に探索するために、擬似的なスレッドを用いることでスレッド生成・切り替えにかかるオーバヘッドを削減でき、また、適切な箇所でスレッドを切り替えることができるため、並列処理には必須であるスレッド間の排他制御も削除できる。