Using focusing search algorithms and a strong heuristic to solve the findpath problem in robotics

ABSTRACT

Two problems are associated with the seeking of good solutions to the find path problem (Find Path) in robotics. First, the use of artificial intelligence searching techniques is limited to the A* algorithm. Secondly, simple and poor heuristics are employed in this best-first search. To speed up the search, two approaches are taken in this paper: i) using two A*-based focusing search algorithms, A+ and A&dgr;, for FindPath; ii) constructing a problem-tailored strong heuristic, h2, under the configuration space representation chosen (2-D with rotation). These approaches are compared with the use of A* and a standard heuristic. Experimental evidence indicates that each of the new approaches improves speed considerably and solution quality in each case is very close to the optimal. When combined, the new approaches speed up the search by more than 40%. We conclude that A&dgr; is, among the three search algorithms studied, the fastest and most suitable one for high branching-factor problems such as FindPath, especially when a strong heuristic (such as h2) is employed.

REFERENCES

• 1: Henry W. Davis, Anna Bramanti-Gregor, and Jin Wang, The advaritages of using depth and breadth components in heuristic search. In Methodologies for Intelligent Systems 3, edited by Z. W. Kas and L. S~it, ta, North Holland, 1988, pp19-28
• 2: J. T. Schwartz , M. Sharir, A survey of motion planning and related geometric algorithms, Artificial Intelligence, v.37 n.1-3, p.157-169, Dec. 1988 [doi>10.1016/0004-3702(88)90053-7 ]
• 3: rtodney A. Brooks, Solving the findpath problem by good representation of free space. IEEE Trans. on Sys. Mart. and Cybern., Vol. SMC-13, No. 3, March/April 1983, pp190-233
• 4: Rodney A. Brooks and Tomas Lozano-Perez, A subdivision algorithm in configuration space for Find- Path with rotation. IEEE Trans. on Sys. Man. Cybern. Vol. SMC-15, No. 2, Mar/Apt 1985, pp224-233
• 5: Tomas Lozano-Perez, Spatial planning: A configuration space approach. IEEE Trans. on Computers, Vol. C-32, No. 2, Feb. 1983, pp108-120
• 6: Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
• 7: Jin Wang, Uaing Focusing Search Algorithms and Strong Heuristics to Solve the Findpath Problem in Robotics. Master Thesis, Dept. of Computer Science and Engineering, Wright State University, 1989
• 8: Anna Branlanti-Gregor, Unidirectional Heuristic Search: Improvements and Extensions. Master Thesis, Dept. of Computer Science and Engilteering, Wright State University, 1987
• 9: J. T. Schwartz ~nd M. Sharir, On the Piano movers' problem I1. General techniq,les for computing topological properties of real manifolds. Adv. Appl. Math., Vol. 4, 1983, pp298-351
• 10: Micha Sharir , Amir Schorr, On shortest paths in polyhedral spaces, SIAM Journal on Computing, v.15 n.1, p.193-215, Feb. 1986 [doi>10.1137/0215014]
• 11: M. Fredman and R. Taljan, Fibonacci heaps and their uses in improved network optimization algorthms. in: Proceedings 25th Annum IEEE Symposium on Foundations of Computer Science, 1984, pp338-346
• 12: Takao Asano , Tetsuo Asano , Leonidas Guibas , John Hershberger , Hiaroshi Imai, Visibility of disjoint polygons, Algorithmica, v.1 n.1, p.49-63, Jan. 1986 [doi>10.1007/BF01840436]
• 13: E. W. Dijkstra, A note on two problems in connect{on with graphs. 1Numerische M~tl~., Vol. 1, 1959, pp269-271
• 14: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 15: Subbarao Kambhampati and Larry Davis, Multiresolution path planning for mobile robots. IEEE Journal of Robotics and Automation, Vol. RA-2, No. 3, Sept. 1986

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Experimentation