Why Solving Multi-agent Path Finding with Large Language Model has not Succeeded Yet Article Swipe

PDF

Weizhe Chen , Sven Koenig , Bistra Dilkina ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2401.03630

With the explosive influence caused by the success of large language models (LLM) like ChatGPT and GPT-4, there has been an extensive amount of recent work showing that foundation models can be used to solve a large variety of tasks. However, there is very limited work that shares insights on multi-agent planning. Multi-agent planning is different from other domains by combining the difficulty of multi-agent coordination and planning, and making it hard to leverage external tools to facilitate the reasoning needed. In this paper, we focus on the problem of multi-agent path finding (MAPF), which is also known as multi-robot route planning, and study the performance of solving MAPF with LLMs. We first show the motivating success on an empty room map without obstacles, then the failure to plan on the harder room map and maze map of the standard MAPF benchmark. We present our position on why directly solving MAPF with LLMs has not been successful yet, and we use various experiments to support our hypothesis. Based on our results, we discussed how researchers with different backgrounds could help with this problem from different perspectives.

Related Topics

Benchmark (Surveying)

Computer Science

Artificial Intelligence

Mechanical Engineering

Concepts

Leverage (statistics) Benchmark (surveying) Computer science Plan (archaeology) Motion planning Path (computing) Variety (cybernetics) Artificial intelligence Work (physics) Robot Operations research Management science Engineering Programming language Mechanical engineering Archaeology History Geodesy Geography

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2401.03630
PDF: https://arxiv.org/pdf/2401.03630
OA Status: green
Cited By: 1
Related Works: 10
OpenAlex ID: https://openalex.org/W4390723614

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4390723614

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2401.03630

Digital Object Identifier
Title: Why Solving Multi-agent Path Finding with Large Language Model has not Succeeded Yet

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-01-08

Full publication date if available
Authors: Weizhe Chen, Sven Koenig, Bistra Dilkina

List of authors in order
Landing page: https://arxiv.org/abs/2401.03630

Publisher landing page
PDF URL: https://arxiv.org/pdf/2401.03630

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2401.03630

Direct OA link when available
Concepts: Leverage (statistics), Benchmark (surveying), Computer science, Plan (archaeology), Motion planning, Path (computing), Variety (cybernetics), Artificial intelligence, Work (physics), Robot, Operations research, Management science, Engineering, Programming language, Mechanical engineering, Archaeology, History, Geodesy, Geography

Top concepts (fields/topics) attached by OpenAlex
Cited by: 1

Total citation count in OpenAlex
Citations by year (recent): 2024: 1

