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/.

February 11, 2013
Volume 2, Issue 11

Motion Planning



Kensin Shi Video

Watch Kensin Shi, a high school senior, win a $100,000 Scholarship for his motion planning algorithm at: http://globenewswire.com

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.

Kensin Shi showing his algorithm

Kensin Shi is showing Dr. Nancy Amato and Ph.D. student Jory Denny his algorithm for the robot. Photo courtesy of Dr. Nancy Amato.



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.

Kensin Shi

Image of Kensin Shi.

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.



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.



As we walk from Point A to Point B, we select a path and navigate our way.  Computers analyze each step to pick the optimal route.  This activity will help students to think about how basic and tedious these steps must be. 

Break students into groups of 2.  One will be the “Sensor” and one will be the “Robot”. The Robot should be blindflolded and the Sensor will pick a location in the room for the Robot to get to. The Robot can ask "Yes" or "No" questions of the Sensor in order to navigate to the location.  The Sensor looks at the Robot's position and surrounding area, and then answers the Robot's question accordingly.  For example, questions might include: “Can I take three steps to the right? And, if I follow that instruction, will it get me closer to my destination?”

The class should then come back together and discuss the process.  Why do the questions need to be Yes/No?  Should questions be simple or multi-step?