CS Bits & Bytes is a bi-weekly newsletter highlighting innovative computer science research. It is our hope that you will use CS Bits & Bytes to engage in the multi-faceted world of computer science to become not just a user, but also a creator of technology. Please visit our website at: www.nsf.gov/cise/csbytes/.

Motion Planning

 

Imagine that you are sitting in the back corner of your relatively empty school cafeteria. You see what appears to be a $20 bill lying on the floor in the front opposite corner of the room. You want to go check it out. Between you and the bill are rows of tables and a few people standing around. How do you navigate to get there? Maybe you pass between tables where there is space, or you have to walk all the way around a row of tables if your path is blocked. You make judgments of how to get from point A to point B fairly quickly and intuitively. For a robot with a computer brain, this is a more difficult problem. There are many possible paths, and the computer for the robot uses an algorithm to figure out the best and fastest - before someone else gets there - way to get there.

 

 

The development of efficient and robust algorithms for motion planning is an active area of research in computer science and will continue to become more important as computers interact more closely with our physical world.  This is challenging because the real world is complex and dynamic, that is, always changing. Sensors gather information to create a roadmap of the room and to determine any obstacles in real-time. This random positioning is done a number of times to create a roadmap that can be navigated without obstacles. Special mathematical methods are then used to determine the shortest path between points as it moves around obstacles to a destination.

Motion planning algorithms can be used in a variety of applications from driverless cars and surgical robots and on to automated factories or character animation. For surgical robots, algorithms are needed to figure out the most direct way to access a tumor, while making the smallest incision possible and not damaging organs. Automated factories use motion planning algorithms to optimize the operation of multiple robots, and animated characters in video games and movies use motion planning algorithms to make the characters move in more realistic, lifelike ways.

Who Thinks of this Stuff?! Kensen Shi is a 17-year old high school senior at A&M Consolidated High School in College Station, TX.  In December 2012, Shi won a $100,000 scholarship in the Siemens Competition in Math, Science, and Technology. Working with Dr. Nancy Amato, a computer scientist at Texas A&M University and Ph.D. student Jory Denny, Shi was able to combine two previous algorithms to create a new, faster, and more efficient one to help robots find safe paths around obstacles. His project is called Lazy Toggle PRM, but Shi is anything but lazy!  He said that his inspiration to do research was to put his textbook knowledge to use and solve real-world problems.

 

Links:

Dr. Lydia Kavraki is a pioneer in motion planning, and her work is the basis for many of the current generation algorithms in this area. She and her colleagues at Rice University in Houston, TX have created an “open source” suite of motion planning tools. Open Source means that the software is freely available for others to use and to modify. You can download a graphical motion planning simulator at: http://ompl.kavrakilab.org/.

See some cool images from a Stanford University course on Motion Planning at: http://ai.stanford.edu/~latombe/cs26n/2012/home.htm.

For more information on Kensen Shi’s Siemens Prize, visit: http://www.nbcnews.com/id/50076026/#.URFkCaV_2zA.