Motion Planning: Robots, Digital Actors, and Molecules

Project Gallery
2005-06 Selected Projects
 Moving in  Dynamic Environmen with Tabu Search. Jin Min and Qin Dika.
The artificial potential field methods provide simple and effective motion planners for practical purpose. However, the formation of local minima can trap the robot before reaching the goal. In this project, we integrated the artificial potential field approach with a powerful heuristic method, tabu search, to help the robot escape from the local minima. In order to apply tabu search algorithm to our motion planning problem, we customized the framework to address both problem-specific and algorithm-specific issues, and simulated the integrated algorithm with a 2D space environment where there are both static and dynamic obstacles. Our simulation results have shown quite a compromising performance on a number of complex dynamic environments.

 Constraining C -Space Sampling for Exploration. Chiang Tsung Han and Lau Qiangfeng, Peter.
The goal of this project is to investigate the feasibility and efficiency of using properties of the workspace in sampling within the configuration space C to solve the motion planning problem of searching for a target at an unknown location. This report describes an algorithm that first computes the constraints of the 3D workspace and use it in sampling the -space for waypoints to create a tour that explores the workspace.

2004-05 Selected Projects
Motion planning for legged robots on rough terrains. Rémi Fontan and Julien Bravet.
The walking robot problem is really interesting in robotics and can benefit several applications, in particular exploration of sub-surface environments such as caves, and planetary exploration, especially on Mars, because of the rough terrains that we may find on this planet. That is the reason why we are interested in this project to enable a six-legged robot to walk on rough terrains. The robot consists of several articulated limbs with an end-effector at the end of each limb. Only the end-effector can make contact with the environment, which consists of an horizontal surface with small, arbitrarily distributed features called footholds. On rough terrains, the robot must carefully select potential footholds on the ground and coordinate the different legs in order to achieve a collision-free configuration and overall stability. In this project, we consider only simple horizontal footholds that correspond to points on the plane and the robot chooses one foothold among the reachable ones according to a specific heuristic. It chooses also the foot to move in such a way that the robot is always well balanced and there is no collision with the other legs and its body. In this project, the robot moves only onwards and we do not deal with the general problem of finding a path from a start location to a goal location.
Autonomous computation of camera viewpoints and movements in virtual environments. Huynh Quang Thuan and Pham Thanh Phong.
Given a computer model of an object or a virtual environment, it is very hard for normal users to view or inspect the object since it requires the use of specialized tools, software, and skills. A video going through the the environment will give them a sense of the environment in a more pleasant way. Till now, generating such videos requires manually choosing view points and navigation order by an expert. With the fast growth of number of models today, generating videos for each model manually is not a feasible task. In this approach, given a model, the system will automatically compute a set of view points, and then generate a complete video of the scene by going through these points. Selecting good view points is achieved with the aid of a newly defined potential field. Camera path is computed by the PRM method and order of movements among view points is optimized by genetic algorithm. Camera looking direction is computed along the smoothed path to generate the video. The system has been tested with both object and virtual buildings models.


A Virtual Camera Tour for Pre-Mission Reconnaissance. Tan Chek Tien and Lim Sher Ee Dennis.
Today’s military relies heavily on satellite photos for details of the terrain. However, such photos only give a strategic view of the region, with little information on the tactical situation. As such, soldiers often move into the region half-blind. Our intention is to design a camera tour program in which such bases can be designated as hotspots and a motion path is created from a start to end point in a virtual environment, visiting all hotspots along the way, thus giving soldiers a feel of the terrain from ground level. We used a graphical coding program, Quest3d to accomplish this, and implemented a two-fold motion planning strategy to show the terrain layout in a useful manner.


2003-04 Selected Projects

Interesting game: Lookout decreasing versus stalking. Tirthankar Bandyopadhyay and Li Yuan Ping.

