バックトラッキングを活用したマルチエージェントシステムによる複数制約充足プランニング

大規模言語モデル(LLM)の発展により，従来の技術では困難であった自然言語処理タスクにおいて，人間に匹敵する精度が達成されている[1,2]．近年，LLMを活用し，旅行計画[3]や経路探索[4]，ロボットの動作制御[5]など，実世界の広範な応用タスクに対し，解法を自律的に導きそれを実行するLLMエージェント1）の実現が期待されている．特に注目されているのは，プランニングタスクへの応用である．プランニングタスクとは，与えられた目標を達成するための一連の計画を策定するものである[7]．先行研究では，CoT（Chain-of-Thought）[8]やReAct（ReasoningandActing）[9]といった手法を組み込み，LLMエージェントのプランニング能力を強化する試みが行われている．しかし，単一のLLMエージェントが複数の制約を同時に満たすプランニングを行うことは依然として難しいと1）本稿ではZhiheng[6]らに倣い，エージェントを「環境内で自律的に意思決定し，行動する人工的な存在」と定義する．されている．例えば，複数制約充足プランニングタスクの一つである実世界旅行計画ベンチマーク『TravelPlanner』では，全ての制約を満たすプラン生成の成功率がGPT-4で4.4%，OpenAIo1で15.6%と，人間レベルには大きく劣る結果が報告されている[3,10]．主な原因の一つには，単一のLLMエージェントが相互に依存する制約を同時に最適化することの難しさが挙げられる．この課題に対し，複数のエージェントが相互に連携しタスクを遂行する協調的なマルチエージェントシステム[11]が有効だと考えられる．分割された各サブタスクを異なるエージェントが担当することで負荷を分散し，互いに協働することで相互に依存する複数の制約を満たすプランニングが期待される．本研究では，『TravelPlanner』[3]を対象に，マルチエージェントシステムが複数制約充足プランニングタスクにおいて有効であるかを検証した．実際に構築したシステムの概要を図1に示す.『TravelPlanner』では，予算や観光地などに関する複数の制約を同時に満たす旅程の作成が求められる．そこで，エージェントごとに独立した制約を割り当て部分的にプランニングを行い，制約を満たす候補がなくなった段階でバックトラッキングすることで，最終的に全ての制約を厳密に満たすプランの生成を試みた．実験の結果，シングルエージェントによるプランニング戦略と比較して，制約の充足率が向上しており，有効性が確認された．一方で，エージェント間で受け渡す情報の一部が欠落するなど，マルチエージェントシステムに起因する課題も確認された．