Topics and Questions for the Exam

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).

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?