Path Planning for Point RobotsProblemFrameworkVisibility graph methodWhat is a visibility graph?A simple algorithm for building visibility graphsComputational efficiencyFrameworkBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchOther graph search algorithmsFrameworkA brief summaryGeometric PreliminariesPrimitive objects in the planePrimitive objects in the planeIntersecting primitive objects in the planeIntersect line segmentsIntersect line segments with ccwIntersecting primitive objects in the planeAdditional informationVisibility graph methodClassic path planning approachesClassic path planning approachesRoadmapVoronoi diagram methodOther roadmap methodsClassic path planning approachesCell-decomposition methodsTrapezoidal decompositionComputational efficiencyAdjacency graphFrameworkA brief summaryCell-decomposition methodsQuadtree decompositionOctree decompositionSketch of the algorithmClassic path planning approachesPotential fieldAttractive & repulsive fieldsAlgorithm in picturesSketch of the algorithmLocal minimaQuestionCompletenessNUS CS 5247 David HsuPath Planning for Path Planning for Point RobotsPoint RobotsNUS CS 5247 David Hsu 2Problem Input Robot represented as a point in the plane Obstacles represented as polygons Initial and goal positions OutputA collision-free path between the initial and goal positionsNUS CS 5247 David Hsu 3Frameworkcontinuous representation(configuration space formulation)discretization(random sampling, processing critical geometric events)graph searching(breadth-first, best-first, A*)NUS CS 5247 David Hsu 4Visibility graph method Observation: If there is a a collision-free path between two points, then there is a polygonal path that bends only at the obstacles vertices. Why? Any collision-free path can be transformed into a polygonal path that bends only at the obstacle vertices. A polygonal path is a piecewise linear curve.NUS CS 5247 David Hsu 5What is a visibility graph? A visibility graph is a graph such that Nodes: qinit, qgoal, or an obstacle vertex. Edges: An edge exists between nodes u and v if the line segment between u and v is an obstacle edge or it does not intersect the obstacles.NUS CS 5247 David Hsu 6A simple algorithm for building visibility graphsInput: qinit,qgoal, polygonal obstaclesOutput: visibility graph G1: for every pair of nodes u,v2: if segment(u,v) is an obstacle edge then3: insert edge(u,v) into G; 4: else5: for every obstacle edge e6: if segment(u,v) intersects e7: go to (1);8: insert edge(u,v) into G.NUS CS 5247 David Hsu 7Computational efficiency Simple algorithm O(n3) time More efficient algorithms Rotational sweep O(n2log n) time Optimal algorithm O(n2) time Output sensitive algorithms O(n2) space1: for every pair of nodes u,v O(n2)2: if segment(u,v) is an obstacle edge then O(n)3: insert edge(u,v) into G;4: else5: for every obstacle edge e O(n)6: if segment(u,v) intersects e7: go to (1);8: insert edge(u,v) into G.NUS CS 5247 David Hsu 8Frameworkcontinuous representation(configuration space formulation)discretization(random sampling, processing critical geometric events)graph searching(breadth-first, best-first, A*)NUS CS 5247 David Hsu 9Breadth-first searchAB CDEFNUS CS 5247 David Hsu 10Breadth-first searchAB CDEFNUS CS 5247 David Hsu 11Breadth-first searchACDBEFNUS CS 5247 David Hsu 12Breadth-first searchACDBEFNUS CS 5247 David Hsu 13Breadth-first searchACDBEFNUS CS 5247 David Hsu 14Breadth-first searchACDBEFNUS CS 5247 David Hsu 15Breadth-first searchACDBEFNUS CS 5247 David Hsu 16Breadth-first searchACDBEFNUS CS 5247 David Hsu 17Breadth-first searchACDBEFNUS CS 5247 David Hsu 18ACDBEFBreadth-first searchInput: qinit, qgoal, visibility graph GOutput: a path between qinitand qgoal1: Q = new queue;2: Q.enqueue(qinit);3: mark qinitas visited;4: while Q is not empty5: curr = Q.dequeue();6: if curr == qgoalthen7: return curr;8: for each w adjacent to curr10: if w is not visited11: w.parent = curr;12: Q.enqueue(w)13: mark w as visitedNUS CS 5247 David Hsu 19Other graph search algorithms Depth-first Best-first, A*NUS CS 5247 David Hsu 20Frameworkcontinuous representation(configuration space formulation)discretization(random sampling, processing critical geometric events)graph searching(breadth-first, best-first, A*)NUS CS 5247 David Hsu 21A brief summary Discretize the space by constructing visibility graph Search the visibility graph with breadth-first searchHow to perform the intersection test?NUS CS 5247 David HsuGeometric PreliminariesGeometric PreliminariesNUS CS 5247 David Hsu 23Primitive objects in the plane 0-dim 1-dimclass Point {double x;double y;}class Segment {Point p;Point q;}NUS CS 5247 David Hsu 24Primitive objects in the plane 2-dimclass Triangle {Point p;Point q;Point r;}class Polygon {list<Point> vertices;int numVertices;}NUS CS 5247 David Hsu 25Intersecting primitive objects in the plane Case 1: line segment & line segment ??=NUS CS 5247 David Hsu 26Intersect line segments Counter-clockwise testabcbcab×00bcabbcabyyyyxxxxkji−−−−isCcw(Point a, Point b, Point c ) {u = b – a;v = c – b;return (u.x*v.y – v.x*u.y) > 0;}NUS CS 5247 David Hsu 27Intersect line segments with ccwisCoincident(Segment s, Segment t) {return xor(isCcw(s.p, s.q, t.p),isCcw(s.p, s.q, t.q)) &&xor(isCcw(t.p, t.q, s.p),isCcw(t.p, t.q, s.q))} Pseudo-code Special casesNUS CS 5247 David Hsu 28Intersecting primitive objects in the plane Case 2 line segment l & polygon P Intersect l with every edge of P Case 3 polygon P & polygon Q Intersect every edge of Pwith every edge of Q More efficient algorithms exist if P or Q are convex.NUS CS 5247 David Hsu 29Additional information CS 4235 computational geometry Efficient geometry libraries CGAL, LEDA, etc.NUS CS 5247 David Hsu 30Visibility graph method Represent the connectivity of the configuration space in the visibility graph Running time O(n3) Compute the visibility graph Search the graph An optimal O(n2) time algorithm exists. Space O(n2) Can we do better?NUS CS 5247 David Hsu 31Classic path planning approaches RoadmapRepresent the connectivity of the free space by a network of 1-D curves Cell decompositionDecompose