arXiv:2512.20711cs.RO2025-12

提出可随时求解的优化框架,高效规划移动搜索路径以缩短寻物时间。

Anytime Metaheuristic Framework for Global Route Optimization in Expected-Time Mobile Search

  • 基于最小延迟问题构建模型,结合辅助目标提升搜索效率
  • 在大规模数据集上实现更优解质量与运行时权衡,优于现有方法
  • 适合需要快速生成初始方案且资源受限的机器人搜索场景

预期时间移动搜索(ETS)是机器人领域基础任务,要求移动传感器在环境中导航以最小化定位隐藏物体的期望时间。在静态二维连续环境中,全局路径优化因目标函数评估困难而研究不足,根源在于环境连续性及运动与可视性约束的相互作用。先前工作通过部分离散化处理,采用效用贪婪启发式求解离散感知问题;另有研究间接利用固定图上的最小延迟问题近似目标函数,借助高效元启发式算法实现全局路径优化。本文在此基础上提出Milaps(Minimum latency problems)——一种基于模型的ETS解决方案框架,引入新颖的辅助目标,并采用近期表现优异的任意时元启发式算法求解旅行配送员问题。在新构建的大规模数据集上评估显示,该方法在解质量与运行时间之间实现更优权衡,最佳策略能快速生成初步解,为感知配置分配静态权重,并通过元启发式优化全局代价。定性分析进一步验证了框架在多种场景下的灵活性。

原文摘要 · Abstract (English)

Expected-time mobile search (ETS) is a fundamental robotics task where a mobile sensor navigates an environment to minimize the expected time required to locate a hidden object. Global route optimization for ETS in static 2D continuous environments remains largely underexplored due to the intractability of objective evaluation, stemming from the continuous nature of the environment and the interplay of motion and visibility constraints. Prior work has addressed this through partial discretization, leading to discrete-sensing formulations tackled via utility-greedy heuristics. Others have taken an indirect approach by heuristically approximating the objective using minimum latency problems on fixed graphs, enabling global route optimization via efficient metaheuristics. This paper builds on and significantly extends the latter by introducing Milaps (Minimum latency problems), a model-based solution framework for ETS. Milaps integrates novel auxiliary objectives and adapts a recent anytime metaheuristic for the traveling deliveryman problem, chosen for its strong performance under tight runtime constraints. Evaluations on a novel large-scale dataset demonstrate superior trade-offs between solution quality and runtime compared to state-of-the-art baselines. The best-performing strategy rapidly generates a preliminary solution, assigns static weights to sensing configurations, and optimizes global costs metaheuristically. Additionally, a qualitative study highlights the framework's flexibility across diverse scenarios.

路径规划元启发式机器人搜索

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。