Python实现机器人路径规划实验(A*、BFS、DFS、D*四种路径搜索算法)

Overview ------ 路径规划需要实现三个算法，DFS，A\*和D\*。BFS是已经实现好了的算法，可以直接跑，作为作业的参考。 三个路径规划算法只需要补充关键部分代码即可，需要补充代码的部分我用注释标识出来了，如下所示， ```python def searching(self): """ A_star Searching. :return: path, visited order """ self.PARENT[self.s_start] = self.s_start self.g[self.s_start] = 0 self.g[self.s_goal] = math.inf heapq.heappush(self.OPEN, (self.f_value(self.s_start), self.s_start)) ############################# START ############################# # PUT YOUR CODE HERE! pass ############################# END ############################# return self.extract_path(self.PARENT), self.CLOSED ``` 把代码在START和END之间补充完整即可。 相关的论文请参考 Papers这一节，除了A\*和D\*之外，还列举了相关的改进算法，感兴趣的同学可以自己查阅。 Directory Structure ------ . └── Search-based Planning ├── Breadth-First Searching (BFS) ├── Depth-First Searching (DFS) ├── A* └── D* └── Papers ## Animations - Search-Based A\* 和 D\* 的运行效果下面的动图所示，其中D\*算法是在线规划的算法，可以动态交互。 <div align=right> <table> <tr> <td><img src="Search_based_Planning/gif/DFS.gif" alt="dfs" width="400"/></a></td> <td><img src="Search_based_Planning/gif/BFS.gif" alt="bfs" width="400"/></a></td> </tr> </table> <table> <tr> <td><img src="Search_based_Planning/gif/Astar.gif" alt="astar" width="400"/></a></td> <td><img src="Search_based_Planning/gif/D_star.gif" alt="lpastar" width="400"/></a></td> </tr> </table> </div> ## Papers ### Search-base Planning * [A*: ](https://ieeexplore.ieee.org/document/4082128) A Formal Basis for the heuristic Determination of Minimum Cost Paths * [Learning Real-Time A*: ](https://arxiv.org/pdf/1110.4076.pdf) Learning in Real-Time Search: A Unifying Framework * [Real-Time Adaptive A*: ](http://idm-lab.org/bib/abstracts/papers/aamas06.pdf) Real-Time Adaptive A* * [Lifelong Planning A*: ](https://www.cs.cmu.edu/~maxim/files/aij04.pdf) Lifelong Planning A* * [Anytime Repairing A*: ](https://papers.nips.cc/paper/2382-ara-anytime-a-with-provable-bounds-on-sub-optimality.pdf) ARA*: Anytime A* with Provable Bounds on Sub-Optimality * [D*: ](http://web.mit.edu/16.412j/www/html/papers/original_dstar_icra94.pdf) Optimal and Efficient Path Planning for Partially-Known Environments * [D* Lite: ](http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf) D* Lite * [Field D*: ](http://robots.stanford.edu/isrr-papers/draft/stentz.pdf) Field D*: An Interpolation-based Path Planner and Replanner * [Anytime D*: ](http://www.cs.cmu.edu/~ggordon/likhachev-etal.anytime-dstar.pdf) Anytime Dynamic A*: An Anytime, Replanning Algorithm * [Focussed D*: ](http://robotics.caltech.edu/~jwb/courses/ME132/handouts/Dstar_ijcai95.pdf) The Focussed D* Algorithm for Real-Time Replanning * [Potential Field, ](https://journals.sagepub.com/doi/abs/10.1177/027836498600500106) [[PPT]: ](https://www.cs.cmu.edu/~motionplanning/lecture/Chap4-Potential-Field_howie.pdf) Real-Time Obstacle Avoidance for Manipulators and Mobile Robots * [Hybrid A*: ](https://ai.stanford.edu/~ddolgov/papers/dolgov_gpp_stair08.pdf) Practical Search Techniques in Path Planning for Autonomous Driving