dijkstra A和D等算法介绍.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：1.95M 资料格式：pdf 举报版权申诉

ce7c49c5-d924-4639-b786-b5b414beb639.pdf-第1页.png

第1页 / 共132页

ce7c49c5-d924-4639-b786-b5b414beb639.pdf-第2页.png

第2页 / 共132页

ce7c49c5-d924-4639-b786-b5b414beb639.pdf-第3页.png

第3页 / 共132页

ce7c49c5-d924-4639-b786-b5b414beb639.pdf-第4页.png

第4页 / 共132页

ce7c49c5-d924-4639-b786-b5b414beb639.pdf-第5页.png

第5页 / 共132页

ce7c49c5-d924-4639-b786-b5b414beb639.pdf-第6页.png

第6页 / 共132页

ce7c49c5-d924-4639-b786-b5b414beb639.pdf-第7页.png

第7页 / 共132页

ce7c49c5-d924-4639-b786-b5b414beb639.pdf-第8页.png

第8页 / 共132页

文本预览

Robotic Motion Planning: A* and D* Search Robotics Institute 16-735 http://www.cs.cmu.edu/~motionplanning Howie Choset http://www.cs.cmu.edu/~choset 16-735, Howie Choset with slides from Ayorkor Mills-Tettey, Vincent Lee-Shue Jr. Prasad Narendra Atkar, Kevin Tantisevi

Outline • Overview of Search Techniques • A* Search • D* Search • D* Lite 2

Graphs Collection of Edges and Nodes (Vertices) A tree 3

Search in Path Planning • Find a path between two locations in an unknown, partially known, or known environment • Search Performance – Completeness – Optimality → Operating cost – Space Complexity – Time Complexity 4

Search • Uninformed Search – Use no information obtained from the environment – Blind Search: BFS (Wavefront), DFS • Informed Search – Use evaluation function – More efficient – Heuristic Search: A*, D*, etc. 5

Uninformed Search Graph Search from A to N BFS 6

Informed Search: A* Notation • n → node/state • c(n1,n2) → the length of an edge connecting between n1 and n2 • b(n1) = n2 → backpointer of a node n1 to a node n2. 7

Informed Search: A* • Evaluation function, f(n) = g(n) + h(n) • Operating cost function, g(n) – Actual operating cost having been already traversed • Heuristic function, h(n) – Information used to find the promising node to traverse – Admissible → never overestimate the actual path cost Cost on a grid 8

分享到：

赞收藏

资料库

dijkstra A和D等算法介绍.pdf

相关推荐

课程资源

热门标签

最新资料