【研究領域課題番号】20K11932 (KAKENデータベースで見る）

【研究キーワード】

探索 / Heuristic Search / 人工知能

【研究成果の概要】

Although the number of processing cores on CPUs and GPUs have continued to increase in recent years, recent work has shown that this increased parallelism does not necessarily result in improved performance of search algorithms. This project is an experimental and theoretical investigation of the tradeoffs between search efficiency and increased parallelism in search algorithms. We have analyzed greedy best first search algorithms for path-finding on graphs. We developed a theoretical framework to compare parallel best-first search with sequential best-first search, including both suboptimal (GBFS, Weighted A*) and optimal (A*) best-first search methods. We analyzed the extent to which the search behavior of existing parallel best-first search methods differ from sequential best-first search. We showed that existing methods are vulnerable to pathological behavior, and that they can expand nodes which would not be expanded by sequential search under any tie-breaking policy, resulting in arbitrarily worse performance compared to sequential search. We also proposed PUHF, a parallel best-first search which is guaranteed to expand a node only if there is some tie-breaking strategy for sequential search which expands the node.

【研究種目】基盤研究(C)

【研究期間】2020-04-01 - 2023-03-31

【配分額】4,290千円 (直接経費: 3,300千円、間接経費: 990千円)

【研究領域課題番号】19H00597 (KAKENデータベースで見る）

【研究キーワード】

創造性 / 洞察問題解決 / 計算論的アプローチ / fMRI / イノベーション / 拡散思考 / 収束思考 / Q学習 / 探索 / 活用 / 脳神経基盤 / グループダイナミクス / 強化学習 / 生体データ / 認知特性 / 集団力学 / AI

【研究成果の概要】

2021年度は、主に２つの実験を実施した。第一に、神戸大学の学部学生を対象とした大規模実験を実施した。具体的には、2020年度と同様、Psytoolkitでプログラムした心理実験（２腕バンディット）を、個人、ダイアド（２名のグループ）、トライアド（３名のグループ）に対して実施した。それに加え、今年度はAUT（alternative use test）テストを実施した。これは拡散思考、創造性を測定するテストであり、このテストによって、これらの個人、集団の創造性のパフォーマンスについても測定した。その結果、昨年度の研究では明らかにすることができなかったグループレベルでの学習特性が創造性パフォーマンスにどのような影響を与えているのかについて分析することができた。データ分析の結果、個人、グループの創造性のパフォーマンスは、リスク愛好度や探索志向性に大きく影響されることが明らかになった。また、創造性のパフォーマンスはダイアドが最も低く、個人、トライアドが高いパフォーマンスを示すことがわかった。これは昨年度に実施した認知課題に対しるパフォーマンスの個人、ダイアド、トライアド、テトラッド間での比較分析結果と整合的なものであった。
第二に、生理学研究所の協力を得て、2019年度、2020年度に個人を対象に実施したfMRI検査に対し、そのデータ解析を進めた。これらの年度では２つのfMRI実験を実施し、そのデータ解析の概要は得られている。それらの結果を１つの論文にまとめるため、検討を続けている。それに加え、今年度は２名のコミュニケーション活動を取り入れたうえで、同様のfMRI実験を実施した。ただし、実験実施時においてコロナ感染状況が悪化したため、当初予定していた被験者数を集めることができず、次年度に追試を実施していく予定である。

【研究種目】基盤研究(A)

【研究期間】2019-04-01 - 2024-03-31

【配分額】36,920千円 (直接経費: 28,400千円、間接経費: 8,520千円)

【研究分野】知能情報学

【研究領域課題番号】17K00296 (KAKENデータベースで見る）

【研究キーワード】

探索 / 並列アルゴリズム / Heuristic search / artificial intelligence / 探索アルゴリズム / 人工知能 / 並列探索アルゴリズム

【研究成果の概要】

最適解（最小コスト解）を保証するヘテロジニアス並列探索アルゴリズムBlock-Parallel IDA*を開発した。Block-Parallel IDA*はGPUのBlock毎に探索木の部分木を割り当てることにより、従来のスレッド並列GPU探索アルゴリズムより優れた性能を得られることを実証した。一方、最適解を求めるのは難しい問題において充足解を求めるヘテロジニアス並列探索アルゴリズムBatch Monte Carlo Random Walk(BMRW)を開発して、従来のRandom　Walkより優れた結果を得られることを実証した。

【研究の社会的意義】

近年、従来型の演算コアを数十個搭載する主演算装置（CPU）に加えて、数千個の演算コアを搭載するGPUを両方搭載しているヘテロジニアスな計算機が普及している。人工知能においてエージェントやロボットの自動行動計画問題及び、経営工学における生産スケジューリング問題や施設配置問題等、多くの難解な探索・最適化問題に対して並列処理能力を十分に発揮できるグラフ探索アルゴリズムを設計することが必要である。本研究においてCPUとGPUを同時に有効に使う探索アルゴリズムを提案・解析した。

【研究種目】基盤研究(C)

【研究期間】2017-04-01 - 2021-03-31

【配分額】4,680千円 (直接経費: 3,600千円、間接経費: 1,080千円)

【研究分野】エンタテインメント・ゲーム情報学

【研究領域課題番号】25330432 (KAKENデータベースで見る）

【研究キーワード】

ゲームプログラミング / 探索 / 機械学習 / ゲーム情報学 / 人工知能

【研究成果の概要】

本研究課題の究極の目標は,直感や大局観などの言葉で表される人間の判断の根拠の概要を,計算機の分析を通じて言語や図で明示的に表現する手法を実現することである.対象とする分野は,計画の通り,人工知能の判断力が熟達した人間の判断力に追いついたことを重視し,将棋や囲碁を扱った. それらを題材に，棋譜と解説すべき局面の重要性を評価することを目標に,どのような展開が有力かを推定する手法を開発・改善し，性能を評価した．

【研究種目】基盤研究(C)

【研究期間】2013-04-01 - 2016-03-31

【配分額】2,600千円 (直接経費: 2,000千円、間接経費: 600千円)

【研究分野】知能情報学

【研究領域課題番号】20700131 (KAKENデータベースで見る）

【研究キーワード】

人工知能 / 進化計算 / 探索

【研究成果の概要】

ロボットや自律エージェントにおけるタスク割り当てや自動行動計画等の最適化問題および制約充足問題に対する有用なアルゴリズムを開発するのは困難である。本研究は自動プログラミング法の遺伝的プログラミングを用いて、このような問題に対するヒューリスティック(限られた時間内に準最適解を求める場合有用な手法)を自動的に検出・作成するシステムの構築に取り組んだ。大規模クラスタを用いた並列遺伝的プログラミングシステムを実装して、制約充足問題(SAT)に対する新たなヒューリスティックを自動作成した。更に、遺伝的プログラミングを用いて展示場案内ロボットの行動決定ヒューリスティック(コントローラー)を作成した。尚、複数ナップサック問題に対する新たな厳密アルゴリズム、及び、ヒューリスティック法を提案した。

【研究種目】若手研究(B)

【研究期間】2008 - 2010

【配分額】3,900千円 (直接経費: 3,000千円、間接経費: 900千円)