2.6: Collision Detection and Freespace Sampling Methods

Loading...

Do curso por University of Pennsylvania

Robotics: Computational Motion Planning

655 classificações

University of Pennsylvania

Robotics: Computational Motion Planning

655 classificações

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

[INAUDIBLE] obstacles are really convenient to work with, because

they provide an explicit description of the configure space obstacles.

Often times, we don't have this luxury and

the obstacles are instead defined implicitely through a collision function.

More specifically, if we let x denote the coordinates of a point in configuration

space, we're usually able to define a function, let's call it CollisionCheck,

that returns zero if the configuration is in freespace, and one otherwise.

In this slide, we show a situation where our putitive robot,

the red polygon, is entirely in freespace.

So we want our CollisionCheck function to return a zero.

In this next case, the robot is colliding with one of the obstacles.

So we would want our CollisionCheck function to return a one for

this configuration.

Collision detection is a key subroutine for most path planning algorithms, and

it often boils down to computing the answer to some basic geometric questions.

Lets go back and consider our example.

Here we can imagine representing both our robot and

our obstacle as collections of triangles, as shown in this figure.

Deciding whether the robot and

the obstacle intersect is now a matter of determining whether

any of the robot's triangles overlap any of the obstacle's triangles.

Here we can make use of the fact that triangles are convex polygons.

In this circumstance, it means that we can test where the two triangles intersect

by checking all of the sides on both triangles, and testing whether any of

those sides act as separating lines, where all of the points from one triangle lie

on one side of the line, and all of those from the other lie on the opposite side.

If you can find such a separating edge, among the six edges among

the two triangles, you have proved that the triangles don't intersect.

If not, you can conclude that they do.

This idea of finding a separating line, or

plane, actually generalizes to higher dimensions.

For instance, If you have a robot composed of convex polygons in three dimensions

like boxes or pyramids.

You can check for collision by testing if any of the faces on one of

the polygons acts as a separating hyperplane.

In the cases that we've considered so far, the robots and

the obstacles are basically composed of simple polygons.

So to test for collision,

we first transform the robot according to the configurations space parameters and

then test for collision between the robot's components and the obstacles.

In this case, this amounts to testing whether any of the red triangles

overlap any of the black triangles.

In this case we would want our CollisionCheck function to return a zero,

indicating that no intersections are found.

In this next case, there are in fact red triangles that do overlap

the black triangles so our CollisionCheck function should return a one.

Another question that we may be interested in answering is whether all of

the points along the line segment between two configuration space points x1 and

x2 are in freespace.

Sometimes we're lucky and

we can actually answer that question definitively by analysis.

In practice, if two points are both in freespace, and

they are close enough to each other, given some reasonable distance metric,

then we tend to assume that a straight line path between them is collision free.

This can obviously go horribly wrong if we're not careful.

But let's live dangerously for a second.

In considering our 2D planning problem,

we can proceed by sampling a grid of locations in the configuration space.

For each grid point we determine whether or

not it is in freespace using our CollisionCheck function.

All the grid points that are in freespace are going to be treated as

nodes in our graph.

This figure shows the resulting sampled freespace points.

in this example, we're going to go ahead and assume that if two adjacent grid

points are both in freespace, then all the points between them are also in freespace.

And we connect them by an etch, as shown here.

In this case, we've chosen matters so

that the start and end points are both nodes in the graph.

We can then employ anyone of our usual suite of graph-based planning tools

to search for a path between the two nodes.

The resulting path through the graph is shown here, in red.

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