Earticle

초록

영어

Multi-process bidirectional heuristic search algorithms (such as PBA*) that utilize island nodes have been shown to have the potential for exponential speedup over their plain counterparts that do not utilize island nodes. PBA* (Parallel Bidirectional A*) is a primary algorithm in this area and, to the best of our knowledge, unique in its usage of island nodes for reducing the size of the traversed search space and in its usage of multidimensional heuristics for reducing interprocess communication cost. Both, island nodes use and reference nodes use within the context of multidimensional heuristics have been reported to provide excellent performance, compared to plain heuristic search counterparts. However, both of these two features have also resisted refinements for over two decades. Specifically, the two main issues are: how to identify well-placed (in the state space) island nodes, and how to generate well-placed reference nodes. The work presented in this paper is an initial step toward this end. We present two methods, one employing Voronoi diagrams for the purpose of identifying well-placed island nodes, and one employing Kohonen Networks for the purpose of identifying well-placed reference nodes. We implement and compare our methods against a plain version of PBA*. Our finding indicate that the cost of incorporating the proposed improvements into PBA* is negligible; and when PBA* is equipped with the island identification method, or with the reference node identification method, it outperforms its random island nodes counterpart and its random reference nodes counterpart,
respectively, for the vast majority of test cases.

목차

Abstract
 1. Introduction and Background
 2. Proposed Methods
 3. Performance evaluation
 4. Conclusion
 References

저자

• Anestis A. Toptsis [ Dept. of Computer Science and Engineering, York University ]
• Rahul A. Chaturvedi [ Dept. of Computer Science and Engineering, York University ]
• Avaz Feroze [ Dept. of Computer Science and Engineering, York University ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Advanced Science and Technology

• 간기

  월간

• pISSN

  2005-4238

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605