Research Page for Iyad Kanj
Research Interests: Parameterized and exact computation; combinatorial optimization; graph theory/algorithms; computational geometry; robot motion planning; computational biology.
Current Students
|
|
| Brandon Meng (Ph.D. student) |
Current Research Projects
Matrix Completion & Clustering
Matrix Completion Modulo Constraints: Matrix completion is a fundamental problem in Machine Learning. Given a matrix with missing entries, the goal is to complete the matrix so as to minimize a certain objective measure, such as the rank of the matrix, or the number of subspaces of bounded dimension into which the matrix can be partitioned. A richer setting is when the completion is subject to constraints imposed on the complete matrix.
The goal of this project is to investigate the complexity and design parameterized/exact algorithms for matrix completion problems.
Clustering Incomplete
Data: Clustering is a fundamental problem in data analytics, where
the objective is to cluster the data points so that the
intra-cluster similarity is high. In this setting, given a matrix,
some of whose entries might be missing, the objective is to complete the
missing entries in order to enable a partitioning of the matrix vectors/rows
into clusters, such that all elements in the same cluster are ``similar.''
Several measures of intra-cluster similarity are studied, including the
radius and diameter of the clusters.
The goal of this project is to design parameterized algorithms with respect to
natural clustering parameters such as: the radius/diameter of the clusters, the number of clusters,
the rank of the clusters, among others.
Robot Motion Planning
Path Planning in the Presence of Obstacles: Path planning is the problem of computing a path between two points that satisfies some desirable properties. Properties of interest include: shortest (w.r.t. Euclidean length or some weight function), obstacle-free, or if the latter is not possible, a path that overlaps with the fewest number of obstacles. Such problems shave applications in robotics, and lead to interesting computational geometry and/or graph problems.
In certain applications, the robot is equipped with a
devise with a coverage range (e.g., a camera, or a paint spray), and an
additional requirement on the sought path is that it covers a certain
area/volume (i.e., every point in the
area/volume is within the range of some
point on the path). Examples of such applications include covering a
terrain by a sweeping robot or by a robot equipped with a camera, or painting a
3-D object.
The goal of this project is to study parameterized/exact and approximation algorithms for such coverage problems, which, in most cases, turn out to be computationally hard.
Reliable & Efficient Motion Planning for Continuum-Arm Robots: Continuum-arm robots are bio-inspired devices that seek a middle ground between rigid and soft robots. They are made of multiple sections, where each section is a bundle of pneumatic muscle actuators. This results in high compliance, payload, inherent safety, and dexterous manipulability, making them perfectly suited to serve as co-robots. However, their high level of compliance comes at the price of high redundancy in their spatial shapes, making motion planning for such robots a big challenge, especially in environments clattered with obstacles.
The goal of this project is to design efficient, reliable, and stable motion planning algorithms for continuum-arm robots.
Recent Editorial and PC Service