Shive
- 1. ROBOT NAVIGATIONROBOT NAVIGATION ININ DISCRETE & CONTINUOSDISCRETE & CONTINUOS ENVIRONMENTSENVIRONMENTS BY :BY : SOHEIL GHANBARISOHEIL GHANBARI HOSSEIN MOBASHERHOSSEIN MOBASHER
- 2. Introduction Discrete Uniformed Search Algorithms DFS BFS Informed Search Algorithms RBFS A* Genetic Algorithm Hill Climbing Continues ANT Colony Rapidly-exploring Random Tree References
- 3. Path planning in robotics consists in the design of the best geometric path between two given configurations. Often the term motion planning is used to include also the design of the time law (time history) that the rover must follow on the geometric path. The geometric path must avoid all obstacles present in the physical space.
- 4. Depth-first search油(DFS) is an油algorithm油for traversing or searching油tree油or油graph油data structures. One starts at the油root油(selecting some node as the root in the graph case) and explores as far as possible along each branch before油backtracking.
- 5. DB A C E
- 9. DB A C E
- 12. Complete? No: fails in infinite-depth spaces, spaces with loops. Modify to avoid repeated states along path. Complete in finite spaces Time Complexity ? O(bm ): terrible if m is much larger than b But if solutions are dense, may be much faster than breadth-first. Optimal? No
- 13. Breadth-First Search油(BFS) is a油strategy for searching in a graph油when search is limited to essentially two operations: visit and inspect a node of a graph. gain access to visit the nodes that neighbor the currently visited node. Expand shallowest unexpanded node.
- 14. Example of BFS execution
- 15. Example of BFS execution
- 16. Example of BFS execution
- 17. Example of BFS execution
- 18. Example of BFS execution
- 19. Example of BFS execution
- 20. Example of BFS execution
- 21. Example of BFS execution
- 22. Example of BFS execution
- 23. Example of BFS execution
- 24. Example of BFS execution
- 25. Example of BFS execution
- 26. Example of BFS execution
- 28. RBFS is a linear-space algorithm that expands nodes in best-first order even with a non-monotonic cost function and generates fewer nodes than iterative deepening with a monotonic cost function.
- 29. 55 1122 2
- 32. Complete? Like A*. Time Complexity ? Time complexity difficult to characterize. The worst-case time complexity of RBFS is O(b2d - 1 ). Optimal? Like A*, optimal if h(n) is admissible.
- 33. Idea: avoid expanding paths that are already expensive. Evaluation function f(n) = g(n) + h(n) g(n) = cost so far to reach n h(n) = estimated cost to goal from n f(n) = estimated total cost of path through n to goal
- 34. Problem: Find a path from Arad to Bucharest.
- 43. Genetic Algorithms were invented to mimic some of the processes observed in natural evolution. The idea with GA is to use this power of evolution to solve optimization problems.
- 45. Like climbing Everest in thick fog with amnesia. Useful to consider state space landscape. Random-restart hill climbing overcomes local maxima. Random sideways moves escape from shoulders loop on flat maxima.
- 46. The油ANT Colony Optimization油algorithm油is a probabilistic technique for solving computational problems which can be reduced to finding good paths. In the natural world, ants (initially) wander油randomly, and upon finding food return to their colony while laying own pheromone trails.
- 48. RRT is a data structure and algorithm that is designed for efficiently searching nonconvex high-dimensional spaces. RRTs are constructed incrementally in a way that quickly reduces the expected distance of a randomly- chosen point to the tree.
- 49. An animation of a RRT starting from iteration 0 till 10000
- 50. Artificial Intelligence, A modern approach. 2nd Edition, Stuart J. Russel, Peter Norving. http://www.doc.ic.ac.uk/~nd/surprise_97/journal/vol4/jmd/ http://www.ladispe.polito.it/robotica/PhDcourse/2009/Path_planning_en_slides.pdf http://citeseer.ist.psu.edu/311812.html http://eprints.kfupm.edu.sa/60786/1/60786.pdf http://www.cse.ohio-state.edu/~gurari/course/cis680/ http://www.biolab.si/gregorl/Students/mui/Recursive%20Best-First%20Search.ppt http://www.cs.ucf.edu/~dmarino/ucf/cop3502/lec_biswas/recursion12.pdf http://www.ics.uci.edu/~smyth/courses/cs271/topic3_heuristicsearch.ppt http://pdf.aminer.org/000/265/208/autonomous_path_planning_in_a_variety_of_environment s.pdf
- 51. Any Question ?
- 52. Thanks for your attention