This project looks into the problem of stalking behavior. In this scenario we have two robots, one we call the target which moves along without any pre-specified intelligence and the other which we call the spy which follows the target where ever it goes. The spy has the additional constraint to make sure that he is not “visible” to the target. i.e. the spy will implement both the algorithms for the pursuit as well as the evasion. The aim of our project is to plan a path for tracking with least self visibility(the time the spy is visible to the target is shortest). We proposed two algorithms for  two typical environments i.e. narrow and open space which the strategy for the spy’s motion should be different. The motivation of our project is that in defense perspective, sometimes the spy wants to follow enemies to find out about their hideouts or their bases. Also such a behavior is also exhibited by wild animals for stalking and capturing their prey.

Digital Indian classical violin artist. Ankur Dhanik and Zhu Hongmei

We have looked into the animation of an Indian classical violinist’s hand. The motivation comes from the fact that one of us is learning playing violin. Violin is one of the most melodious musical instruments. The violin is played with two hands, one hand is used for bowing and the other one is used for fingering. Playing violin demands extreme coordination between the two hands and especially the four fingers of the left hand.

We consider it as a motion planning problem in a high dimensional space. The success of probabilistic and randomized algorithms in planning motion in high dimensional spaces is evident. Generally, such techniques are used to find a motion strategy given an initial and target point in the high dimensional space. In our case, the goal positions are known in Cartesian coordinates but we have to transform them to the joint space of the human hand. The goal can be single and multiple, which depends on which note is being played. Some people have already looked into the use of randomized algorithms in animations. We derive our motivation from the success of randomized motion planners and use the randomized technique with forward kinematics to find the joint angles. We use linear interpolation to plan motion of the hand in the joint space, from initial to final configurations. The interdependent motion of fingers is derived heuristically, using some constraints and observation.

Our naïve IK solver, though brute force now, fairs quite well and can be improved significantly with better randomized algorithms. Motion generation using linear interpolation gives good results. The finger motions are quite realistic.

The bowing motion of the arm is also solved using fairly simple geometry and some empirical data from observations. We were satisfied with the arm motion generated.

Overall, we were able to generate fairly realistic animation of an Indian Classical violin artist using simple techniques aided by intuition and observations. We feel that this approach can be built up to achieve much better results.

Localized adaptive motion planner. Chang Kok Meng, Foo Meng Fang, and Yeo Ye Chuan.


In applying the probabilistic roadmaps method for motion planning, one key problem is sampling points in narrow passages. We consider two well-known approaches in building probabilistic roadmaps for the motion-planning problem: (1) uniform sampling for the nodes in the roadmap, (2) Gaussian sampling approaches to get points in narrow passages.

When uniform sampling is used, fewer points in narrow spaces and this reduces the connectivity of the free space. With Gaussian sampling, efficient sampling requires correct choice for standard deviation, s, of the Gaussian distribution. The optimal s depends on the C-space characteristics. As the C-space is not uniform (i.e. sizes of free space and passages are different), a global value of s may not give the best solution.

For this project, we focus on the problem of a workspace with narrow passages. With both uniform and Gaussian sampling approaches, many sampled points around a narrow passage are discarded and this is inefficient.

To reduce this inefficiency, we attempt to adapt the sampling to the local characteristics of the configuration space by exploring 2 techniques: (1) dividing the configuration space into cells and use an adaptive algorithm to determine the number of points to sample in each cell, and (2) using an adaptive algorithm to select a suitable value of s for Gaussian sampling.

Mobile ad-hoc network routing in large crowd environment. Goh Han Leong.

The aim of this project is to model the crowd movement of people in an enclosed area, for example exhibition hall. The result of this monitoring can be use in wireless communication which will be illustrated below. Nowadays, most people carry mobile phone, and the mobile phone contains their friends’ phone number. Through this relation we can assume that if mobile phone A’ phone book contains mobile phone B number their respective owner should be friend. And people who know each other will tend to walk together. In an exhibition hall there will be many of these subgroups. By monitoring the relative motion of theses subgroup, we can form a shortest path for a communication route.

Based on the above observation a useful scheme for wireless ad hoc network is constructed .


Last updated: Sat Jul 29 14:58:34 SGT 2006