RESEARCH

Robotics | Computational biology | Others

Geometry and motion are ubiquitous in the physical world, at both macroscopic and microscopic levels. To operate in this world or to simulate it, we need accurate models of the environment, compact data structures to represent the models, and efficient algorithms to compute motion for physical or simulated objects. We are interested in representations and algorithms for synthesizing and analyzing motion and the applications of these techniques in computational biology and robotics.

ROBOTICS

Online POMDP Planning

Online POMDP Planning

 

Continuous POMDP Planning Continuous POMDP Planning 
Offline POMDP Planning Offline POMDP Planning

This project addresses the key challenges in building fast algorithms and software for solving partially observable Markov decision processes (POMDPs). APPL is a software package that implements our POMDP solvers.

targettrack2 Autonomous Target Tracking

Our motivation is to build autonomous robots that can follow people and recognize their activities. Such capabilities are important in applications such as home care for the elderly, intelligent environments, and iteractive media. In particular, the goal of this project is to develop reliable and efficient motion strategies for an autonomous robot to follow a target and keep it within the sensor range, despite occlusion by obstacles.

Autonomous Target Tracking (complete) Autonomous Target Following

Our motivation is to build autonomous robots that can follow people and recognise their activities. Such capabilities are important in applications such as home care for the elderly, intelligent environments, and interactive media. In particular, the goal of this project is to develop reliable and efficient motion strategies for an autonomous robot to follow a target and keep it within sensing range. In this research, we investigate the use of greedy strategies using local information to achieve goal.

hybrid Adaptive Hybrid Sampling

Several advance sampling strategies have been proposed in recent years to address the narrow passage problem for probabilistic roadmap (PRM) planning. The sampling strategies all have unique strengths, but none of them solves the problem completely. We investigate general and systematic approaches for adaptively combining multiple sampling strategies so that their individual strengths are preserved. Our preliminary results show that although the performance of individual sampling strategies varies across different environments, the adaptive hybrid sampling strategies that we have constructed perform consistently well. We can also show that, under reasonable assumptions, the adaptive strategies are provably competitive against all individual strategies used.

singlequery2 Single-Query Randomised Path Planning

Motion planning is concerned with computing collision-free motion for moving objects (e.g., drug molecules inside the binding cavity of a protein, robot manipulators on an assembly line, or articulated models of human arms) in an environment populated with obstacles. The key difficulty of motion planning is its exponential dependence on the number of degrees of freedom of a moving object. The focus of this work is to use random sampling as a fundamental technique for attacking this issue.

Kinodynamic Motion Planning with Moving Obstacles

The moon of physical objects is subject to kinematic and dynamic constraints. For example, a car cannot move sidewise; a bouncing ball must obey the laws of physics. These constraints compound the difficulty of motion planning. We have extended our sampling techniques for path planning to handle objects whose motion is described by a control system, which is a set of differential equations that captures diverse types of kinematic and dynamic constraints. In particular, our implemented algorithm is fast enough to deal with moving obstacles in “real-time”.

Robot Placement (completed) Robot Placement

Proper placement of the base of a robot manipulator is an important issue in many robotics applications. For instance, in manufacturing, the base location of a manipulator has a significant impact on the cycle time of tasks such as spot welding and inspection. An automated means to determine the best placement can both increase the throughput of work cells and reduce set-up time. This work investigates methods that employ randomised motion planning techniques to search for the best placement efficiently.

 

COMPUTATIONAL BIOLOGY

pathway2 Pathway Modelling

Our goal is to develop and analyze models of large biochemical networks that typically arise in the study of signalling pathways. Specifically, we have been addressing a basic problem that arises when one constructs ODEs based bio-pathways models; namely, one must first estimate the values of many unknown rate constants and initial concentrations using limited noisy data. We have developed decomposition methods using which a large model can be broken down into smaller models. One then does parameter estimation on the smaller models followed by reconciling conflicting estimates of shared parameters via the well known technique called belief propagation. We have also been building a powerful approximation technique through which a large ODEs based model (with many unknown parameters) is first converted into a probabilistic graphical model called a dynamic Bayesian network. All subsequent analysis including parameter estimation is then carried out on the approximated –much simpler- model with the help of standard Bayesian inferencing techniques. We have applied this method successfully in a number of biologically relevant settings. We are also continuing to extend its scope and applicability along multiple dimensions. In particular we are developing GPU-based implementations of all our algorithms as well as formal verification techniques such as probabilistic and statistical model checking.

Protein Flexibility Analysis (completed) Protein Flexibility Analysis

Protein conformational changes play a critical role in vital biological functions. Due to noise in data, determining salient conformational changes accurately and efficiently is a challenging problem. We have developed an efficient algorithm for analysing conformational changes of a protein, given its structures in two different conformations. A key element of the algorithm is a statistical test that determines the similarity of two protein structures in the presence of noise. Using data from the Protein Data Bank and Macromolecular Movements Database, we tested the algorithm on proteins that exhibit a range of different conformational changes the results show that our algorithm can reliably detect salient conformational changes, including well-known examples such as hinge and shear.

Stochastic Roadmap Simulation of Molecular Motion (completed) Stochastic Roadmap Simulation of Molecular Motion 

Many interesting properties of molecular motion are best characterized statistically by considering an ensemble of motion pathways rather than an individual one. Classic simulation techniques, such as the Monte Carlo method and molecular dynamics, generate individual pathways one at a time and are easily “trapped” in the local minima of the energy landscape. They are computationally inefficient if applied in a brute-force fashion to deal with many pathways. We introduce Stochastic Roadmap Simulation (SRS), a randomized technique for sampling molecular motion and exploring the kinetics of such motion by examining multiple pathways simultaneously.

ligand2 Ligand Binding to PXR 

The human pregnane X receptor (hPXR) is a nuclear receptor that binds to various ligands, regulating the breakdown of drugs in the human body. To study drug-drug interactions, we are investigating a method that predicts potential ligand binding conformations in the binding pocket of hPXR.

 

OTHERS

Collision Detection (completed) Collision Detection 

Computing distance between objects is an important problem in many applications, for example, virtual environment simulation, computer animation, and robot motion planning. Distance information can be used to detect collision, as collision has undesirable consequences in most systems. It can also be used to guide sampling in randomized motion planning algorithms. This project investigates efficient algorithms for collision detection and distance computation. The particular emphasis is on collision detection among moving objects.

Motion Synthesis for Character Animation (completed) Motion Synthesis for Character Animation

Creating motion for human-like characters is an interesting and important problem. Despite the versatility of human movement, two types of behaviors are essential: locomotion (moving around in an environment) and manipulation (using hands and arms to manipulate objects).