Exploration Sampling Methods

I proposed two sampling-heuristic:

  • Artificial potential fields based sampling heuristic for goal directed exploration.
  • Triangular geometry based sampling heuristic for exploration of the space in close vicinity to the initial state and the goal region.
    • Applications include parking of autonomous cars.

The heuristics were tested on a sampling-based planning algorithm called RRT*. The uniform sampling heuristic of RRT* was replaced with the proposed methods. The results show that proposed sampling functions allow a considerable decrease in the number of iterations required to find a solution and thus lead to more efficient memory utilization and accelerated convergence rates.

RRT* with artificial potential field based sampling heuritcs (P-RRT*):

Figures (a-c): The sampling by P-RRT* results in incremental reduction in the size of the Voronoi regions in the direction towards the goal. Therefore it can be said that the proposed heuristic has a Voronoi bias that effectively guides the random samples towards the goal region.

Figures (d-e): Depicts the Voronoi biasing of RRT* with uniform sampling heuristic.

RRT* with triangular geometry based sampling heuristic (TG-RRT*):

TG-RRT* directs the random samples towards the centre of the triangle formed by the initial, goal and random sample locations. Four common triangular centers exist (as shown below), namely the incentre, the orthocentre, the circumcentre and the centroid. During the experimentation phase, all four of these centres were, one-by-one, appended to the TG-RRT* algorithm and the behaviour of the resulting algorithm was carefully observed. Out of these aforementioned triangular centres, only the incentre (IC-RRT*) and the centroid (C-RRT*) methods were successful in enhancing the performance parameters of the original RRT* algorithm for almost all test environments.

In all figures, j and t denotes the number of iterations and the taken by the mentioned algorithm whereas c corresponds to the length of the computed path solution.

Exploration by IC-RRT* :

Exploration by C-RRT*:

Exploration by RRT*:

Journal Publications:

  • Ahmed Hussain Qureshi and Yasar Ayaz, "Potential Functions Based Sampling Heuristic for Optimal Motion Planning", Autonomous Robots, DOI 10.1007/s10514-015-9518-0, 2015. (Imapct Factor: 2.066) [PDF]
  • Ahmed Hussain Qureshi, Saba Mumtaz, Yasar Ayaz, Osman Hasan, Mannan Saeed Muhammad and Muhammad Tariq Mahmood "Triangular Geometrised Sampling Heuristic For RRT* Motion Planner", International Journal of Advanced Robotic Systems (IJARS), InTech Publishers, 12:10, 2015, (Top Most Popular Paper of IJARS for 3 consecutive weeks in February - March 2015). (Impact Factor: 0.526) [PDF]

Conference Publications:

  • Ahmed Hussain Qureshi, Saba Mumtaz, Khawaja Fahad, Yasar Ayaz, Mannan Saeed, Osman Hasan, Whoi Yul Kim, Moonsoo Ra, "Triangular Geometry based Optimal Motion Planning using RRT*", Proceedings of 13th International Workshop on Advance Motion Control, pp. 380-386, Yokohama, Japan, 2014. [PDF]
  • Ahmed Hussain Qureshi, Saba Mumtaz, Khawaja Fahad, Badar Ali, Yasar Ayaz, Faizan Ahmed, Mannan Saeed, Osman Hasan, Whoi Yul Kim, Moonsoo Ra, "Adaptive Potential guided directional-RRT*", Proceedings of IEEE-RAS International Conference on Robotics and Biomimetics (ROBIO), pp. 1887-1892, China, 2013. [PDF]
  • Ahmed Hussain Qureshi, Khawaja Fahad Iqbal, Syeda Madiha Qamar, Fahad Islam, Yasar Ayaz, Naveed Muhammad, "Potential guided directional-RRT* for accelerated motion planning in cluttered environments", Proceedings of IEEE-RAS International Conference on Mechatronics and Automation (ICMA), pp. 519-524, Takamatsu, Japan, 2013. [PDF]