Predicting the Performance of Randomized Parallel Search: An Application to Robot Motion Planning

• Alanberg-Navony, N., Itai, A., and Moran, S.: 1994, Average and randomized complexity of distributed problems, Technical Report, Technion, Haifa, Israel.

  Google Scholar 

• Amato, N. M. and Dale, L. K.: 1999, Probabilistic roadmap methods are embarrassingly parallel, in: Proc. IEEE Internat. Conf. on Robotics and Automation, pp. 688–694.

• Challou, D., Boley, D., Gini, M., Kumar, V., and Olson, C.: 1998, Parallel search algorithms for robot motion planning, in: K. Gupta and A. del Pobil (eds), Practical Motion Planning in Robotics: Current Approaches and Future Directions, Wiley, New York, pp. 115–131.

  Google Scholar 

• Challou, D., Gini, M., and Kumar, V.: 1993, Parallel search algorithms for robot motion planning, in: Proc. of IEEE Internat. Conf. on Robotics and Automation, Vol. 2., pp. 46–51.

  Google Scholar 

• Cook, D. J. and Varnell, R. C.: 1998, Adaptive parallel iterative deepening search, J. Artificial Intelligence Res. 9, 139–166.

  Google Scholar 

• Corporation, T. M.: 1992, The connection machine CM-5 Technical Summary, Thinking Machines Corporation, Cambridge, MA.

  Google Scholar 

• Ertel, W.: 1992, OR-parallel theorem proving with random competition, in: A. Voronokov (ed.), LPAR'92: Logic Programming and Automated Reasoning, Lecture Notes in Artificial Intelligence 624, Springer, Berlin, pp. 226–237.

  Google Scholar 

• Ertel, W.: 1993, Massively parallel search with random competition, in: Working Notes of the 1993 AAAI Spring Symposium for Innovative Applications of Massive Parallelism, pp. 62–69, AAAI Press, Menlo Park, CA; available as Technical Report No. TR SS-93-04.

  Google Scholar 

• Ferreira, A. and Pardalos, P. (eds): 1996, Solving Combinatorial Optimization Problems in Parallel: Methods and Techniques, Lecture Notes in Computer Science 1054, State-of-the-Art Surveys, Springer, New York.

  Google Scholar 

• Grama, A. and Kumar, V.: 1999, State of the art in parallel search techniques for discrete optimization problems, IEEE Trans. Knowledge Data Engrg. 11(1), 28–35.

  Google Scholar 

• Henrich, D., Wurrl, C., and Woern, H.: 1998, Multi-directional search with goal switching for robot path planning, in: A. P. del Pobil, J. Mira and M. Ali (eds), Tasks and Methods in Applied Artificial Intelligence, Lecture Notes in Artificial Intelligence 1416, Springer, Berlin, pp. 75–84.

  Google Scholar 

• Hoel, P., Port, S., and Stone, C.: 1971, Introduction to Probability Theory, Houghton Mifflin Company, Boston, MA.

  Google Scholar 

• Hoos, H. H.: 1998, Stochastic Local Search – Methods, Models, Applications, PhD Thesis, the Darmstadt University of Technology, Germany.

  Google Scholar 

• Hoos, H. H. and Stützle, T.: 1998, Evaluating Las Vegas algorithms – Pitfalls and remedies, in: Proc. of the 14th Conf. on Uncertainty in Artificial Intelligence, pp. 238–245, Morgan Kaufmann, Los Altos, CA.

  Google Scholar 

• Hsu, D., Latombe, J., Motwani, R., and Kavraki, L.: 1999, Capturing the connectivity of highdimensional geometric spaces by parallelizable random sampling techniques, in: P. Pardalos and S. Rajasekaran (eds), Advances in Randomized Parallel Computing, Combinatorial Optimization Series, Kluwer Academic Publishers, Dordrecht, pp. 159–182.

  Google Scholar 

• Janakiram, V., Agrawal, D., and Mehrotra, R.: 1988, A randomized parallel backtracking algorithm, IEEE Trans. Computers 37(12), 1665–1675.

  Google Scholar 

• Karp, R. and Zhang, Y.: 1993, Randomized parallel algorothms for backtrack search and branch-and-bound computation, J. ACM 40(3), 765–789.

  Google Scholar 

• Kavraki, L. E. and Latombe, J. C.: 1998, Probabilistic roadmaps for robot path planning, in: K. Gupta and A. del Pobil (eds), Practical Motion Planning in Robotics: Current Approaches and Future Directions, Wiley, New York, pp. 33–53.

  Google Scholar 

• Kim, S. W. and Boley, D.: 2001, Building and navigating a network of local minima, J. Robotic Systems 18(8), 405–419.

  Google Scholar 

• Latombe, J. C.: 1991, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA.

  Google Scholar 

• Li, G.-J. and Wah, B. W.: 1986, Coping with anomalies in parallel branch-and-bound algorithms, IEEE Trans. Computers 35.

• Mehrotra, R. and Gehringer, E. F.: 1985, Superlinear speedup through randomized algorithms, in: Proc. of Internat. Conf. on Parallel Processing, pp. 291–300.

• Rao, V. N. and Kumar, V.: 1993, On the efficiency of parallel backtracking, IEEE Trans. Parallel Distributed Systems 4(4), 427–437.

  Google Scholar 

• Reeves, C. R.: 1993, Modern Heuristic Techniques for Combinatorial Problems, Wiley, New York.

  Google Scholar 

• Reif, J.: 1979, Complexity of the Mover's problem and generalizations, in: Proc. of IEEE Symposium on Foundations of Computer Science, pp. 421–427.

Download references