10:00-11:45, room 105 C-5

2 groups: at 10 a.m. for those with surnames beginning with A-K, at 11 a.m. for those with
surnames beginning with L-W

1 How are kinematics of nonholonomic robots defined?

Configuration: (q0 , u(·), T) ∈ Rn × Lm [0, T ]

• q0 - is the initial configuration of the robot, a vector in n-dimensional Euclidean space

(Rn ).

• u(·) - represents the control input applied to the robot. It is a function that maps the
time interval [0, T ] to a space Lm (the set of admissible control inputs in a function
space).

• T - the total time of the motion.

Taskspace coordinates: y = (y1 , ..., yr ) ∈ Rr , where r is the dimensionality of the taskspace.
These coordinates describe the position or orientation of the robot in its environment or the
space of tasks it needs to perform.
Instantaneous kinematics in time t after applying control u(·)

y(t) = ϕq0 ,t (u(·))

It describes how the robot’s taskspace coordinates evolve over time in response to the ap-
plied control.

2 How are general, affine and driftless models of kinemat-

ics defined?
General ODE (ordinary differential equation) form of kinematic eqution:

q̇ = g(q, u,t)

, where:
• q represents the configuration of the robot

• u is the control input

• t is time

1
 • g(q, u, t) describes the dynamics of the system
Velocity(control) affine system with drift
q̇ = G(q)u + g0 (q)
• G(q) is a matrix that relates the velocity of the configuration to the control input,
making it an affine term.
• g0 (q) represents a drift term, which is a vector that captures any additional motion or
behavior not directly dependent on the control input.
Driftless system:
q̇ = G(q)u
The driftless system simplifies the model by excluding the drift term, considering only the
relationship between the configuration’s velocity and the control input

3 What are standard models of wheeled robots?

Robots with one wheel:
(a) unicycle
Robots with two wheels:
(a) bicycle-type,
(b) inverted-pendulum-type

2
Robots with three wheels:

(a) two-wheel differential drive with passive caster wheel,

(b) synchronous drive,

(c) omnimobile robot with Swedish wheels (mecanum),

(d) omnimobile robot with active caster wheels,

(e) omnidirectional robot with active steerable wheels

Robots with four wheels:

(a) car-like structure

Special Applications of wheeled robots:

(a) Articulated robots — robot with a trailer

(b) Hybrid robots — example: wheels and tracks

3
4 What are definitions of fundamental concepts in proba-
bility?
4.1 Axioms

0 ≤ P(X) ≤ 1 (1)
P(True) = 1 (2)
P(False) = 0 (3)
P(X ∪Y ) = P(X) + P(Y ) − P(X ∩Y ) (4)

0 ≤ P(X) ≤ 1 (Non-negativity): The probability of any event X is between 0 and 1, inclu-

sive.
P(X ∪ Y ) = P(X) + P(Y ) − P(X ∩ Y ) (Additivity): The probability of the union of two
events is the sum of their individual probabilities, minus the probability of their intersec-
tion.

4.2 Discrete random variables

X is a random variable with values from {x1 , x2 , ..., xn } (5)

P(X = xi ) denotes a probability that the variable X has the value xi (6)

4.3 Continuous random variables

X is a random variable with values in R (7)

P(X = x) or P(x) denotes probability density in x (8)

4.4 Expectation

E[X] = ∑ xp(x) — case for discrete random variable (9)

x
Z
E[X] = xp(x)dx — case for continuous random variable (10)

4
4.5 Entropy
Entropy is a scientific concept that is most commonly associated with a state of disorder,
randomness, or uncertainty.

H p (x) = E[−log2 p(x)] (11)

H p (x) = − ∑ p(x)log2 p(x) (12)
x
Z
H p (x) = − p(x)log2 p(x)dx (13)

4.6 Conditional probability

• joint distribution — p(x, y) = p(X = x ∧Y = y)

• if X and Y are independent p(x, y) = p(x)p(y)

• conditional probability p(x|y) is a probability that X = x if Y = y

• p(x, y) = p(x|y)p(y)

• if X and Y are independent: p(x|y) = p(x)

• theorem of total probability:

p(x) = ∑ p(x|y)p(y) (14)

y
Z
p(x) = p(x|y)p(y)dy (15)

4.7 Bayes rule

P(B|A)P(A)
P(A|B) = (16)
P(B)

5
5 How are normal distributions defined and parameter-
ized?
The general form of density function for normal distribution is:
1 1 x−µ 2
f (x) = √ exp{− ( ) } (17)
σ 2π 2 σ
where
σ — standard deviation (σ2 — variance)
µ — mean/expected value

