用代数方法解决机器人路径规划内存瓶颈问题
A Space-Efficient Algebraic Approach to Robotic Motion Planning
- 通过多项式树证书技术改进代数检测方法
- 实测证明新算法内存占用远低于传统方法
- 适合需要低内存运行的机器人任务场景
针对基础设施巡检和自动化手术成像等机器人任务中的路径规划问题，本文将其建模为组合优化问题——图巡视（Graph Inspection）。现有最优算法因指数级空间复杂度而难以实用。本文提出一种基于代数工具的内存高效方法，利用与特定算术电路相关联的多项式单项式检测技术。首先修复了已有工作中单项式检测的微小缺陷，提出名为“树证书”的新方法；进一步证明这些工具不仅能检测单项式，还可高效恢复目标单项式，从而拓展了代数方法的应用范围。针对图巡视问题，设计并评估了完整的代数处理流程，工程实现表明基于电路的算法确实在实践中具备显著内存优势，激励后续工程优化。
原文摘要 · Abstract (English)
We consider efficient route planning for robots in applications such as infrastructure inspection and automated surgical imaging. These tasks can be modeled via the combinatorial problem Graph Inspection. The best known algorithms for this problem are limited in practice by exponential space complexity. In this paper, we develop a memory-efficient approach using algebraic tools related to monomial testing on the polynomials associated with certain arithmetic circuits. Our contributions are two-fold. We first repair a minor flaw in existing work on monomial detection using a new approach we call tree certificates. We further show that, in addition to detection, these tools allow us to efficiently recover monomials of interest from circuits, opening the door for significantly broadened application of related algebraic tools. For Graph Inspection, we design and evaluate a complete algebraic pipeline. Our engineered implementation demonstrates that circuit-based algorithms are indeed memory-efficient in practice, thus encouraging further engineering efforts.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。