Computational Geometry and Robot Motion Planning

Lecture Notes for Introduction to Computational Geometry (Com S 418/518) Yan-Bin Jia, Iowa State University Robot Motion Planning Outline: I. Configuration and degrees of freedom II. Configuration space (C-space) III. Planning of a collision-free path Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.

I. The Planning Problem Static environment: 2-dimensional (2D) Polygonal robot ?4 with polygonal obstacles ?5 start ? = {?1,?2, ,??} ?3 goal ?1 Task: Move the robot from the start placement to the goal placement without colliding with any obstacles. ?2

Reference Point The robot as a polygon ?. How to represent its placement, or configuration? ? Pick a reference point (usually in the interior of ?). ?(0,0) ? No rotation reference point The robot can only translate. ?(3, 2) ?(?,?): the robot placement with its reference point at (?,?). It has only two degrees of freedom (2 DOFs): ? and ?.

Configuration With rotation The robot can additionally change its orientation around the reference point. ? 3,2,? 4 ? Need to specify the rotation angle ?. reference edge ?(?,?,?): the robot placed at (?,?) with orientation ?. ?(0,0,0) 3 DOFs: ?,?,? Configuration could also include the robot s velocity and angular velocity. Pose refers to position and orientation only.

Degrees of Freedom Number of independentparameters that define the configuration of an object. 2 DOFs: (?,?) point line 2 DOFs: (?,?) ?:orientation ? translation in the direction of the line does not change its configuration. ? ?: signed distance of translation in the perpendicular direction line segment 3 DOFs: (?,?,?) translation along the segment changes its configuration. ? (?,?)

DOF (contd) DOFs for a robot as one rigid body: 2D 3D (?,?,?) (?,?) translation (?,?,?) (?,?,?,?,?,?) translation & rotation rotation angles about stationary ?,?,? axes, or three Euler angles: roll, pitch, and yaw (Com S 477/577, Fall 2024)

Serial Manipulators 2-DOF manipulator: (?1,?2) ?4 ?3 4-DOF WAM Arm + 3-DOF BarretHand (both from Barret Technology, Inc.) ?1 ?2

Shadow Hand Anthropomorphic 24 joints. 20 DOFs almost like the human hand! Image: Shadow Robot Company

II. Configuration Space (C-space) Work space ?: 2D environment Configuration space ?(?): parameter space of the robot ? in ? C-space: 2 [0,2?) translation + rotation From the C-space to the workspace: ?(?) ? (?,?,?) ?(?) placement

Point in the C-space A polygonal robot is represented as a point in the C-space. ? 0,0,0 ? 0, 2, ? 4 ? 4

Collision and Forbidden Configuration A configuration (?,?,?) is forbidden if the placement ?(?,?,?) collides with an obstacle. Otherwise, it is free. set of obstacles Forbidden C-space ?????(?,?): the set of forbidden configurations Free C-space ?????(?,?): the set of free configurations ?????(?,?) ?????(?,?) = ?(?) ??????,? ??????,? =

C-obstacle for a Translating Robot Robot Obstacle C-obstacle ?3-?1 ?4-?1 ?1 ?1 ?1 ?5 ?2 ?1 ?3 ?5 ?2 ?3 ? ?4 ?4 ?4-?2 ?3-?3 ?3 ?2-?3 ?2 ?3 ?5-?2 ?2 ?1-?2 ?1-?3 ? C-obstacle ?(?): ? ? ?(?) and ?(?) ? } ??????,? = ?(?) collision ? ?

Path C-space: Work space: point curve robot C-obstacles (possibly joined) obstacle path overlapping C-obstacles

Point Robot Work space = C-space & every obstacle = its C-obstacle Obstacles ?1,?2, ,?? have disjoint interiors. Bounding box ? contains all obstacles. ? ?????= ? ?? ?=1 Also the free work space. Possibly disconnected. ?

?????as a Trapezoidal Map Remove trapezoids lying inside the obstacles ?(?????) A trapezoid is removed if its top edge bounds an obstacle from above. ?(?log?) expected time.

III. Roadmap A planar graph embedded in ????? and formed by adding one node in the center of each trapezoid; one node in the middle of each extension; an arc between two nodes if one is in the center of a trapezoid while the other is on the boundary. The roadmap is constructed by traversing the DCEL of ?(?????).

Roadmap Construction Traverse the DCEL of the trapezoidal map ?(?????). ? ?(?) ? We can navigate from the node representing the center of one trapezoid to that representing the center of any other reachable trapezoid.

Motion Planning for a Point Robot ???? Input: starting position ?????? and goal position ?????. ????? ????? ????? Determine the trapezoids ????? and ???? containing ?????? and ?????, respectively. ?????? Let ?????? and ????? be the nodes at the centers of ????? and ????. ?????? Three parts of the path ?????? ?????: straight line segment ????????????; path ?????? ????? (via BFS); straight line segment ??????????.

Collison-Free Path ???? ????? Correctness hinges on two questions: ????? ????? Is the found path collision free? ?????? Yes, because it consists of segments inside trapezoids (which are in ?????). ??????

Completeness Does the algorithm always find a collision-free path whenever one exists? Suppose there is a collision-free path ?????? ?????. ?????and ???? are trapezoids ?????. ????? ?? 1 Path ?????? ????? crosses trapezoids 1= ?????, 2, , ?= ????. Node ?? at the center of ? ? ?? 1 ? 1 ?1 ?2 It suffices to show that a collision-free path ?1 ?? can be found. ?3 ?????? 2 3 For 1 ? ? 1, ? borders ?+1 (at a vertical extension). Collision free paths ?? ??+1 exist for 1 ? ? 1. A path ?1 ??exists (and will be found by BFS).

Planning Time Environment complexity: total number ? of vertices of the obstacles. #trapezoids = ?(?) Determine the trapezoids ????? and ???? containing ?????? and ?????, respectively. Use the point location structure of the trapezoidal map. ?(log?) Construct the path ?????? ????? (via BFS). ?(?) Report the path ?????? ?????. ?(?) Theorem A set ? of polygonal obstacles with ? edges can be preprocessed in ?(?log?) expected time such that a collision-free path for a point robot between any start and goal positions can be computed in ?(?) time if it exists.