Contests

From The iroboapp Project
Jump to: navigation, search

First Annual Programming Contest on Grid Map Path Planning for Undergraduate Students

Contest open on TUE February 3, 2015

Sponsors

  • ACM Professional Chapter in Prince Sultan University
  • ACM Student Chapter in Prince Sultan University

Overview

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.

Competition Rules

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.

Getting Started

1- First, download the source code of the jPath NetBeans project.

Download jPath Library Here

2- Have a look to the jPath java documentation

jPath Java Doc

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