2.4: Visibility Graph

Loading...

Do curso por University of Pennsylvania

Robotics: Computational Motion Planning

626 ratings

University of Pennsylvania

Robotics: Computational Motion Planning

626 ratings

Curso 2 de 6 em Specialization Robotics

Robotic systems typically include three components: a mechanism which is capable of exerting forces and torques on the environment, a perception system for sensing the world and a decision and control system which modulates the robot's behavior to achieve the desired ends. In this course we will consider the problem of how a robot decides what to do to achieve its goals. This problem is often referred to as Motion Planning and it has been formulated in various ways to model different situations. You will learn some of the most common approaches to addressing this problem including graph-based methods, randomized planners and artificial potential fields. Throughout the course, we will discuss the aspects of the problem that make planning challenging.

Na lição

Configuration Space

Welcome to Week 2! In this module, we begin by introducing the concept of configuration space which is a mathematical tool that we use to think about the set of positions that our robot can attain. We then discuss the notion of configuration space obstacles which are regions in configuration space that the robot cannot take on because of obstacles or other impediments. This formulation allows us to think about path planning problems in terms of constructing trajectories for a point through configuration space. We also describe a few approaches that can be used to discretize the continuous configuration space into graphs so that we can apply graph-based tools to solve our motion planning problems.

2.4: Visibility Graph3:14

2.5: Trapezoidal Decomposition1:22

2.6: Collision Detection and Freespace Sampling Methods4:49

Conheça os instrutores

CJ Taylor
Professor of Computer and Information Science
School of Engineering and Applied Science

Now that we have a conceptual framework for thinking about a wide range of motion

planning problems, in terms of planning trajectories to configuration space,

we can talk about various approaches to solving this problem.

Specifically, in the next few sections I'm going to talk about three approaches,

all of which have a common theme.

Namely, they start with the motion planning problem framed on a continuous

configuration space and then use various approaches to reformulate this problem

in terms of a graph, so that we can apply the kinds of algorithms we discussed

earlier like Grassfire, Dijkstra, and Astock.

We could illustrate these approaches using the 2D planing program

depicted on the following slide.

As usual, our goal is to come up with a trajectory

from the starting two deconfiguration to the ending configuration.

In this case, the configuration space obstacles are modeled as polygons,

which suggests the following discretization.

We associate a node with every configuration space optical vertex,

as shown here.

Then, we compute what is known as a visibility graph.

More specifically, we draw an edge between any two vertices that

can be connected by a straight line that lies entirely in free space.

Note that this includes every pair of

neighboring vertices on the same configuration space obstacle.

In order to be able to run this algorithm, we need to be able to determine whether

a line segment between any two points intersects a configuration space obstacle.

In the situation shown here, where the configuration

space obstacles are polygons, this is actually relatively straightforward.

We also include the start and end points as nodes in our graph.

Once we've done this, we're back to original planning problem we considered

earlier, where our goal is to construct the shortest path through the graph

between the start node and the end node.

A problem that can be readily solved using Dijkstra's algorithm.

Here is a result of finding the shortest path in our example.

This visibility graph algorithm is actually complete.

That is, it will find a path if one exists and

report failure if no path can be constructed.

This could happen if the start position or

end position was entirely surrounded by an obstacle.

Moreover, you can prove that this visibility algorithm

are actually construct the shortest possible path between the two points.

You can see the intuition for

this by thinking of the path between the two vertices as a piece of string.

Imagine what would happen if you pull this string as tight as possible

to eliminate all of the slack.

The resulting trajectory would consist of a series of straight lines

between vertices corresponding exactly to the edges of the visibility graph

However, we can debate whether it's a great idea for

our trajectory to clip the obstacles so closely.

In practice,

we may want to pretend that the robot is actually a bit bigger than it truly is.

This would inflate the configuration space obstacles by a safety margin.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play