N (µ, Σ) — multidimensional normal distribution with mean µ and covariance Σ

1 1
N ∼ P(X) = p exp{− (x − µ)T Σ−1 (x − µ)} (18)
(2π)n det Σ 2
canonical parametrization:
Ω = Σ−1 — information matrix Ω
ξ = Σ−1 µ — information vector ξ

6 What are properties of transformations of normally dis-

tributed random variables?
Gaussian probability distribution function transformations:

• linear (Y = AX + B):

if
P(X) = N (µ, Σ)
then
P(Y ) = N (Aµ + B, AΣAT ) (19)

If P(X) = N (µ, Σ) is a multivariate normal distribution, and Y = AX + BY is a linear

transformation, where A is a matrix and B is a vector, then the resulting distribution
of Y is also a multivariate normal distribution P(Y ) = N (Aµ + B, AΣAT )

6
 • sum (Y = X1 + X2 ):

if
P(X1 ) = N (µ1 , Σ1 )
P(X2 ) = N (µ2 , Σ2 )
then
P(Y ) = N (µ1 + µ2 , Σ1 + Σ2 ) (20)

If X1 and X2 are independent normally distributed random variables with means µ1

and µ2 , and covariance matrices Σ1 and Σ2 , then the sum Y = X1 + X2 is also normally
distributed P(Y ) = N (µ1 + µ2 , Σ1 + Σ2 )
• product

P(X1 )P(X2 ) = N (µ1 , Σ1 )N (µ2 , Σ2 ) = N (µY , ΣY ) (21)

where
ΣY = (Σ−1 −1 −1
1 + Σ2 )
µY = ΣY Σ−1 −1
1 µ1 + ΣY Σ2 µ2

If X1 and X2 are independent normally distributed random variables with meansµ1

and µ2 , and covariance matrices Σ1 and Σ2 , then the product Y = X1 · X2 is also
normally distributed P(Y ) = N(µY , ΣY )

7 What are Markov processes and what tasks and algo-

rithms are related to them?
A stochastic process over countable state space, in which the current state depends only
from its previous state and probabilities of transfer are constant over the time.

p(Xk+1 |XK Xk−1 ...X1 X0 ) = p(Xk+1 |Xk ) (22)

a process without memory.

• Markov chain - it is a specific type of Markov process where the state space is dis-
crete, and the transitions between states are governed by fixed probabilities.
• Hidden Markov Model (HMM)
Markov process in which the state chain cannot be observed directly, but through an
output function.

7
 • Markov decision process (MDP)
Markov chain with added controls (actions) – a new state depends on a pair (old state,
action).
• Partially observable Markov decision process (POMDP)
MDP with hidden states

8 What is a difference between incremental and absolute

localization?
Incremental:
• use internal robot data
• between consecutive moments in time may be small, but due to the nature of the
method, errors accumulate in subsequently.
Absolute:
• use external data
• the error doesn’t accumulate and remains constant over time
The key distinction lies in the source of information. Incremental localization relies on
internal data generated by the robot itself, while absolute localization incorporates external
data sources for position estimation.
Incremental localization methods are prone to error accumulation over time due to the
integration of small errors at each step. In contrast, absolute localization tends to have
more consistent errors that do not accumulate over time, assuming the accuracy of the
external data source remains constant.

9 What is the procedure of odometry based localization?

