Motion Planning in Virtual Environments

Software Workshop (sadna)
Spring 2007


Due to the strike, various submission dates have changed. The new dates are marked by "(notice new date)" .

Instructors: Dan Halperin (TAU) and Yesha Sivan (AFEKA College of Engineering)
Monday 16-18, Schreiber 007

Teaching Assistant: Alon Shalita

The assignment in this workshop is to plan a collision free motion for moving bodies (robots) in an environment cluttered with obstacles. The major platform will be SecondLife, which is one of the first programmable Metaverse platforms. Several problems will be proposed as well as different solution approaches.

Possible projects:
 Robot getting out of a maze
 Hover (flying) chair
 Snake (multi-link) robots; follow-me dog
More projects will be proposed in class. Students are encouraged to propose their own projects.

Important Notice

As you will find out when you log into SecondLife (which is free of charge for limited actions), it can be a fascinating and varied experience. Also, there is quite a lot that one can do with the local scripting language SL. However, SL, which must be run on SecondLife's servers, may not be as strong as needed to develop some sophisticated motion-planning (and other) algorithms. Indeed, in class we will demonstrate how to communicate between an SL object and the outside world, where, for example, you can run a C++ program.
You should be aware of the fact that this solution is far from ideal, and there are many technical difficulties with this solution as well as with working with SecondLife in general (just now, at the time of writing this text, the SecondLife servers are down). Our brief experience is that the system is not completely stable nor very well documented. You need to take into account that alongside the exciting options that SecondLife offers, it can be rather painful to work with. In class we will review various pitfalls and shortcomings of the system.
If you prefer to focus on the algorithmics of motion planning, we will offer alternative, more stable, working environments. At the other end of the spectrum from SecondLife, you may opt for developing your own GUI with the simplest graphics.

Prerequisites: Software 1, Software Project, Algorithms, Data Structures.

Recommended team size: 3 students.

The submission of the project is in three steps:

1. (notice new date) May 28th, 2007: project proposal - a brief (2,3 pages) description of the project, platform, and work plan.
2. (notice new date) August 22nd, 2007: prototype and its documentation (students are strongly encouraged to submit the prototype earlier than this deadline to allow for more time toward the final submission)
3. (notice new date) September 23rd, 2007: submission of the full project, with project book (including a detailed programming guide)

Meetings during the semester (preliminary list, stay tuned):

 26/2/2007: Overview of the workshop (D.H. + Y.S.)
 5/3: A brief introduction to motion planning (D.H.)
Basics of motion planning, ppt slides.
For more background on solving translational motion planning in the plane (the maze solver), see Chapter 13 of the following book: M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications , 2nd Edition, Springer, 2000.
A warm-up exercise.
 12/3: Programming in SL, a primer (A.S.)
 19/3: Programming in SL, continued (A.S.)
 26/3: A survey of possible projects (D.H. + Y.S.)
 16/4: Discussion of projects (cancelled, student strike)
... strike ...
 28/5 (notice new date) : Project proposals: presentations by students

Last update: 28 May 2007