CS 545: Introduction to Robotics Fall 2019HW 4: Path Planning with RRTsIn this assignment we’ll explore a fundamental problem in robotics: path planning. Thatis, the problem of moving a robot from an initial configuration A to a goal configurationB, while avoiding obstacles along the way.You can think of this as a literal path planning problem where a mobile base mustnavigate to a goal, or in a more abstract application, such as finding a sequence of jointangles that will move an arm from one position to another.This problem has two primary issues that make it difficult to apply shortest-path algorithmsfrom graph theory, like Djikstra’s or A-star:1. The search space is continuous: we dont have a predefined set of discrete nodes tosearch through. Any kind of discretized planning will require us to create our ownnodes.2. There may not be an accurate measure of distance. For example, how do we determinethe distance between two configurations for a robot arm? Do we look at theend effector pose? The joint angles? There is no clear answer.1 RRTOne method to solve this problem is an algorithm called Rapidly-exploring RandomTrees (RRT). The algorithm itself is quite simple, and only has 1 hyperparameter to tune!Consider a 2D search problem where we must find a path from a starting point Nstartto a goal point Ngoal, while avoiding the obstacles. To do so, we must build a path (asequence of points) connecting Nstart to Ngoal. We’ll be assuming a euclidean distancefunction for our implementation.1CS 545: Introduction to Robotics Fall 2019Figure 1: A 2D RRT search space with no obstacles (left) and a single obstacle (right).Nstart is in green, while Ngoal is in red.An RRT is an iteratively built tree with clever use of random sampling that is likely(though not guaranteed) to build one such path from Nstart to Ngoal.We first randomly sample a point in the search space. Let’s call it Psample.We then compute the direction vector between the closest node Nclose in our search treeand Psample.2CS 545: Introduction to Robotics Fall 2019Now we create a new node that is a fixed distance δ away from Nclose along our directionvector, which we’ll call Nnew.If Nnew is not in collision with an obstacle, we add it to our search tree.Figure 2: A valid Nnew will not collide with any obstacles (left). A Nnew that does collide(right) should be discarded.3CS 545: Introduction to Robotics Fall 2019After every new addition, we check if that point is within δ of the goal position. If so,we connect to the goal and draw our path.Figure 3: Once Nnew is clCS 545代做、RRTs代做、代寫Python程序語言、代ose enough to Ngoal, connect the two nodes and trace the pathfrom Nstart to Ngoal.Note that the path we build is quite convoluted. RRT will only build a valid path, notnecessarily the shortest path! The algorithm provides no proof of optimality, but it isrelatively fast to compute compared to other path planning algorithms.The example above is restricted to a 2-dimensional search problem, but the code you willwrite will be able to work across N-dimensional search spaces.2 RRTImplement the empty methods in the RRT, CollisionBox, and CollisionSphere classesin src/rrt.py and src/collision.py. The skeleton code lays out the basic structure,alongside a Node implementation you may find helpful as a data structure. You are freeto modify the RRT class as needed, but you MUST implement the methods provided.3 TestingUnit tests are provided to help you check and bugfix your implementation. Look throughthe tests in test/test rrt.py to understand what each unit test is looking for.4CS 545: Introduction to Robotics Fall 2019You can run unit tests for your RRT with the following commands:cd code/rrt# Run all tests for RRTnose2 test.test_rrt# Run a single test classnose2 test.test_rrt.TestRRTInit# Run a single test casenose2 test.test_rrt.TestRRTInit.test_rrt_init_basicThe TestRRTBuild test case will run an end-to-end test of your RRT. Make sure you’vepassed this final test case before moving on.4 VisualizationTo get a visual understanding of what your RRT is doing, we have implemented a specialcase of the RRT for 2-dimensional search problems with a visualization method.Finish the implementation in src/planar rrt.py and examine the unit test intest/test planar rrt.py. You can change the input values to experiment with yourPlanarRRT, but first try out the default configuration. You should see a visualizationsimilar to the ones illustrated in this document!# Run the PlanarRRTnose2 test.test_planar_rrt5 QuestionsIn the pdf file answers.pdf answer each of the following questions in a couple sentences.1. Why is the path returned by the RRT not guaranteed to be optimal (i.e. not theshortest feasible path)?2. What effect will increasing δ have on the performance of the RRT?5CS 545: Introduction to Robotics Fall 20193. What effect will increasing the bounds of the search space have on the performanceof the RRT? How about increasing the number of dimensions of the search space?4. Why is it important to have a relatively small δ? Hint: think about what wouldhappen if we have lots of small obstacles in our search space6轉自：http://www.3daixie.com/contents/11/3444.html