はじめに
こんにちは、東北大学修士2年の守屋彰二と申します。この度、SB Intuitions株式会社 R&D本部 Foundation dev部 Dialogチームにて、インターンシップに参加させていただきました。
本記事では、インターン中に取り組んだ「マルチエージェントによる複数制約充足プランニング」について、その概要と成果を紹介いたします。
大規模言語モデル（LLM）の登場により、さまざまな分野でその可能性が注目されています。その一例として、プランニングタスクにおける活用があります。プランニングタスクとは、与えられた目標を達成するための一連の計画を策定するタスク [Huang+,24] であり、自律型エージェントに求められる重要な機能であると考えられています。また、旅行計画や経路探索など、実世界での幅広い応用が期待されています。
LLMを推論器として活用することにより、複雑なタスクに対し、自然言語で解法を記述しながら柔軟かつ高度なプランニングを実現する手法が模索されています。例えば、CoT（Chain of Thought）[Wei+,22] やReAct（Reasoning and Acting）[Yao+,22] などの手法を用いて、LLMエージェントのプランニング能力を強化する試みが行われています。
しかし、複雑な実世界環境では、LLMエージェントが複数の制約を同時に満たすプランニングを行うのは依然として困難であることが指摘されています。例えば、実世界における旅行計画ベンチマーク『TravelPlanner』では、全ての制約を満たすプラン生成の成功率はGPT-4で4.4%、OpenAI o1でも15.6%程度にとどまっています [Xie+,24]。
この低い成功率の一因には、1つのLLMエージェントが相互に依存する複数の制約を同時に最適化することの難しさがあります。上記の『TravelPlanner』の例では、ユーザの要望を全て満たすような計画を立てると予算が超過してしまい、予算を考慮しながら再度計画を立て直すと今度はユーザの要望を適切に考慮できなくなってしまう、といったように、全体の制約を一度に処理しようとすると、特定の制約を満たすために他の制約を犠牲にしやすい傾向があることが知られています。また、このような制約の数が増えれば増えるほど、プランニングはより難しくなることも明らかとなっています。
このような課題を克服するために、1つのLLMエージェントに全ての制約を処理させるのではなく、複数のエージェントが協調しながら分散的に制約を満たすマルチエージェントシステムを活用することで、異なる制約を担当するエージェント間で情報を共有しながら、効率的に制約充足を達成することが可能になるのではないかと考えました。
本研究では『TravelPlanner』を対象とし、マルチエージェントによる協調アプローチが複数制約充足プランニングタスクにおいて有効であるかを検証しました。具体的には、タスクをサブタスクに細分化し、それぞれを異なるエージェントが担当することで負荷を分散しました。また、各エージェント間で部分解を共有することで、全体として制約を満たすプランニングを目指しました。
構築したシステムの概要図を下図1に示します。このシステムは、バックトラッキングを活用してエージェント間の協働を実現し、アルゴリズムの厳密性とLLMの柔軟性を組み合わせた設計となっています。
実験の結果、シングルエージェントによるベースラインシステムと比較して複数制約の充足率が向上し、マルチエージェントによる協働アプローチがこのようなプランニングタスクにおいて有効であることを確認しました。
実世界旅行計画ベンチマーク『TravelPlanner』
旅行計画の自動生成は長年研究されており、ルート最適化 [Chia+,16; Zhou+,17]や、ユーザ嗜好への適応 [Vansteenwegen+,11]など、多くの側面からのアプローチが進められています。しかし、実際の旅行計画では、動的な情報収集や多様な制約の同時考慮が求められ、依然として解決すべき課題が残っています。
このような背景のもと、実世界データを基に、複数の要素を考慮した一貫性のある旅行計画を生成するエージェントの能力を評価するベンチマーク『TravelPlanner』[Xie+,24]が提案されました。『TravelPlanner』は、与えられたユーザのクエリと参照情報をもとに、旅行計画を立案するタスクであり、エージェントは、様々な制約を満たしながら、日程ごとに訪問都市、移動手段、観光地、食事（朝・昼・夕）、および宿泊施設を決定することが求められます。本研究では、このベンチマークを用いて、旅行計画における複数制約充足を通じてエージェントのプランニング能力を評価し
ます。
このベンチマークには2つのモードがあります：
- Sole-Planningモード：事前に提供された参照情報を用いてプランニングを行う
- Two-Stageモード：Toolを介して必要な情報を収集したのちプランニングを行う
今回は、エージェントの純粋なプランニング能力を評価するため、Sole-Planningモードを対象に実験を行いました。
制約の概要
計画を立案する際には、以下の2種類の制約を満たす必要があります。
Commonsense Constraint：クエリに含まれない常識的な制約
- Within Sandbox：参照情報内から選択しているか（Hallucinationを回避）
- Complete Information：計画に必要な情報が欠けていないか
- Within Current City：食事や観光地などが滞在都市内から選ばれているか
- Reasonable City Route：都市間の移動ルートが合理的であるか
- Diverse Restaurants：同一プラン内にレストランが重複していないか
- Diverse Attractions：同一プラン内に観光地が重複していないか
- Non-conf. Transportation：選択した移動手段が矛盾していないか
- Minimum Stay Night：宿泊施設ごとの最低滞在日数を満たしているか
Hard Constraint：ユーザのクエリ内で指定される制約
- Budget：予算を超過していないか
- Room Rule：選択した宿泊施設が指定された部屋のルール（“No pets”や“No visitors”など）を満たしているか
- Room Type：選択した宿泊施設が指定された部屋のタイプ（“Private Room”や“Shared Room”など）を満たしているか
- Cuisine：選択したレストランが指定された料理（“Chinese”, “French”など）を提供しているか
- Transportation：選択した移動手段が指定された移動手段の制限（“No Flights”, “No Self-driving”など）を満たしているか
また、評価方法として、それぞれの種類の制約を全て満たすインスタンスの割合（Commonsense Constraint Pass Rate、Hard Constraint Pass Rate）に加え、全ての制約を満たすインスタンスの割合（Final Pass Rate）が評価されます。
提案手法：
バックトラッキングを組み合わせたマルチエージェントシステム
バックトラッキングとは
バックトラッキングは、部分解を順に割り当てる過程で制約を満たさない場合に、前のステップに戻って別の値を再帰的に割り当てるアルゴリズムです。この手法を用いることで、全ての制約を満たす有効な解を効率的に探索することが可能です。
代表的な適用例として、Nクイーン問題や迷路探索が挙げられます。これらの問題では、厳密な制約を満たしながら解を見つけるためにバックトラッキングが広く活用されています。
マルチエージェントシステムへの適用
本研究では、バックトラッキングをマルチエージェントシステムに組み合わせることで、相互依存する制約を効率的に満たしながらプランニングを行うことを目指しました。今回はインターン期間の都合上、タスクの制約依存性を基にエージェントのアーキテクチャを人手で設計しています。
提案するシステムのアーキテクチャの概要を説明します。
まず、前処理として、ユーザが提供したクエリと参照情報から必要な制約や関連情報を抽出し、それらを後続のエージェントに適切に渡します。この前処理により、後続のエージェントが効率的にプランニングを行うための土台を整えます。
次に、複数のプランナーエージェントがそれぞれ割り当てられたサブタスクを処理します。各エージェントは、受け渡された制約や情報をもとに部分的なプランニングを実行し、その結果を次のエージェントに引き継ぎます。この順次処理により、複雑なプランニングタスクが分散されるだけでなく、エージェント間での情報共有によってタスク全体の整合性が保たれます。
一方、プランニングの過程で制約を満たすことが難しい局面に直面することもあります。この場合、システムはバックトラッキングを用いて、問題が発生した段階から一つ前のエージェントに戻りプランを修正します。戻る際には、テキストベースのフィードバックとして、どの制約が満たされなかったのか、どのような調整が必要かといった具体的な情報が提供されます。（図6の例では、移動手段エージェントが1つ前の予算エージェントにより分配された予算では$100不足していることをフィードバックとして与えています。）このフィードバックを受けとったエージェントは、次の試行で別の候補を選択することで解決を図ります。この段階で制約を満たすことが困難であると判断した場合は、さらにバックトラッキングを行います。この再帰的なアルゴリズムにより、エージェントは全体の制約を厳密に満たしながらプランニングを行うことが可能になります。
このように、複数制約の充足が重要なプランニングタスクにおいて、タスクをエージェントごとに分割し負荷を分散させることで、計算効率の向上を図るとともに、フィードバックを伴うバックトラッキングと組み合わせることで、相互に依存する制約を柔軟かつ正確に満たすプランニングを実現することを目指しました。
実験
本研究では、『TravelPlanner』のvalidationデータのうち、”3 days”の計60件を対象として実験を行いました。制約の数ごとにEasy、Medium、Hardの3つの難易度に分類され、それぞれ20件ずつあります。
提案手法の各エージェントでは、後述のベースラインに合わせGPT-4-1109-previewを使用しました。各エージェントに与えられたプロンプトは、Appendixに示しています。
ベースライン
実験のベースラインとして、『TravelPlanner』ベンチマークにて検証されているシングルエージェントによる既存のプランニング戦略を使用しました。具体的には、次の3つの手法を評価対象としました：
- Direct
- CoT（Chain of Thought）
- ReAct（Reasoning and Acting）
なお、実験にはGPT-4-1109-previewを使用しており、プロンプトや実装についてはベンチマークで公開されているものをそのまま使用しました。
実験結果
提案手法は、ベースラインを上回るFinal Pass Rateを示しました。特に、Commonsense Constraint とHard Constraintの両方において、Pass Rateが顕著に向上しました。
以下に、各制約別の充足率を示します。
提案手法は、特にMediumやHard設定において、Final Pass Rateが上昇する傾向が見られました。ここから、提案手法が制約数の多いタスクにおいて有効であることが確認できました。
また、タスクの細分化により、各項目ごとに制約の充足率が向上しました。例えば、宿泊施設に依存するRoom Rule やMinimum Nights Stayなどの充足率が向上していることから、サブタスクに分割した処理が効果的であることが示されました。さらに、バックトラッキングに基づくエージェント間の協働が、Budgetなどの相互に依存する横断的な制約において有効である可能性が示唆されました。
一方で、提案手法におけるBudgetの充足率は依然として50.0%に留まっており、LLMの指示理解や追従能力が十分に発揮されていないことが示唆されます。また、Within Sandboxの充足率が低下しており、Hallucinationの増加も見られました。
CoTやReActとの比較はAppendixに載せておりますが、これらの手法についても同様の傾向を確認いたしました。
考察
定性分析
実際の各エージェントの生成例を表3に示しています。
この例からわかるように、各プランナーエージェントのフィードバックに基づいて予算の再分配が適切に行われており、バックトラッキングが効果的に働いている事例が見受けられました。
一方で、制約を満たさない場合に、参照情報には存在しない「都合の良い」データを生成してしまう（Hallucinationが生じる）事例が確認されました。この現象は、ベースラインでも指摘されていますが、提案手法では推論回数が増加するため、その影響がより顕著に現れたと考えられます。他にも、エージェント間で受け渡す情報の一部が欠落し、後続のエージェントが正確な推論を行えなくなる問題も見られました。
これらの対策として、現在は一つのエージェントが担当している項目を複数のエージェントが重複して担当することで、相互に整合性を確認する手法や、各エージェントの結果だけでなくその推論過程も後続のエージェントに与える手法が考えられます。
提案手法の限界
本研究では、タスクを解く順序をあらかじめ与えてしまっており、人手による設計が介入してしまっています。エージェントが完全に自律的にプランニングタスクを解くためには、マルチエージェント構造の自動設計が必要であると考えられます。
本研究では、タスクの概要とクエリからエージェント構造の自動設計も試みました。しかし、タスクの大まかな細分化やサブタスク間の依存関係の生成は可能でしたが、各サブタスクの具体的な入出力やエージェント間で受け渡す情報の詳細を制御することは難しく、完全な自動化までは依然として課題があることがわかりました。
まとめ
本研究では、『TravelPlanner』のような複数制約充足プランニングタスクに対し、バックトラッキングを組み込んだマルチエージェントシステムを構築し、有効性を検証しました。実験結果より、シングルエージェントのベースラインと比較し、制約の充足率の向上を確認できました。
謝辞
最後になりますが、メンターとしてサポートいただきました大萩さん、Dialogチームの皆様、および日頃からご協力いただきました社員の皆様にこの場をお借りして御礼申し上げます。
参考文献
Xu Huang, Weiwen Liu, Xiaolong Chen, Xingmei Wang, Hao Wang, Defu Lian, Yasheng Wang, Ruiming Tang, Enhong Chen. Understanding the planning of LLM agents: A survey.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, Denny Zhou. Chain-of-Thought Prompting Elicits Reasoning in Large Language Models.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, Yuan Cao. ReAct: Synergizing Reasoning and Acting in Language Models.
Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, Yu Su. TravelPlanner: A Benchmark for Real-World Planning with Language Agents.
Jian Xie, Kexun Zhang, Jiangjie Chen, Siyu Yuan, Kai Zhang, Yikai Zhang, Lei Li, Yanghua Xiao. Revealing the Barriers of Language Agents in Planning.
Wai Chong Chia; Lee Seng Yeong; Fennie Jia Xian Lee; Sue Inn Ch'ng. Trip planning route optimization with operating hour and duration of stay constraints.
Xiaolu Zhou, Mingshu Wang, Dongying Li. From stay to play – A travel planning tool based on crowdsourcing user-generated contents.
Pieter Vansteenwegen, Wouter Souffriau, Greet Vanden Berghe, Dirk Van Oudheusden. The City Trip Planner: An expert system for tourists.
Jeff Erickson. Algorithm.
Appendix
各エージェントに与えられたプロンプト例
ベースラインシステムにおいては、『TravelPlanner』で提供されているプロンプトを使用しました。
提案手法で使用した各エージェントのプロンプトを以下に示します。
これらのプロンプトは、基本的にベースラインシステムのプロンプトの一部を切り出したものであり、必要以上の情報を与えないよう留意しました。
- 前処理エージェント用プロンプト
# Task Description
You are a Travel Planner Manager Agent. You have several subordinate planner agents who manage city routes, budgets, transportation, meals, attractions, and places to stay. For a given query, extract the information to be passed to all subordinate agents and the information to be passed to each subordinate agent. You must adhere to the format given in the example. -
各プランナーエージェント用プロンプト。ここでは移動手段のプランナーエージェントを紹介します
# Task Description
You are a transportation planner agent. Select the transportation from the information that meets the requirements. You must adhere to the format given in the example. First output the inference process, then output the results in JSON format. Output the result under the string "--- JSON OUTPUT ---". - 後処理エージェント用プロンプト
# Task Description
You are the plan aggregator. The following information will be provided: - Current plan - Plans for transportation, meals, attractions, and accommodations Please update the current plan by reflecting each of these elements into it. Fill in "-" if there is an empty value. You must adhere to the format given in the example. Specifically, output "Current City", "Transportation", "Breakfast", "Attraction", "Lunch", "Dinner", and "Accommodation" for each day. For meals, attractions, and accommodations, please output the name of the city as well as the name of the restaurant as the example shows. Output in a plain text as below (not a JSON format).
各制約別の充足率
