摘要翻译：
本文研究了一种基于对称性的搜索空间缩减技术，它可以将无向均匀代价网格地图上的最优寻路速度提高38倍。我们的技术将网格映射分解成一组空矩形，从每个矩形中移除所有内部节点，并可能从周边移除一些节点。然后，我们在选定的剩余周界节点对之间添加一系列宏边，以方便在每个矩形中进行可证明的最优遍历。我们还开发了一种新的在线剪枝技术来进一步加快搜索速度。我们的算法速度快，内存效率高，并且保持了与在未修改的网格地图上搜索相同的最优性和完备性保证。
---
英文标题：
《Symmetry-Based Search Space Reduction For Grid Maps》
---
作者：
Daniel Harabor and Adi Botea and Philip Kilby
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Robotics        机器人学
分类描述：Roughly includes material in ACM Subject Class I.2.9.
大致包括ACM科目I.2.9类的材料。
--

---
英文摘要：
  In this paper we explore a symmetry-based search space reduction technique which can speed up optimal pathfinding on undirected uniform-cost grid maps by up to 38 times. Our technique decomposes grid maps into a set of empty rectangles, removing from each rectangle all interior nodes and possibly some from along the perimeter. We then add a series of macro-edges between selected pairs of remaining perimeter nodes to facilitate provably optimal traversal through each rectangle. We also develop a novel online pruning technique to further speed up search. Our algorithm is fast, memory efficient and retains the same optimality and completeness guarantees as searching on an unmodified grid map.
---
PDF链接：
https://arxiv.org/pdf/1106.4083