Personal tools
You are here: Home Courses Workshop Spring 2011 Coordinating Multi Disc Robots and Web Integration
« September 2017 »
Log in

Forgot your password?

Coordinating Multi Disc Robots and Web Integration

Coordinating Multi Disc Robots

Consider k disc robots Br(1),Br(2),...,Br(k) with radii r(1),r(2),...,r(k), respectively, moving in a room cluttered with polygonal obstacles. Devise a data structure that can efficiently answer queries of the following form: Given k free start positions s(1),s(2),...,s(k) of the robots and k free goal positions g(1),g(2),...,g(k), respectively, plan a collision-free motion of the robots Br(i), i \in {1,2,...k} from s(i) to g(i), such that the robots do not collide and avoid the obstacles during their motions.

The program mp_two_discs coded in the file mp_two_discs.cpp and the header files it includes solves the problem for two disks. It is based on CGAL. Even for only two disks it can handle only relatively simple obstacles. It is described in detail in the book "CGAL Arrangements and Their Applications". The book is expected to be published this year, but we are giving you an early insight. The book web-page contains links to all the source files of the examples and applications described in the book (including the one above). It also contains links to relevant data and miscellaneous files.

The syntax of the command line to execute the program above follows:

mp_two_discs obstacle-file radius#1 radius#2 #vertices #edges queries-file

Here are two examples of execution:

mp_two_discs obstacles_simple.dat 2 2 32 32 queries_simple.dat
mp_two_discs obstacles_maze.dat 1 1 32 32 queries_maze.dat

You may use the program above as your base code, Enhance it to solve your problem, and optimize it.

The script generates mazes in the format of the obstacle file accepted by the program. The script accepts a positive integer as the number of spikes of the maze. The image depicted on the right shows a maze with 8 spikes generated by the script. Type:

gen_maze --help

to obtain the exact syntax.

The program above solves the 2-disk motion-planning program for two disks of radii 1 only for a maze of four or less spikes in less than a few minutes.

You are asked to optimize the program (this may require devising and implementing different algorithms) so that it solves the k-disk motion-planning problem for more complex obstacles. For example, your program should solve the problem for 2 disks of radii 1 for a maze of at least 8 spikes. (Please, do not stop at 8 spikes). Recall, that the program should also solve the problem for more than 2 robots.

Your solution will be given a score that takes in account the number of robots, the number of spikes, the radii, and the time consumption. The provider of the solution with the highest score will win a valuable price. ok, perhaps no so valuable, but with high prestige.

Multi Robot

Web Integration

This part is optional

The web page offers solutions to some geometric problems. (Do not confuse them with the problem you need to solve.)The service is integrated into this website, which runs Plone (an open source content management system). It offers already a solution to the "Translating Polygonal Robot" problem described below (through the first item in the web page above). Integrate your solution as a web service.


A Translating Polygonal Robot

Given a polygonal robot Q, which can translate (but not rotate) in a room cluttered with polygonal obstacles, maintain a data structure that can efficiently answer queries of the following form: Given a start position s of some reference point in Q and a goal position g, plan a collision-free motion of the robot from s to g.

Python Binding

This part is optional

Several components of CGAL have already Python bindings; see CGAL Python Bindings for more information. Add Python bindings to the components of CGAL you plan to use as part of your solution. For example, the provided base code contains a call to the function CGAL::approximated_offset_2(), which generates a general polygon with holes. When the program is executed a collection of polygons with holes is computed and the polygons are unified. The union is stored in an object S, the type of which is an instance of the class template CGAL::General_polygon_set_2<>. (The union is computed with the join() member-function). At some point the program queries the object S using the oriented_side() member-function. This implies that you need Python bindings to CGAL::approximated_offset_2() and CGAL::General_polygon_set_2<>, assuming your program is based on the provided code.

If you use Python bindings for CGAL, we advise you to use Python bindings for QT as well to visualize the date; see below. This way you can develop your entire solution in Python.


Enhance your program with the ability to visualize the input, the intermediate data-structures, and the output. You may use any visualization tool you are familiar with. However, if you decide to implement your application in Python (using CGAL python bindings), you should consider using also QT and in particular Python bindings for QT. If you integrate your application as a web service, then visualization must be done within a web browser. In this case it is recommended to use Java.

Document Actions