Navigation

- B4M36UIR
- Classification
- Tasks
- support
- T1a-ctrl - Open-loop locomotion control
- T1b-react - Reactive obstacle avoidance
- T1c-map - Map building
- T1d-plan - Grid-based path planning
- T1e-expl - Robotic information gathering - mobile robot exploration
- T1x-dstar - Incremental path planning (D* Lite)
- T2a-tspn - Data-collection Path Planning with Remote Sensing (TSPN)
- T2b-dtspn - Data collection path planning with curvature-constrained trajectory - Dubins TSPN
- T3a-sampl - Randomized sampling-based algorithms - Probabilistic Roadmap
- T3b-rrt - Randomized sampling-based algorithms - Rapidly-exploring Random Trees (RRT)
- T4a-greedy - Greedy policy in pursuit-evasion
- T4b-mcts - Monte-Carlo Tree Search policy in pursuit-evasion
- T4c-vi - Value-iteration policy in pursuit-evasion
- T4d - Patrolling in polygonal environment

- Laboratory Exercises
- Lab01 - Introduction to CoppeliaSim/V-REP and Open-Loop Robot Locomotion Control
- Lab02 - Exteroceptive sensing: Reactive-based Obstacle Avoidance and Map Building
- Lab03 - Grid and Graph based Path Planning
- Lab04 - Incremental Path Planning
- Lab05 - Mobile Robot Exploration
- Lab06 - Mobile Robot Exploration
- Lab07 - Multi-goal Planning, Data Collection Path Planning
- Lab08 - Curvature-constrained Data Collection Path Planning ((D)TSPN)
- Lab09 - Randomized Sampling-based Algorithms
- Lab10 - Asymptotically Optimal Randomized Sampling-based Algorithms
- Lab11 - Game Theory in Robotics - Task Explanation - Greedy policy, Patrolling
- Lab12 - Game Theory in Robotics - Task Explanation - MCTS, Value Iteration
- Lab13 - Game Theory in Robotics - Area patrolling, Polygon ilumination, Gap edges algorithm, Double Oracle

- Lectures
- Project
- For students
- Lectures Records
- Lecture 01 - Course information, introduction to robotics
- Lecture 02 - Robotic paradigms and control architectures
- Lecture 03 - Path planning - Grid and graph-based path planning methods
- Lecture 04 - Robotic information gathering - Mobile robot exploration
- Lecture 05 - Multi-goal Planning
- Lecture 06 - Data Collection Planning
- Lecture 07 - Curvature-Constrained Data Collection Planning
- Lecture 08 - Randomized Sampling-based Motion Planning Methods

- Topics and Questions for the Exam
- Distant form of teaching

- Lectures Records
- Tutorials

All courses

- Winter 2020 / 2021
- Summer 2019 / 2020
- Winter 2019 / 2020
- Summer 2018 / 2019
- Winter 2018 / 2019
- Summer 2017 / 2018
- Older

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

- 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/b4m36uir/resources/exam_topics.txt ยท Last modified: 2019/09/19 13:31 (external edit)