已入深夜,您辛苦了!由于当前在线用户较少,发布求助请尽量完整地填写文献信息,科研通机器人24小时在线,伴您度过漫漫科研夜!祝你早点完成任务,早点休息,好梦!

Exact Anytime Multi-Agent Path Finding Using Branch-and-Cut-and-Price and Large Neighborhood Search

跳跃式监视 路径(计算) 数学优化 计算机科学 网格 集合(抽象数据类型) 国家(计算机科学) 搜索树 上下界 分界 树(集合论) 搜索算法 算法 数学 人工智能 组合数学 数学分析 几何学 程序设计语言
作者
Edward Lam,Daniel Harabor,Peter J. Stuckey,Jiaoyang Li
出处
期刊: [Association for the Advancement of Artificial Intelligence]
卷期号:33 (1): 254-258 被引量:2
标识
DOI:10.1609/icaps.v33i1.27202
摘要

Given a set of agents on a grid, the multi-agent path finding problem aims to find a path that moves each agent from its given start location to its target location such that they do not collide and that the sum of arrival times is minimized. LNS2 is a state-of-the-art algorithm for anytime, suboptimal solving. It is an upper-bounding algorithm that repeatedly adjusts an existing solution and, being a local search, is oblivious to optimality. BCP is a state-of-the-art algorithm for exact solving. It is a lower-bounding tree search that attempts to tighten the lower bound until a solution appears. As BCP operates on the lower bound, the first solution it finds is optimal or nearly optimal, and therefore has poor anytime behavior. This paper proposes to tightly couple LNS2 and BCP to achieve better anytime, suboptimal solving while retaining the optimality guarantee of BCP. Experiments indicate that the combination achieves better anytime behavior than BCP in general and better suboptimal performance than LNS2 on congested maps.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
salt发布了新的文献求助10
刚刚
ZND发布了新的文献求助10
1秒前
yang发布了新的文献求助10
2秒前
2秒前
机灵采萱发布了新的文献求助10
2秒前
ttxxcdx发布了新的文献求助10
3秒前
谦让鹏涛发布了新的文献求助10
4秒前
summanus发布了新的文献求助10
4秒前
情怀的应助被无解采纳,获得10
4秒前
5秒前
龙行天下爱完成签到,获得积分20
5秒前
何伟完成签到 ,获得积分20
6秒前
Yx发布了新的文献求助10
6秒前
7秒前
Ava的应助被啥傻啥啥啥傻嗯采纳,获得10
7秒前
8秒前
cxh完成签到,获得积分10
9秒前
夜雨声烦完成签到,获得积分10
10秒前
Pikachu完成签到,获得积分10
11秒前
ttxxcdx发布了新的文献求助10
12秒前
bubble发布了新的文献求助10
12秒前
13秒前
13秒前
15秒前
李健的应助被xin采纳,获得10
15秒前
huangyi完成签到 ,获得积分10
16秒前
无解发布了新的文献求助10
16秒前
今后的应助被ZZZ采纳,获得10
16秒前
满意盈完成签到,获得积分10
19秒前
马华化完成签到,获得积分0
20秒前
天涯明月完成签到,获得积分10
20秒前
springlrt的应助被将个烂就采纳,获得30
21秒前
田様的应助被将个烂就采纳,获得10
21秒前
ttxxcdx发布了新的文献求助10
21秒前
21秒前
22秒前
tt关注了科研通微信公众号
23秒前
23秒前
24秒前
tomatoGG发布了新的文献求助10
24秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
John McDowells Bildungstheorie 800
八旗制度の研究 600
plantTFDB 508
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8172444
求助须知:如何正确求助?哪些是违规求助? 9565203
关于积分的说明 21778439
捐赠科研通 7764184
什么是DOI,文献DOI怎么找? 3431343
关于科研通互助平台的介绍 2555224
邀请新用户注册赠送积分活动 2476362