First Annual Programming Contest on Grid Map Path Planning for Undergraduate Students
Contest open on TUE February 3, 2015
- ACM Professional Chapter in Prince Sultan University
- ACM Student Chapter in Prince Sultan University
Path planning in grid maps is an active research area in computer science that has a lot of applications in different areas including mobile robots, video games, transportation systems, telecommunication and networks. there has been a lot of algorithms devised to provide a solution to the path planning problem including exact methods such as A* and Dijkstra and heuristic algorithms such as Genetic Algorithm (GA), Ant Colony Optimization (ACO), and others.
This competition intends to involve undergraduate students in Prince Sultan University to contribute to this area by the implementation of existing or new algorithms of path planning in grid maps to compare between of performance of these algorithms.
Each group of student submits an implementation of a path planning algorithm of his choice. It can be a known existing algorithm like A*, or it can be newly designed algorithm by the group of students, It is recommended to consider A* or one of its variants and provide an optimized implementation of the algorithm.
It is highly recommended to carefully choose the data structure used in your program and have better execution time and memory performance.
1- First, download the source code of the jPath NetBeans project.
2- Have a look to the jPath java documentation
3- Open with NetBeans the jPath NetBeans project
4- Run the sample code of the Dijkstra implementation by running the class
PathFinderApp the and observe the execution.
5- You can try with different maps. Note that there is a folder called
maps that contains several maps with different sizes
How to Participate?
To participate to the competition, you need to program your own path planner exactly in the same of the Dijkstra planner.
Your planner must implement the interface
Planner defined in the jPath package. It must then override the method
findPath in the same way done with the Dijkstra planner.
These are some ideas that you can work on: 1- Improve the execution time of the Dijkstra planner provided in the sample code. In fact, the execution time with large maps is very large. You can improve the execution time by optimizing the code and using other data structure. There are several optimized implementations of the Dijkstra planner.
2- Implement the A* algorithm for grid map search. You can have this link as a reference. You can try to find better implementation of the A* algorithm
3- Implement any algorithm of your choice.
Note: You should not modify any of the classes provided. You need to only to program your own planner in a new class.
How to Submit
When you complete and test your implementation, send your code to akoubaa at coins-lab.org.
Submission deadline: April 20, 2015.
Content of the jPath package
In what follows a description of most important folders and files in the jPath package.
maps: a folder that contains several paths with different shapes and sizes
Cell.Java: a class the represents a cell in a grid map
GridMap.java: class the represents a grid map
Path.java: a class the represents a Path in a grid map
Planner.java: an interface that must be implemented by any planner
PathLib.java: a class that present some useful functions for Path manipulation
Dijkstra.java: presents an implementation of Dijkstra algorithm
PathFinderApp: is a executable class that test a path planning algorithm
Request for more information?
For any additional information, please contact the competition chair Dr. Anis Koubaa akoubaa at coins-lab.org