Massachusetts Institute of Technology 16.412J/6.834J Intelligent Embedded Systems Advanced Lecture Warm-Up Objective The purpose of this question is to exercise your ability to dive into the recent literature, to distill a clean understanding of the method, to track down supporting references, to communicate this method effectively and to evaluate the applicability of the method. This is a warm up exercise for the advanced lecture that you will be giving in a few weeks. This week you assemble a presentation. Next week this presentation will then go to other students in the class for feedback, and then you will write a plan for incorporating that feedback. Please prepare three copies of your presentation for next Wednesday. Problem: Path Planning Using Lazy PRM Many intelligent embedded systems move rapidly within a physical environment. This requires the ability to quickly generate plans to navigate around obstacles. While the best complete algorithms are doubly exponential, probabilistic algorithms have emerged that have very good practical performance, and probabilistic guarantees of convergence. This problem tests your understanding of the Lazy probabilistic roadmap planner (lazy PRM), and your ability to communicate the algorithm in a simple intuitive manner. Start by reading the paper: • R. Bohlin and L. Kavraki, Path planning using lazy PRM, in ICRA 2000. This paper was distributed in class.I have also distributed in class some guidelines for giving technical presentations. Please use these guidelines in order to develop and assess your presentation. Suppose you are part of an MIT team building a set of softball size satellites, called "Spheres”. Spheres will navigate around the corridors of the international space station, looking for leaks in the hull or problems with a set of environmental sensors. You've been asked to give a presentation of Lazy PRM to the team as a candidate algorithm for Spheres path planning. Please assemble a set of slides that intuitively explain the Lazy PRM algorithm and its underlying theory. Do not stop at the supplied reference, but track down any supporting references necessary to fully understand the theory. Include on your slides references to the sources used. To ground the approach, walk through the steps of PLR applied to the movement of Spheres between modules of space station. These slides might correspond to the steps outlined in each subsection of section 3 of the Bohlin and Kavraki paper. The slides should communicate visually whenever possible. Along with each slide include a text narrative (called a facing or notes page), describing that step in the algorithm. You should think through for yourself the best presentation structure so that you offer a comprehensive presentation of the method as it pertains to the Spheres problem. In your presentation you will probably want to include at least the following: • Flesh out any parts of the algorithm that are left open in the paper. For example, describe the A* algorithm mentioned in section 3.2. Select and describe one of the collision detection algorithms described in section 3.3. And so on for the remaining sections…. • Make design commitments for the lazy PLR algorithm, as suitable for the task. For example, demonstrate the algorithm on a drawing of part of space station, perhaps finding the relevant information about space station on the web (if available). In section 3.1 select a reasonable value for Mneighb, ρcolletc. and argue why these commitments are reasonable. Make similar commitments for each relevant subpart of section 3 of the paper.• Finally comment on the appropriateness of Lazy PLR to this task, highlighting any features of the algorithms, concerns and areas for future exploration. Use your judgment about length. Assume that your presentation is no longer than 45 minutes, hence you probably need no more than about 20 slides. Provide any additional background material as you find
View Full Document
Unlocking...