Per-year citation counts (last 5 years)
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4390723614
doi	https://doi.org/10.48550/arxiv.2401.03630
ids.doi	https://doi.org/10.48550/arxiv.2401.03630
ids.openalex	https://openalex.org/W4390723614
fwci
type	preprint
title	Why Solving Multi-agent Path Finding with Large Language Model has not Succeeded Yet
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11714
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9995999932289124
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1707
topics[0].subfield.display_name	Computer Vision and Pattern Recognition
topics[0].display_name	Multimodal Machine Learning Applications
topics[1].id	https://openalex.org/T10181
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9912999868392944
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1702
topics[1].subfield.display_name	Artificial Intelligence
topics[1].display_name	Natural Language Processing Techniques
topics[2].id	https://openalex.org/T10586
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9787999987602234
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1707
topics[2].subfield.display_name	Computer Vision and Pattern Recognition
topics[2].display_name	Robotic Path Planning Algorithms
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C153083717
concepts[0].level	2
concepts[0].score	0.7561378479003906
concepts[0].wikidata	https://www.wikidata.org/wiki/Q6535263
concepts[0].display_name	Leverage (statistics)
concepts[1].id	https://openalex.org/C185798385
concepts[1].level	2
concepts[1].score	0.6451554894447327
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1161707
concepts[1].display_name	Benchmark (surveying)
concepts[2].id	https://openalex.org/C41008148
concepts[2].level	0
concepts[2].score	0.6129910945892334
concepts[2].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[2].display_name	Computer science
concepts[3].id	https://openalex.org/C2776505523
concepts[3].level	2
concepts[3].score	0.5490208864212036
concepts[3].wikidata	https://www.wikidata.org/wiki/Q4785468
concepts[3].display_name	Plan (archaeology)
concepts[4].id	https://openalex.org/C81074085
concepts[4].level	3
concepts[4].score	0.5068040490150452
concepts[4].wikidata	https://www.wikidata.org/wiki/Q366872
concepts[4].display_name	Motion planning
concepts[5].id	https://openalex.org/C2777735758
concepts[5].level	2
concepts[5].score	0.4698920249938965
concepts[5].wikidata	https://www.wikidata.org/wiki/Q817765
concepts[5].display_name	Path (computing)
concepts[6].id	https://openalex.org/C136197465
concepts[6].level	2
concepts[6].score	0.4414916932582855
concepts[6].wikidata	https://www.wikidata.org/wiki/Q1729295
concepts[6].display_name	Variety (cybernetics)
concepts[7].id	https://openalex.org/C154945302
concepts[7].level	1
concepts[7].score	0.4302109479904175
concepts[7].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[7].display_name	Artificial intelligence
concepts[8].id	https://openalex.org/C18762648
concepts[8].level	2
concepts[8].score	0.4208647906780243
concepts[8].wikidata	https://www.wikidata.org/wiki/Q42213
concepts[8].display_name	Work (physics)
concepts[9].id	https://openalex.org/C90509273
concepts[9].level	2
concepts[9].score	0.3747214078903198
concepts[9].wikidata	https://www.wikidata.org/wiki/Q11012
concepts[9].display_name	Robot
concepts[10].id	https://openalex.org/C42475967
concepts[10].level	1
concepts[10].score	0.33352482318878174
concepts[10].wikidata	https://www.wikidata.org/wiki/Q194292
concepts[10].display_name	Operations research
concepts[11].id	https://openalex.org/C539667460
concepts[11].level	1
concepts[11].score	0.3221758008003235
concepts[11].wikidata	https://www.wikidata.org/wiki/Q2414942
concepts[11].display_name	Management science
concepts[12].id	https://openalex.org/C127413603
concepts[12].level	0
concepts[12].score	0.14636793732643127
concepts[12].wikidata	https://www.wikidata.org/wiki/Q11023
concepts[12].display_name	Engineering
concepts[13].id	https://openalex.org/C199360897
concepts[13].level	1
concepts[13].score	0.08628454804420471
concepts[13].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[13].display_name	Programming language
concepts[14].id	https://openalex.org/C78519656
concepts[14].level	1
concepts[14].score	0.0
concepts[14].wikidata	https://www.wikidata.org/wiki/Q101333
concepts[14].display_name	Mechanical engineering
concepts[15].id	https://openalex.org/C166957645
concepts[15].level	1
concepts[15].score	0.0
concepts[15].wikidata	https://www.wikidata.org/wiki/Q23498
concepts[15].display_name	Archaeology
concepts[16].id	https://openalex.org/C95457728
concepts[16].level	0
concepts[16].score	0.0
concepts[16].wikidata	https://www.wikidata.org/wiki/Q309
concepts[16].display_name	History
concepts[17].id	https://openalex.org/C13280743
concepts[17].level	1
concepts[17].score	0.0
concepts[17].wikidata	https://www.wikidata.org/wiki/Q131089
concepts[17].display_name	Geodesy
concepts[18].id	https://openalex.org/C205649164
concepts[18].level	0
concepts[18].score	0.0
concepts[18].wikidata	https://www.wikidata.org/wiki/Q1071
concepts[18].display_name	Geography
keywords[0].id	https://openalex.org/keywords/leverage
keywords[0].score	0.7561378479003906
keywords[0].display_name	Leverage (statistics)
keywords[1].id	https://openalex.org/keywords/benchmark
keywords[1].score	0.6451554894447327
keywords[1].display_name	Benchmark (surveying)
keywords[2].id	https://openalex.org/keywords/computer-science
keywords[2].score	0.6129910945892334
keywords[2].display_name	Computer science
keywords[3].id	https://openalex.org/keywords/plan
keywords[3].score	0.5490208864212036
keywords[3].display_name	Plan (archaeology)
keywords[4].id	https://openalex.org/keywords/motion-planning
keywords[4].score	0.5068040490150452
keywords[4].display_name	Motion planning
keywords[5].id	https://openalex.org/keywords/path
keywords[5].score	0.4698920249938965
keywords[5].display_name	Path (computing)
keywords[6].id	https://openalex.org/keywords/variety
keywords[6].score	0.4414916932582855
keywords[6].display_name	Variety (cybernetics)
keywords[7].id	https://openalex.org/keywords/artificial-intelligence
keywords[7].score	0.4302109479904175
keywords[7].display_name	Artificial intelligence
keywords[8].id	https://openalex.org/keywords/work
keywords[8].score	0.4208647906780243
keywords[8].display_name	Work (physics)
keywords[9].id	https://openalex.org/keywords/robot
keywords[9].score	0.3747214078903198
keywords[9].display_name	Robot
keywords[10].id	https://openalex.org/keywords/operations-research
keywords[10].score	0.33352482318878174
keywords[10].display_name	Operations research
keywords[11].id	https://openalex.org/keywords/management-science
keywords[11].score	0.3221758008003235
keywords[11].display_name	Management science
keywords[12].id	https://openalex.org/keywords/engineering
keywords[12].score	0.14636793732643127
keywords[12].display_name	Engineering
keywords[13].id	https://openalex.org/keywords/programming-language
keywords[13].score	0.08628454804420471
keywords[13].display_name	Programming language
language	en
locations[0].id	pmh:oai:arXiv.org:2401.03630
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2401.03630
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2401.03630
locations[1].id	doi:10.48550/arxiv.2401.03630
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2401.03630
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5103236436
authorships[0].author.orcid	https://orcid.org/0000-0001-9068-4247
authorships[0].author.display_name	Weizhe Chen
authorships[0].author_position	first
authorships[0].raw_author_name	Chen, Weizhe
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5026549557
authorships[1].author.orcid	https://orcid.org/0000-0002-5458-094X
authorships[1].author.display_name	Sven Koenig
authorships[1].author_position	middle
authorships[1].raw_author_name	Koenig, Sven
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5087538704
authorships[2].author.orcid	https://orcid.org/0000-0002-6784-473X
authorships[2].author.display_name	Bistra Dilkina
authorships[2].author_position	last
authorships[2].raw_author_name	Dilkina, Bistra
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2401.03630
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2024-01-13T00:00:00
display_name	Why Solving Multi-agent Path Finding with Large Language Model has not Succeeded Yet
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11714
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9995999932289124
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1707
primary_topic.subfield.display_name	Computer Vision and Pattern Recognition
primary_topic.display_name	Multimodal Machine Learning Applications
related_works	https://openalex.org/W2378211422, https://openalex.org/W2745001401, https://openalex.org/W2359600231, https://openalex.org/W2380019117, https://openalex.org/W3138952546, https://openalex.org/W1987886368, https://openalex.org/W1660309994, https://openalex.org/W2369187583, https://openalex.org/W3197207153, https://openalex.org/W3154539612
cited_by_count	1
counts_by_year[0].year	2024
counts_by_year[0].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2401.03630
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2401.03630
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2401.03630
primary_location.id	pmh:oai:arXiv.org:2401.03630
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2401.03630
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2401.03630
publication_date	2024-01-08
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	35
abstract_inverted_index.In	81
abstract_inverted_index.We	111, 142
abstract_inverted_index.an	20, 118
abstract_inverted_index.as	98
abstract_inverted_index.be	31
abstract_inverted_index.by	5, 59
abstract_inverted_index.is	42, 54, 95
abstract_inverted_index.it	70
abstract_inverted_index.of	8, 23, 38, 63, 89, 106, 137
abstract_inverted_index.on	49, 86, 117, 129, 146, 168
abstract_inverted_index.to	33, 72, 76, 127, 163
abstract_inverted_index.we	84, 159, 171
abstract_inverted_index.and	15, 66, 68, 102, 134, 158
abstract_inverted_index.can	30
abstract_inverted_index.has	18, 153
abstract_inverted_index.how	173
abstract_inverted_index.map	121, 133, 136
abstract_inverted_index.not	154
abstract_inverted_index.our	144, 165, 169
abstract_inverted_index.the	1, 6, 61, 78, 87, 104, 114, 125, 130, 138
abstract_inverted_index.use	160
abstract_inverted_index.why	147
abstract_inverted_index.LLMs	152
abstract_inverted_index.MAPF	108, 140, 150
abstract_inverted_index.With	0
abstract_inverted_index.also	96
abstract_inverted_index.been	19, 155
abstract_inverted_index.from	56, 183
abstract_inverted_index.hard	71
abstract_inverted_index.help	179
abstract_inverted_index.like	13
abstract_inverted_index.maze	135
abstract_inverted_index.path	91
abstract_inverted_index.plan	128
abstract_inverted_index.room	120, 132
abstract_inverted_index.show	113
abstract_inverted_index.that	27, 46
abstract_inverted_index.then	124
abstract_inverted_index.this	82, 181
abstract_inverted_index.used	32
abstract_inverted_index.very	43
abstract_inverted_index.with	109, 151, 175, 180
abstract_inverted_index.work	25, 45
abstract_inverted_index.yet,	157
abstract_inverted_index.(LLM)	12
abstract_inverted_index.Based	167
abstract_inverted_index.LLMs.	110
abstract_inverted_index.could	178
abstract_inverted_index.empty	119
abstract_inverted_index.first	112
abstract_inverted_index.focus	85
abstract_inverted_index.known	97
abstract_inverted_index.large	9, 36
abstract_inverted_index.other	57
abstract_inverted_index.route	100
abstract_inverted_index.solve	34
abstract_inverted_index.study	103
abstract_inverted_index.there	17, 41
abstract_inverted_index.tools	75
abstract_inverted_index.which	94
abstract_inverted_index.GPT-4,	16
abstract_inverted_index.amount	22
abstract_inverted_index.caused	4
abstract_inverted_index.harder	131
abstract_inverted_index.making	69
abstract_inverted_index.models	11, 29
abstract_inverted_index.paper,	83
abstract_inverted_index.recent	24
abstract_inverted_index.shares	47
abstract_inverted_index.tasks.	39
abstract_inverted_index.(MAPF),	93
abstract_inverted_index.ChatGPT	14
abstract_inverted_index.domains	58
abstract_inverted_index.failure	126
abstract_inverted_index.finding	92
abstract_inverted_index.limited	44
abstract_inverted_index.needed.	80
abstract_inverted_index.present	143
abstract_inverted_index.problem	88, 182
abstract_inverted_index.showing	26
abstract_inverted_index.solving	107, 149
abstract_inverted_index.success	7, 116
abstract_inverted_index.support	164
abstract_inverted_index.variety	37
abstract_inverted_index.various	161
abstract_inverted_index.without	122
abstract_inverted_index.However,	40
abstract_inverted_index.directly	148
abstract_inverted_index.external	74
abstract_inverted_index.insights	48
abstract_inverted_index.language	10
abstract_inverted_index.leverage	73
abstract_inverted_index.planning	53
abstract_inverted_index.position	145
abstract_inverted_index.results,	170
abstract_inverted_index.standard	139
abstract_inverted_index.combining	60
abstract_inverted_index.different	55, 176, 184
abstract_inverted_index.discussed	172
abstract_inverted_index.explosive	2
abstract_inverted_index.extensive	21
abstract_inverted_index.influence	3
abstract_inverted_index.planning,	67, 101
abstract_inverted_index.planning.	51
abstract_inverted_index.reasoning	79
abstract_inverted_index.benchmark.	141
abstract_inverted_index.difficulty	62
abstract_inverted_index.facilitate	77
abstract_inverted_index.foundation	28
abstract_inverted_index.motivating	115
abstract_inverted_index.obstacles,	123
abstract_inverted_index.successful	156
abstract_inverted_index.Multi-agent	52
abstract_inverted_index.backgrounds	177
abstract_inverted_index.experiments	162
abstract_inverted_index.hypothesis.	166
abstract_inverted_index.multi-agent	50, 64, 90
abstract_inverted_index.multi-robot	99
abstract_inverted_index.performance	105
abstract_inverted_index.researchers	174
abstract_inverted_index.coordination	65
abstract_inverted_index.perspectives.	185
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
sustainable_development_goals[0].id	https://metadata.un.org/sdg/11
sustainable_development_goals[0].score	0.41999998688697815
sustainable_development_goals[0].display_name	Sustainable cities and communities
citation_normalized_percentile