Hadas-MP 1

<u style="display: none;">... no changes ... no changes ... no changes ... no changes ... no changes ... no changes ... no changes ... no changes ... no changes ... no changes ... no changes ... <a href='http://www.insurance-top.com'>car insurance</a> : [http://www.insurance-top.com auto insurance] - [HTTP://www.insurance-top.com auto insurance] : [Insurance car|http://www.insurance-top.com] - [Insurance car|HTTP://www.insurance-top.com] : http://www.insurance-top.com/auto/ : http://www.insurance-top.com insurance quote : home insurance : "cars insurance" http://www.insurance-top.com : [http://www.insurance-top.com|insurance auto] </u>!! Collision Detection

This matlab program computes whether a robot, described as a single, possibly nonconvex polygon, collides with any of the obstacles in the environment, also described as polygons.

Usage:collision_chk(robot,robot_noncnvx,tran_rot,obs_cell,obs_noncnvx)

Where :

robot=

(2 x no. of vertices ) matrix defining the vertices of the robot - can be nonconvex. vertices are to be specified in clock/counter-clock wise order.

robot_noncnvx =

1 if robot is nonconvex. otherwise 0

tran_rot =

structure of [x,y,theta in radians] - defines translation and rotation of the robot. If you set this as [] (empty vector), the program generates a random movement.

obs_cell =

A vector cell array where each entry contains a matrix defining vertices of the obstacles can be nonconvex. Vertices are to be specified in clock/counter-clock wise order.

obs_noncnvx =

no. of obstacles vector with 1 in the ith place if the ith obstacle is nonconvex, otherwise 0.

Method and resultsWhen two polygons collide, it means that there is at least one point that belongs to both polygons. Using optimization tools, we check to see whether such a point exist, and if it does, then a collision occured. This program detects a collision in the following way:

  1. The robot is centered around the origin.
  2. The robot polygon is Rotated by theta, Translated along x and Translated along y.
  3. All nonconvex polygons (robot and/or obstacles) are triangulated (we need convex polygons for the optimization algorithms).
  4. The robot convex polygon(s) are defined as a set of vertices. Using these vertices, each edge of the polygon is transformed into a linear constraint Axeq b such that a point inside the polygon satisfies all of the edge constraints.
  5. The obstacle polygons induce another set of linear constraints.
  6. A linear program is solved for each robot-obstacle pair, using their constraints. If there is a feasable solution, then a collision occured and the program exits with the message:"A Collision was detected !". If all of the linear programs were infeasable, then the program displays:"No collision was detected".

Other than the message, a plot is displayed where the (moved) robot is in red and the obstacles are in blue.

Examplerobot = [1 1 3 3 2; 1 3 3 1 2]; obs_cell = {[1 1 3 2 3;3 4 4 3.5 3] [-3 -3 0 0 -1 -1 2; -1 1 1 -2 -2 0]}; tran_rot.x = -1;tran_rot.y = -1;tran_rot.theta = pi;

The result of collision_chk(robot,1,tran_rot,obs_cell,[1 1]):

> A Collision was detected !

The code:collision_chk

Back to Hadas Kress-Gazit