Final 1 2018, questions PDF

Preview

Summary

Download Final 1 2018, questions PDF

Description

Final Exam “Robot Motion Planning”

Summer Term 2018 Prof. Burschka Please, provide the answers for the 3 main question sets on three separate double-sheets. Make sure to put your name and Matriculation-ID on each of the papers you return and return also sheets for not solved question sets with your name on it. Return all sheets including the empty ones.

Please, hold your personal id (Personalausweis) and student id ready for inspection during the exam.

Good luck!

: : Branch of study (Fachrichtung):

Problem 1 (Planning): a) Configuration spaces: • Explain the two methods how the robot geometry can be reduced to a point. What are the parameters of the resulting space? • Assuming that there is no slip between the wheel and the rail, draw the configuration space of a train wheel moving on a straight track. • Explain how the motion strategies used in Bug 1 and Bug 2 algorithm differ. Draw examples for both bugs showing the “difficult configurations” (cases when the algorithm is really inefficient) • Explain the difference between Euler angles and the axis-angle representation of rotations. How many degrees of freedom do they provide from the nine elements of a rotation matrix? Give the form of the basic rotation matrices around the x and around y axis? What is the disadvantage of the Euler angle representation? b) Roadmaps • Construct.(draw).a.roadmap.on.the.provided.solution.sheet.using.roadmap.methods.specified. below.the.figures.

.... ......................Voronoi. • •

• •

.

.

.

Boustraphedon.

..simplified.Visibility.Graph.

Explain.briefly.using.an.iterative.method.discussed.in.the.lecture,.how.the.Voronoi.lines.can.be. found?. Explain.the.difference.between.Boustraphedon.and.Trapezoidal.Decomposition..What.is.the. advantage.from.using.Boustraphedon.algorithm.and.how.does.it.relate.to.the.strategy,.which. separation.line.to.keep?. Explain.the.difference.to.the.generic.Visibility.Graph?.What.is.the.intuition.behind.the. reduction.of.lines.used.in.the.simplified.approach?. Explain,.what.is.a.roadmap.and.how.does.it.help.to.speed.up.path.planning?.

c) Potential.Field. • Explain and draw an example of the Potential Field planning method.. • What types of potential functions are used for the goal position and for the obstacles?. • What is the equation for the acting forces on the robot?. • What is the difference between the two situations below and how can the problem be resolved? What is the mathematical explanation for each of them? .

Problem 2 (Probabilistic Roadmaps) a) Expansiveness • Explain briefly the parameters describing the expansiveness of a given space adding for each parameter a drawing depicting how the expansiveness of a given space can be parametrized with (e,a,b)? • What important result does the expansiveness analysis provide for parametrization of a probabilistic roadmap? b) Single Query PRM • Explain with a short text and a drawing, how the sampling in single query PRMs can be improved. • Sketch, how an expected sample distribution in a rectangular region will look like with and without the improvement. • What is the application of a single query PRM? c) Multiple Query PRM •

• •

Name.and.explain.briefly.4.methods.to.improve.the.connectivity.for.multiple.query. probabilistic.roadmaps.(explain,.how.the.nodes.placement.is.calculated.in.these. examples).. Explain,.how.they.help.solving.the.problem.of.a.narrow.passages?. What are the advantages and disadvantages while using Probabilistic Roadmaps?

d) Explain.the.principle.of.the.Obstacle-Based.PRMs..Show.with.a.drawing.and.short. explanation,.how.a.boundary.of.an.obstacle.can.be.found?. e) What.are.the.expansiveness.values.for.the.following.space.(draw.the.regions.defining.the. parameters.into.the.figures)?.How.does.the.connectivity.improve.with.the.number.of.nodes.n" chosen.for.construction?.

Problem 3 (Filter): a) Explain the difference between Kalman Filter, Extended Kalman Filter and Unscented Kalman Filter? • Give the corresponding prediction and update equations. • Name and explain the method how to calculate the matrices involved in the equations. • What are the limits of applicability for usage of the above methods? b) Bayesian Filter • • • •

Explain, how to propagate a given probability distribution P(x) in a grid. What is the meaning of the expressions P( y | x ) and P( x | x ) in context of the k

k

k

k-1

Bayesian Filter? How does the update of the probability distribution work in Bayesian Filter (Give equation with a short explanation of what is done in this step for each grid cell. How can a regular Kalman Filter be implemented using the Bayesian Filter? Sketch the steps for a discrete Filter. What is the advantage in using the Kalman formulation?

c) SLAM Explain.the.data.association.step.in.the.SLAM.framework..Draw.a.figure.and.explain. with.an.equation,.how.the.decision.about.corresponding.readings.is.made.. • Which.matrix.in.the.EKF.framework.is.modified.with.the.result.of.this.calculation?.. •

d) An.Extended.Kalman.Filter.is.supposed.to.be.used.in.a.simple.non-holonomic.robot.with. two.actuated.wheels.(Fig..below)..The.system.is.controlling.the:.tangential.velocity.vt.and. rotational.velocity.w.as.control.values.in.the.Kalman.Filter..

th

l

l di t

t

The.system.is.measuring.the.local.distances.to.2.beacons.with.the.known.locations.(xi,.yi). in.the.operating.space.of.the.robot..The.robot.measures.the.radial.distance.ri.and.the. orientation.angle.relative.to.the.orientation.of.the.robot.(dashed.line).ρi • •

•

What.is.a.simple.state.vector.to.describe.the.state. of.the.system?.Explain.your. alternatives.and.the.reason.for.your.choice...Write.the.state.prediction.equation. How.can.the.correct.choice.of.measurements.for.the.convergence.of.the.system.be. validated?.Write.the.generic.form.of.the.corresponding.matrix.and.explain,.what.needs. to.be.tested?. Write.the.equation.for.the.measurement.function.h().in.dependence.on.robot.and. landmark.position.....