Project Description: goals and purpose of the project
Motion planning refers to the construction of inputs to a non-linear dynamical system that drives it from an initial state to a specified goal. Motion planning can be difficult due to geometric constraints. It is especially difficult if multiple robots perform motion tasks simultaneously.
Project Specific Goals/Questions
- In general, the goal is to study motion planning algorithms that robots can use to perform various tasks.
- Development a software to visualize and animate the robot motion.
- Comparative analysis of different algorithms.
Process used on the projectIn the first stage, known algorithms were studied, such as the left hand rule, angle constraint approach, and vertical decomposition. We tested the efficiency and productivity of these algorithms and take it a step further by selecting and modifying known algorithms.
We selected the following algorithms for implementation.
- RandomMotion. The RandomMotion algorithm implemented in every robot aims to the robot target and, if a collision occurs, tells the robot to move a certain distance in a random direction away from the collision. Once the robot has moved away to its temporary position, the robot will re-attempt to reach its final destination.
- Dominance. The concept behind Dominance algorithm can be viewed as an extension or modification of the RandomMotion approach. Upon collision of two or more robots, Dominance takes into consideration ranking by allowing the robot of highest rank to proceed undeterred while the lower ranking robots resort back to RandomMotion.
- Robots on grid. We consider robots on the grid, which means the motion is only horizontal and vertical. We designed two strategies: XY Strategy and Push Strategy. The XY-strategy is simple and can work in some situations. The Push strategy is more advanced and can help in some scenarios where XY-strategy fails.
ConclusionsSeveral motion planning algorithms were implemented and analyzed. Two types of model were considered: arbitrary robot motion and motion on the orthogonal grid.
The algorithms were implemented using Java and the applets are posted on the project website http://www.utdallas.edu/~sxb027100/creu.
Detailed description of the methods and the results can viewed at the project website. One of the conclusions is that robots can do motion planning in many scenarios even if their computational capacities are very limited.
Websites Developed and PublicationsWeb pages developed:- http://www.utdallas.edu/~sxb027100/creu
Papers or posters at conferences:
Back to 2007-2008 Project Listing