Click here for event details.
Title: How to navigate a robot through obstacles? – Iyad Kanj (Depaul)
We consider the following motion planning problem: Given a set of obstacles in the plane, can we navigate a robot between two designated points without crossing more than k different obstacles? Equivalently, can we remove k obstacles so that there is an obstacle-free path between the two designated points?
As you learned last Friday, the above problem is NP-hard, even when each obstacle is a line segment. The problem can be formulated and generalized into the following graph problem: Given a planar graph G whose vertices are colored by color sets, two designated vertices s, t in V(G), and a natural number k, is there an s-t path in G that uses at most k colors? If each obstacle is connected, the resulting graph from this formulation satisfies the property that each color induces a connected subgraph of G.
In this talk, we discuss the parameterized complexity of the above graph problem. We first show that, without the color-connectivity property, the problem is parameterized intractable, and sits high in the parameterized complexity hierarchy. We show that even very restricted slices of the problem remain parameterized intractable. We then shift our attention to instances in which each color is connected. We exploit the planarity of the graph and the connectivity of the colors to design a parameterized algorithm for the problem w.r.t. the combined parameters k and the treewidth of the graph. Finally, we discuss applications of this parameterized algorithm to the geometric motion planning problem.
This is joint work with Eduard Eiben at TU-Wien.
Iyad Kanj is a Professor in the School of Computing at CDM. He obtained his Ph.D. from Texas A&M University in 2001, and joined DePaul the same year. His research area is algorithms and complexity theory, and his research interests are: parameterized complexity & exact computation, graph theory & algorithms, combinatorial optimization, and computational geometry.