CIS480 Final Exam Notes - Hyper Linked
[Note: The problem instances and maps referred to are found in the Appendix].
1. What is a paradigm? What are the main paradigms in intelligent robotic design? Discuss the history of their development, their approach to the three main primitives of robotics, and their relationship to the historical problems of robot design, such as the frame problem (& here) and the closed world assumption.
2. Discuss ethology – its history and its influence on robotics. Include in your discussion the concepts of behavior, emergence, innate releasing mechanism and action-oriented perception.
3. Discuss this statement: “The world is its own best representation.” What does it mean? How does it relate to robotic design? How does it relate to the historical development of robot design concepts? How does it relate to our robot world simulator design? Are there limitations to its applicability? If so, what are they? How does it relate to semi-unreliable actuator performance?
4. What is the difference between a topological map and a metrical map? When is each used to best advantage? Which is used most often by people? Support your answer with an extended, cogent argument.
5. Discuss the A* algorithm. How does it relate to state space search? In what way is the basic virtual data structure a search tree? How is the tree in actuality represented as a priority list? What is a heuristic function? When is a heuristic function admissible? What are the roles of the g, h, and f functions. Which node is chosen to be expanded? What happens when a node is expanded? What heuristic functions can be used to solve the 8 Puzzle? Are they admissible? Why or why not?
6. Discuss the Limo Driver Problem. Describe the essential details of the sample instance shown. Why is it an asymmetric Traveling Salesperson Problem? What heuristic function can be used to allow the LDP to be solved using A*? Show that that heuristic is admissible.
7. Potential question #7 dropped.
8. Consider the following scenario: The robot has just finished creating a topological map of North Campus. It is “kidnapped” and placed at an arbitrary North Campus location. For some reason the senseLocation sensor has failed, but senseNumPaths is still intact. Describe a generic algorithm the robot can use to re-orient itself with the minimal number of moves. [By generic we mean the algorithm can be used in any mission possible environment].
9. Consider the topological maps above. Which maps represent a mission impossible environment for the Kidnapped Robot Problem described immediately above? Why? For each environment that is a mission possible environment what features make it so?
10. Suppose that, in anticipation of sensor problems, the robot is given a certain number of identical markers which it can use to mark any of the locations it chooses. For each mission impossible environment, what is the minimum number of markers the robot would need in order to enable it to solve the Kidnapped Robot Problem? Show on each of the topological maps where markers should be placed.
11. What did you learn from your semester project, especially with respect to the various aspects of robot design theory we have been discussing? Choose several specific issues to illustrate. If you were starting work on your project today, in what way would you approach it differently? Why? Would you choose the same project? Why or why not? Be specific. In what ways would you design things differently? Be specific.