Warning
This page is located in archive.

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?
courses/xep36uir/resources/exam_topics.txt · Last modified: 2019/09/19 13:31 (external edit)