====== Topics and Questions for the Exam ====== ===== A list of possible questions for the exam tests ===== * Characterize the main difference between stationary robots (robotic arms/manipulators) and mobile robots? * What type of mobile robots are you aware of? * Can you name at least three types of ground robots? If so, please list them. * List three main parts of a robot? * sensors, actuators, controllers * What is embodiment in the context of robots and their interactions with the world? * Characterized main differences between exteroceptive and proprioceptive sensors. * List three exteroceptive (proximity) sensors * What is Central Pattern Generator (CPGs) and how it can be utilized for controlling a robot motion? * Describe briefly notion of degrees of freedom (DOF) and Controllable DOF (CDOF) * Characterize differences between holonomic and nonholonomic robots? * What is the duty factor of the walking robot? Express it regarding stance and swing phase of the gait cycle * List three primitives of robotics that are used in robotic paradigms. * What are the three fundamental robotic paradigms? * Characterize hierarchical robotic paradigm? * What is the closed world assumption? * We assume that the world model contains everything the robot needs to know * What is the frame problem? * How can we address the frame problem challenge? * Sketch an example of block diagram of the hierarchical controller. Draw typical blocks and links. * Characterize reactive robotic paradigm? * List of three categories of behaviors and briefly characterize them. * Can you characterize three types of the reflexive behaviors * Briefly describe typical components of the hybrid (deliberative/reactive) paradigm. * Sketch a control schema of a mobile robot with basic blocks and links. * Characterize main differences for Feedback and feedforward motion controller. * What are the typical control loop periods (frequencies) of the control layers, aka temporal decomposition? * Define configuration space C and Cfree. * Define a path and trajectory within the context of path planning. * Show a configuration space for a disk-shaped robot in a polygonal world. Draw a world and the respective configuration space. * Briefly describe visibility graph based path planning method * Briefly describe the cell decomposition based method, e.g., trapezoidal decomposition. * What is Shortest Path Map (SPM)? * What is the Voronoi diagram and how it can be used for path planning? * Characterize differences between path planning based on visibility graph and Voronoi diagram. * Characterize path planning using navigation mesh? * Characterize grid-based path planning methods? * What type of grid-based approach do you know for representing 3D grid maps? * Describe based steps of grid-based planning * What is Bresenham's line algorithm and how you will use it in path planning? * What is Distance Transform based path planning and how it works? * How can you speed graph search algorithms for grid-based representation? * Characterize main ideas of the Jump Point Search algorithm for grid-based path planning. * How can you improve path length for grid-based optimal path planning? * Briefly describe the main ideas of the D* Lite algorithm. * What type of environment representation for robotic exploration do you know? * What is the main idea and benefits of the so-called occupancy grid maps? * Describe the main assumption considered for a simple update of the occupancy grid maps. * Cells are completely free of occupied. Cells as random variables are independent of each other. The state is static. * Characterize main differences between models of sonar and laser sensors utilized for updating occupancy grid maps. * Sketch an algorithm for an update of the occupancy grid map using laser sensor model. * Characterize main challenges (and differences from the single robot) of the multi-robot exploration. * What improvements of simple frontier-based exploration do you know? * List at least two multi-robot exploration strategies, i.e., task allocation algorithms. * What is the main idea of the randomized sampling-based motion planning algorithm? * Briefly describe the main idea of the probabilistic roadmap based approaches. * Characterize main differences between multi-query and single-query sampling-based algorithms? * What are the requirements on the function to be called path, collision-free, and feasible? * Describe formally a feasible path planning. * Describe formally a optimal path planning. * What does it mean an algorithm is probabilistically complete? * What is the asymptotic optimality? * What are the properties of the simplified PRM algorithm? * Briefly describe main idea of the Rapidly-exploring Random Tree (RRT) algorithm. * Is the RRT optimal planning algorithm? * Is the RRT asymptotically optimal algorithm? * Describe briefly Rapidly-exploring Random Graph (RRG) algorithm. * What asymptotically optimal randomized sampling-based algorithm do you known? * What are the improved variants of the asymptotically optimal sampling-based motion planners? * What is the Multi-Goal Path Planning (MTP) problem? * What is the main difficulty of the Multi-Goal Path Planning problem to use conventional solvers for the Traveling Salesman Problem (TSP)? * Describe formally a solution to the multi-goal motion planning problem as a multi-goal path. What is required to call the solution admissible? * List main approaches for solving the multi-goal motion planning (MGMP) problem. * What is the inspection planning and how it can be addressed by a decoupled approach? * List TSP solvers you are aware of. * List two approximation algorithms for the traveling salesman problem (TSP) and provide their approximation factors? * Define formally the traveling salesman problem with neighborhoods (TSPN). * List approaches to solve the TSPN. * Characterize main differences between the traveling salesman problem (TSP) and TSP with neighborhoods (TSPN). * Describe the main idea of the modified unsupervised learning for the TSP to solve TSPN. * Describe the idea of the sampling-based decoupled solution of the TSPN. * Define formally the generalized traveling salesman problem (GTSP) * Describe briefly how to transform generalized traveling salesman problem (GTSP) to asymmetric traveling salesman problem (ATSP). * Describe the main differences between the formulations of the data collection planning as the traveling salesman problem (TSP) and orienteering problem (OP) * Define formally the orienteering problem (OP). * Define formally the orienteering problem with neighborhoods (OP). * Describe the Dubins vehicle model. * What is the optimal path connecting two states of the Dubins vehicle? * What planning problems do you know that are related to the data collection planning? * Define formally the Dubins touring problem (DTP). * Briefly describe how to solve Dubins touring problem (DTP). * How you will compute the lower-bound solution of the Dubins touring problem (DTP). * Define formally Dubins interval problem (DIP). * Define formally the Dubins traveling salesman problem (DTSP). * What are the main differences between the ordinary traveling salesman problem (TSP) and Dubins TSP (DTSP)? * List approach you know for solving Dubins traveling salesman problem (DTSP). * Briefly describe how to solve Dubins traveling salesman problem (DTSP) using decoupled approach. * Briefly describe the Dubins traveling salesman problem with neighborhoods (DTSPN). * List approaches to the Dubins traveling salesman problem with neighborhoods (DTSPN). * Define formally the Dubins orienteering problem (DOP). * What are the main differences between the orienteering problem (OP) and Dubins OP (DOP)? * What are the main differences between the Dubins orienteering problem (DOP) and DOP with neighborhoods (DOPN)? * Define formally the Dubins orienteering problem with neighborhoods(DOPN). * Explain the relation between deterministic, stochastic and adversarial environment and give one example for each. * Define a normal from game, Nash equilibrium and give an example of a game with a unique pure strategy Nash equilibrium. * Explain a strategy that guarantees capturing an evader in a continuous circular arena by an equally fast pursuer without any mobility restrictions, besides the maximal speed. * What is a differential game? Give an example. * Explain the incremental sampling-based algorithm for evading multiple pursuers in continuous perfect information setting. * What is the cop number of a graph? What is the cop number for a tree? What is the cop number for a circle? * Define a stochastic (Markov) game. * Explain value iteration for computing optimal strategy in stochastic games. * Define the art gallery problem. How many guards do we need to solve it? * Explain an algorithm to cover any polygon using n/3 guards in the art gallery problem. * Explain the double oracle algorithm for matrix games. * How many pursuers with line-of-sight visibility do we need to ensure there is no evader in a simple polygonal environment, regardless of the evader's speed? * Explain the algorithm to clear a simple polygon using a single pursuer in visibility-based pursuit evasion. * Define the resource allocation security game. * What is a leader-follower (Stackelberg equilibrium) and how it relates to Nash equilibrium? * Write a mathematical program for solving a zero-sum resource allocation game. * Describe the optimal strategy for patrolling a perimeter with homogeneous robots. * Describe, on high level, how to compute the optimal turning probability in perimeter patrolling. * Explain the semantics of constraint XY of the following mathematical program. * Explain the Monte Carlo tree search algorithm for games with simultaneous moves. ===== A list of possible topics for the exam ===== * Sketch a simple grid-based path planning algorithm * Sketch any angle modification of the A* called Theta* * Sketch the D* lite algorithm and describe how it works. * Sketch an algorithm for frontier-based exploration with the main steps. * Sketch an algorithm for incremental sampling and path searching, i.e., a single query sampling-based path planning algorithm. * Sketch an algorithm for PRM (probabilistic roadmap) construction. * Formulate path planning problem using the notion of configuration space. * What is the feasible path planning and what is the optimal path planning? Define formally. * Explain probabilistic completeness. * Explain asymptotic optimality. * Sketch the Rapidly-exploring Random Tree (RRT). * Sketch the Rapidly-exploring Random Graph (RRG). * Describe ideas of the Informed RRT* and Regionally Accelerated BIT* (RABIT*). * Define formally the Multi-Goal Motion Planning Problem * Working environment, robot, C, Cobs, Cfree, goal locations, multi-goal path is admissible. * Sketch self-organizing map (SOM) based approach for the traveling salesman problem (TSP). * Define formally the data collection planning as the prize-collecting traveling salesman problem with neighborhoods (PC-TSPN) * Sketch the Christofides's algorithm for the traveling salesman problem (TSP) and show its approximation factor. * Describe Noon-Bean transformation of the generalized traveling salesman problem (GTSP) to the asymmetric traveling salesman problem (ATSP). * Define formally the orienteering problem and orienteering problem with neighborhoods. * Define the Dubins touring problem and sketch its solution. * Define the Dubins traveling salesman problem with neighborhoods and sketch its possible solution. * What extensions of the data collection planning with Dubins vehicle to 3D do you know? * What is the cop number of a 4-connected grid? Why? * How would you design an algorithm finding an evader hiding in a building? * How would you design a camera system to protect a supermarket from thieves? * How would you design a system for supporting police units in chasing a fleeing bank robber? * How would you design a system for patrolling a perimeter with heterogeneous robots? * How would you design a system for patrolling area using multiple resources?