Report

Visibility Graph Team 10 NakWon Lee, Dongwoo Kim Robot Motion Planning • Consider the case of point robot • The polygons in S are obstacles, and their total number of edges is denoted by n • The point robot can touch obstacles, because obstacles are open set. • Start position . Goal position . • Paths do not intersect the interior of any of the obstacles. Robot Motion Planning • Use trapezoidal map ( )of the free configuration space . • Configuration space is the parameter space of a robot . Denoted by (). • For a point robot, was simply the empty space between obstacles. Configuration Space Shortest Paths • Construct the trapezoidal map ( ) for configuration space . • Construct the load map . • Find the trapezoids which have the start point or end point. • Find the shortest route in the load map using breadth first search algorithm. Shortest Paths Shortest Paths • Shortest path in road map is not a real shortest path • because some arcs are btw nodes that are far apart, whereas others are btw nodes that are close to each other. • It is just minimum number of hop. • To improve this problem, give each arc a weight corresponding to the Euclidean length, and use graph search algorithm that find the shortest path in a weighted graph. • Dijkstra's algorithm • But, it is still not a shortest path. Shortest Paths • Think of this path as an elastic rubber band. • Fix the endpoints at the start and goal position. • Try to tighten the rubber band. • It will be stopped by the obstacles. • The new path will follow parts of the obstacle boundaries and straight line segments through open space. Shortest Paths • Lemma 15.1 Any shortest path between and among a set of disjoint polygonal obstacles is a polygonal path whose inner vertices are vertices of • Inner vertex – A vertex that is not the begin or endpoint of the path. Shortest Paths • Proof. • Suppose for a contradiction that a shortest path is not polygonal. • Point on that lies in the interior of the free space with the property that no line segment containing is contained in . 1 2 Shortest Paths • There is a disc of positive radius centered at that is completely contained in the free space. • Part of inside the disk, which is not a straight line segment, can be shortened by replacing it with the segment connecting the points which lie on circle. • Contradict the theorem “any shortest path must be locally shortest”. Shortest Paths • Now consider a vertex on . It cannot lies in the interior of the free space. • Consider the disc centered at such that half of the disc is contained in the free space. • Can replace the sub path inside the disc with a straight line segment. • The only possibility left is that is an obstacle vertex. short cut 1 2 1 2 Shortest Paths • Construct a road map with this characterization. • This road map is visibility graph of , denoted by (). • Its nodes are the vertices of . • There is an edge between vertices and if they can see each other. • The segment dose not intersect the interior of any obstacle in . Shortest Paths • Two vertices that can see each other are called visible. • The segment connecting visible two vertices is called a visibility edge. • Endpoint of the same obstacle edge always see each other. • Hence, the obstacle edges form a subset of the edges of (). Shortest Paths • To make a complete road map to find shortest path, add start and goal point as vertices to . • So we consider the visibility graph of the set ∗ ≔ ∪ { , }. • Corollary 15.2 The shortest path between and among a set of disjoint polygonal obstacles consists of arcs of the visibility graph ( ∗ ), where ∗ ≔ ∪ { , }. Shortest Paths Visibility Graph Definition: • The visibility graph of s and t and the obstacle set is a graph whose vertices are s and t the obstacle vertices, and vertices v and w are joined by an edge if v and w are either mutually visible or if (v, w) is an edge of some obstacle. Visibility Graph Visible Vertices Visible Vertices Visible Definition Two points p and q are mutually visible if the open line segment joining them doesn't intersect the interior of any obstacle. Search Tree Computing the Visibility Graph • VisibleVertices: () – (sorting) • Operation on blanced search tree : () • For every vertices with Visible Vertices. • VisibilityGraph – (2 ) Computing the Visibility Graph • Give an (2 ) procedure for constructing. • is the number of line segments in the plane. • No three vertices are collinear?? • The algorithm is not output sensitive. • An ( log + ) algorithm ( is the number of edges in visibility graph) is existent but quite complicated. Computing the Visibility Graph • The text’s algorithm operates by doing sweep one vertex at a time. • New algorithm does the sweep for all vertices simultaneously. • When we use the arrangement, angular sort can be performed for all vertices in (2 ) time. • If we build the entire arrangement, this sorting algorithm will involve (2 ) space. • However it can be implemented in () space using an algorithm called topological plane sweep. Computing the Visibility Graph • First, recall the algorithm for computing trapezoidal maps. • Shoot a bullet up and down from every vertex until it hits its first line segment. • Angle continuously sweeps out all slopes from − ∞ to +∞. • All bullet lines attached to all the vertices begin to turn slowly counterclockwise. Computing the Visibility Graph • The question is what are the significant event points, and what happens with each event? Computing the Visibility Graph • It is useful to view the problem both in its primal and dual form. • 2 ( is the number of segments) segment end points = ( , ), its dual line ∗ : = − . • Significant event occurs whenever a bullet path in the primal plane jumps from one line segment to another. • This occurs when reaches the slope of the line joining two visible endpoints and . Computing the Visibility Graph event event event Computing the Visibility Graph • To keep track of which endpoints are visible and which are not is complicated. • Instead we will take events to be all angles between two endpoints, whether they are visible or not. • By duality, the slope of such an event will correspond to the -coordinate of the intersection of dual lines ∗ and ∗ in the dual arrangement. Dual Arrangement x-coordinate is the slope of dual segment Dual of point D Dual of point C Find Events • By sweeping the arrangement of the 2 dual lines from left-to-right, we will enumerate all the slope events in angular order. Find Events Angular order • By using topological plane sweep, event do not need to be sorted. Topological Plane Sweep • Provides a way to sweep an arrangement of lines using a “flexible” sweeping line. • Because events do not need to be sorted, we can avoid (log ) factor. Topological Plane Sweep • Upper horizon tree • Lower horizon tree Topological Plane Sweep • Data structure • [1: ] – array of line equation. = ( , ), if the th line of , , is = + . • [1: ] – an array representing the upper horizon tree. [] is a pair ( , ) of indices indicating the lines that delimit the segment of in the upper horizon tree to the left and to the right. • 1: – represents the lower horizon tree. • – a set of integers, represented as a stack. If is in , then and +1 share a common right endpoint. • [1: ] – an array holding the current sequence of indices that form the lines 1 , 2 , ⋯ , of the cut. • 1: – a list of pairs of indices indicating the lines delimiting each edge of the cut. [] thus encodes the endpoints of the edge on []. The same convention as that above is used for missing endpoints. Topological Plane Sweep If segment is the rightmost on , set = 0 If segment is the leftmost on , set = −1 Topological Plane Sweep • Algorithm Initialization: • 1. Sort the lines of the arrangement by slope. • 2. Find the leftmost and the rightmost intersection point of the lines. Let the two points be ( , ) and ( , ). • 3. Create vertical lines = − 1, = + 1 as left boundary and right boundary. Determine the intersection points of lines 1 , ⋯ , with the boundaries. • 4. Create upper horizon tree: Insert 1 , ⋯ , . Assume 1 , ⋯ , have been inserted. These lines form an upper bay. To insert +1 , begin at its endpoint on the left boundary. Walk in counter clockwise order around the bay till we find the intersection point of +1 with an edge. • 5. Create lower horizon tree similarly by starting the travers at endpoints on the right boundary. • 6. Initialize : Let [] = (−1, ) and [] = (−1, ). If intersects to the left of the intersection point of and then the right delimiting line of is . Otherwise, the right delimiting line of is . • 7. Initialize by scanning . Topological Plane Sweep • Algorithm Elementary Step • While = Λ • 1. Pop from • 2. Swap [], [ + 1] /*lines are going to cross, after the elementary step*/ • 3. . ← + 1 . , + 1 . ← []. /*the point of elementary step becomes the left endpoint of the two new cut edges */ • 4. Update , . • 5. . ← . , . , + 1 . ← + 1 . , + 1 . /* find the new right endpoints */ • 6. If [ + 1]. = [ + 2] then push + 1 into . If []. = [ − 1] then push − 1 into . /* push valid vertices formed after sweeping into I if there is any */ What Happens at Each Event • For each vertex , there are two bullet paths growing from along the line with slope . • Let () and () denote the line segments that forward bullet path and backward bullet path hit. • If either path does not hit any segment then we store a special null value. • Each slope is determined by exactly two lines. What Happens at Each Event • Possible scenarios What Happens at Each Event • Same segment • If and are endpoints of the same segment, then they are visible, and we add the edge (, ) to the visibility graph. • How can I check this? What Happens at Each Event • Invisible • Consider the distance from to . • Compute the contact point of the bullet path shot from in direction with segment () or (). • If is longer than , and are not visible. Calculate the distance of Calculate the distance of What Happens at Each Event • Segment entry • If we are entering the segment, then we set () or () to this segment. • can be a visibility edge. What Happens at Each Event • Segment exit • The bullet path will need to shoot out and find the next segment that it hits. • It is available in (1) time. • Since we are sweeping over at the same time that we are sweeping over . • We know that the bullet extension from hits . • So, new () is same as (). () Thank You Q&A