1. odometry data collection - position and orientation, sometimes linear velocity and
angular velocity
2. update pose estimation - based on the collected odometry data the robot’s updated
pose is estimated (most often position(X,Y) and orientation (θ).
3. error accumulation - small inaccuracies in the odometry data such as wheel slippage
or sensor noise, can lead to errors in the pose estimation. As the robot moves, these
errors accumulate, and the actual position may diverge from the estimated position.

8
To minimize influence of the drift, additional localization methods or sensor fusion tech-
niques, such as incorporating external sensor data (e.g., GPS, visual odometry), may be
used to correct and refine the pose estimation.

10 What are the methods of absolute robot positioning?

• deterministic:

– trilateration – measurement of distances to markers,

* requires at least three reference points with known positions,
* the robot’s position is determined by intersecting spheres centered on each
reference point with radii equal to the measured distances.
– triangulation – measurement of angles between markers,
* requires at least two reference points with known positions,
* the robot’s position is determined by intersecting lines or angles formed by
the reference points and the robot’s location.
• stochastic:

– multilateration – differences between distances to markers

* requires at least three reference points with known positions
* the robot’s position is determined by considering the differences in dis-
tances to each reference point
– multriangulation – angle of received signal (most often)
* requires at least two reference points with known positions,
* the robot’s position is estimated based on the angles of arrival of signals
from the reference points

11 What is sensor fusion?

Sensor fusion is the process of integrating data from multiple sensors and related informa-
tion to obtain information of better quality than by use of any single sensor.
Types of fusion:
• direct (sensor fusion) — only sensor data is used

• indirect (information fusion) — sensor information is complemented with additional

knowledge (prior knowledge or additional data)

9
The primary goal of sensor fusion is to enhance the quality and accuracy of the informa-
tion obtained. By combining data from multiple sensors, the system can compensate for
limitations and errors associated with individual sensors. This leads to a more reliable and
comprehensive understanding of the surroundings.
Example: By combining data from lidar, cameras and GPS it is possible to improve the
autonomous mobile robot perception and decision-making capabilities.

12 How do general Bayes filters operate?

Data filtering — sequential process of updating the probabilistic model of the state of the
system, varying with time and taking into account periodic observations received from
sensors.
P(xk |Z k ,U k , x0 )
Bayes filters operate as Two-Step Filtering Process:
1. update based on previous belief - estimate the system’s state based on its previous
state and the applied control inputs. This step predicts where the system is expected
to be without considering current sensor readings.

2. correction with current measurements - adjust the predicted state using the most re-
cent sensor measurements. This step corrects the estimate, aligning it with the actual
data obtained from sensors.

parameters: xt−1 , ut , zt . output: xt

13 What are the assumptions and properties of KF?

Applicable to continuous linear systems. At time t probability of X is estimated by N (µt , ∑t ).
It is assumed that Markov conditions are fulfilled and

10
 1. transfer function is linear with Gaussian noise

xt = At xt−1 + Bt ut + εt , εt → N (0, RT )

2. output function is also linear with Gaussian noise

zt = Ct xt + δt , δt → N (0, ∑)
0

3. initial probability is Gaussian

p(x0 ) = N (µ0 , ∑)
0

Then one can prove that posterior distribution is Gaussian.

Steps:
1. prediction of a new state after control ut

2. Kalman gain calculation

3. Resulting state

13.1 Chat:
Assumptions:
1. the system is assumed to be linear

2. the system is either known or accurately approximated

3. the system is assumed to have Markov property

4. perturbations affecting both the system dynamics and the sensor measurements are
Gaussian and white
Properties:
1. KF provides the best linear unbiased estimate (BLUE) of the true state of the system

2. KF updates the state estimate recursively and doesn’t need to store the entire history
of measurements

3. KF minimizes the mean square error of the state estimate

4. KF operates in two steps — prediction and update

11
14 What is EKF and how it differs from KF?
The Extended Kalman Filter (EKF) is an extension of the Kalman Filter designed to handle
nonlinear system models and measurement equations. It linearizes the system dynamics
and measurement equations around the current estimate of the state, allowing it to apply
the standard Kalman Filter algorithm.

xt = g(ut , xt−1 ) + εt , zt = h(xt ) + δt

KF EKF
state prediction At µt−1 + Bt ut g(ut , µt−1 )
measurement prediction Ct µt h(µt )
∂g(ut ,xt−1 )
state matrix (lin.) At ∂xt−1
h(∂xt )
output matrix (lin.) CT ∂xt

Table 1: KF vs EKF

15 What are inputs and outputs of probabilistic localiza-

tion? What are they in mapping?
15.1 Probabilistic Localization
15.1.1 Inputs:

bel(xt−1 ) - Prior belief or probability distribution over the robot’s state at time t − 1.
ut - Control input or action taken by the robot at time t.
zt - Observation or sensor measurement received by the robot at time t.
m - Map of the environment.

15.1.2 Prediction Phase:

In the prediction phase, the goal is to estimate the expected probability distribution of the
new state xt given the control input and the prior belief. This involves predicting where the
robot is expected to be after taking the given action.

12
15.1.3 Correction Phase:
In the correction phase, the estimate is updated based on the observation zt . The observed
data from sensors is incorporated to adjust the predicted state, resulting in a more accurate
belief about the robot’s state.

15.1.4 Outputs:
bel(xt ) - Posterior belief or probability distribution over the robot’s state at time t. This
represents the refined estimate after combining the prediction and correction phases.

15.2 Mapping:
For mapping, the primary goal is to create or update a map of the environment based on the
robot’s sensor measurements.

15.2.1 Inputs:

xt - Robot pose at time t.

zt - Observation or sensor measurement received by the robot at time t.
mt−1 - Map of the environment at time t-1.

15.2.2 Outputs:
m - updated map The mapping process involves incorporating new sensor measurements to
improve and refine the map of the environment.

16 How EKF is used in probabilistic localization?

The EKF (Extended Kalman Filter) is used solely for position correction, assuming that
inaccuracies are small.
Assumptions:

• belief (bel) are represented by moments: (µt , ∑t )

• map is represented by a collection of features zt = {zt1 , zt2 , ...}

• the features are identifiable by a correspondence ct = {ct1 , ct2 , ...}

Properties:

13
 • Gaussian is unimodal – suitable for position tracking and cases when the approximate
pose may be restricted to a small region

• It does not allow hard constraints (like walls)

• Linearization is usually valid only close to the real pose

• It does not interpret negative information (missing features)

Example: Imagine a robot starting in the corner of a room. It predicts it will move forward,
but it has uncertainty in its movement. As it moves, it takes a measurement of a known
object, like a chair. The EKF combines this measurement with its prediction to refine its
estimate. The robot repeats this process as it explores the room, continuously updating its
position based on movement and sensor observations.

17 What types of maps are used in robotics?

17.1 Map taxonomy:
1. Steadiness:

• static - Features in the environment do not change over time.

• semi-static - Some features may change occasionally.
• dynamic - Features in the environment change frequently.

2. Structure:

• metric - Represents the exact geometric information of the environment, often

in a coordinate system.
• topological - Focuses on the connectivity and relationships between places or
landmarks, ignoring precise geometric details.
• hybrid - Combines both metric and topological aspects, offering a more com-
prehensive representation.

3. Representation of distances:

• grid - Represented in a grid-like structure, suitable for metric maps.

• vector - Uses vectors to represent relationships between places, more common
in topological maps.

14
17.2 Comparison of topological and metric maps
Grid metric map:
• ease of creation, representation, updates

• recognition independent of robot pose

• optimization of path lengths possible

Topological map:
• complexity dependant on region, not its size

• high precision of robot localization is not necessary

• simpler high level processing

18 How to build an occupancy grid map?

Searching for a (static) map to maximize probability:

p(m|z1:t , x1:t )

Divide a map into cells m= mi , each one marked with occupancy probability (1 - occupied,
0 - empty).
Assume independence of map cells and calculate each cell separately. Map is updated with
binary Bayes filter.
Representation of cell value:
1. probability p(x) ∈ [0, 1]

2. logarithmic l(x) ∈ (− inf, + inf)

p(x) p(x)
l(x) = log = log
p(¬x) 1 − p(x)
with probabilities recovered by
1
p(x) = 1 −
1 + exp{l(x)}

3. hit/misses (h(x), f(x))

How to Build an Occupancy Grid Map:

15
 1. Objective:
Maximize the probability p(m|z1:t , x1:t ) to create a static map.

2. Grid Division:
Divide the map into cells m = mi , each marked with an occupancy probability (1 for
occupied, 0 for empty).

3. Independence Assumption:
Assume independence of map cells, allowing the calculation of each cell’s probabil-
ity separately.

4. Binary Bayes Filter:

Update the map using a binary Bayes filter, where each cell’s occupancy is updated
based on observed sensor data.

5. Representation of Cell Values:

- Probability (p(x) ∈ [0, 1]).
p(x)
- Logarithmic value l(x) ∈ (− inf, + inf) given by l(x) = log 1−p(x) .
1
- Probability recovery from logarithmic values: p(x) = 1 − 1+exp{l(x)} .

6. Hit/Misses Representation:
Hit/miss observations ((h(x), f (x))) represent confirmation of occupancy and empti-
ness, respectively.
- Hit (Occupied): Observation confirming occupancy.
- Miss (Empty): Observation indicating emptiness.

19 What is definition of SLAM?

Simultaneous localization and mapping (SLAM) is the computational problem of con-
structing or updating a map of an unknown environment while simultaneously keeping
track of an agent’s location within it.

19.1 Definition of task

Based on known control U= u1:t and observations Z = z1:t determine both robot state or
path (x1:t ) and model of environment (map) m.

16
20 What are the main approaches to SLAM problem?
• online SLAM - estimating posterior of current pose

p(xt , m|z1:t , u1:t )

• full SLAM - estimating posterior of whole path

p(x1:t , m|z1:t , u1:t )

• Filter-Based Approaches:

– Extended Kalman Filter (EKF) SLAM:

Utilizes Gaussian distributions and linearizes the system dynamics. Suited for
small to moderately-sized environments with relatively simple dynamics. Ap-
plicable for both online SLAM and full SLAM estimations.
– Unscented Kalman Filter (UKF) SLAM:
Addresses issues related to linearization using a set of sigma points. Suitable for
scenarios with nonlinearities and non-Gaussian distributions. Can be employed
for both online SLAM and full SLAM.
– Particle Filter (Monte Carlo) SLAM:
Represents belief using particles for handling non-Gaussian distributions. Ef-
fective in large-scale, complex environments. Applicable for both online SLAM
and full SLAM.

• Graph-Based Approaches:

– Pose Graph SLAM:

Models the SLAM problem as a graph, optimizing the entire trajectory for
global consistency. Primarily used for full SLAM, estimating the posterior of
the entire path.

• Direct Methods:

– Visual-Inertial SLAM: Integrates visual information with inertial sensor data

for improved accuracy.

21 How is EKF-based SLAM implemented?

• the earliest method (and of the highest influence)

17
 • assumes metric map representation with distinct features included in parameter space
vector.

• robot pose and features coordinates are described by a random variable with Gaussian
distribution
p(xt , m|ZT ,UY ) ∼ N(µt , ∑)
t

µt - mean state and features coordinates ∑t - covariance matrix for µt

21.1 List Step

1. System Modeling: Describe robot state and motion model. Define how sensor mea-
surements relate to the state.

2. Initialization: Set initial estimates for the robot’s pose and landmark positions.

3. Prediction (Motion Update): Use motion model to predict the next state. Adjust
state covariance based on the prediction.

4. Landmark Prediction: For each observed landmark, predict expected measure-

ments.

5. Update (Measurement Update): Obtain actual sensor measurements. Update state

using Kalman Gain and measurement difference.

6. Loop: Repeat steps 3-5 for each time step.

7. State Augmentation: Add new landmarks to the state if observed.

8. Termination: Continue for a set number of steps or until convergence.

22 How does particle filter operate?

Most popular: FastSLAM
parallel tracking of K particles, each on its own path

• new poses of particles are calculated using odometry and assumed noise distribution
[k] [k]
xt ∼ p(xt |xt−1 , ut ) (23)

18
 • with new observation importance weights are calculated based on probability of mea-
surement of n in given pose
[k]
[k] [k] [k]
wt = N(zt |xt , µt,n , ∑)
t,n

next, set of particles is resampled with new probability distribution defined by nor-
malized wi .

Particle Filter adapts to uncertainty, adjusting particles based on motion and sensor data,
providing a probabilistic estimate of the robot’s pose and mapping the environment.

23 How does task planning differ from motion planning?

Task planning:

• collect information

• determine current and target state

• analyze possible solutions

• make a decision

Motion planning:

• lower level of abstraction (physical movement and trajectories)

• required to execute specific task

• generate a detailed path or set of motions for robot’s accuracy

• kinematics aspects of the robot’s movement, considering obstacle and constrains the
enviromental

Task planning involves deciding what needs to be done and the general approach at a high
level. Motion planning, at a lower level, turns this plan into specific, detailed robot move-
ments. It considers the robot’s mechanics, navigates around obstacles, and ensures precise,
obstacle-aware movements. Both planning levels are crucial for successful robotic tasks,
with task planning setting the strategy and motion planning handling the tactical details.

19
24 How are actions defined in the predicate logic?
(not finished)
Paradigm shift:
Instead of describing sequences of events or predefined strategies, defining the available
actions and goals Goal Oriented Action Planning (GOAP)

• + large spectrum of possible behavior sequences that can be generated

• + ease of managing behavior rules

• + generation of different behaviors when requirements change without changing the

sequence by the user

• - he need to solve complex planning problems (often in real time)

24.1 STRIPS — actions

initial conditions — literals describing the conditions that must be met to be able to activate
the action
result — literals describing the state after the execution of the action

24.2 PDDL — actions

example:
(: action go
: parameters (?r ?from ?to)
: precondition (and (in ?r ?from)
(or (beside ?from ?to) (beside ?to ?from)) )
: effect (in ?r ?to)
)

25 How is description defined in PDDL?

(not finished)

1. Syntax similar to programming languages

2. Enable description by STRIPS, ADL and others

3. Allows the use of universal planners

20
 4. Prefix notation

(beside a b)
(not (beside a b))
(and (beside a b) (beside b c))
(beside ?x ?y)

PDDL - components:

1. Domain :

• states (:predicates ) - limitations of the problem

• actions (:action ) - what are available operations

2. Task:

• objects (:objects ) - list of objects that create our ”world”

• initial state (:init ) - initial conditions and correlation to the objects
• objective (:goal ) - what we want to achieve

21