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.