Skip to content

Timeline

Jump to bottom Edit New page
Shivam Vats edited this page Jul 22, 2016 · 7 revisions

##Abstract

The MHA* is a major improvement over single heuristic based A* planners as it made designing of heuristics much easier. Despite that, we still need to put quite a bit of effort into designing and choosing heuristics for good performance. A next logical step, therefore is to automate the process of heuristic design.The method proposed includes two steps:

  1. Given a map, find out the difficult local minima or bottlenecks.

  2. Once bottlenecks are identified, generate heuristics to navigate through them.

ICRA submission Deadline : 10th September, 2016

##Current Status

  • I have been able to profile searches to identify states on the right path that took a long time to be found, implying the existence of local minima in the vicinity. The expanded state is the way to get out of that minima.

  • I have worked on generating island heuristics to improve search. Given that the states expanded after a lot of search are exits from local minima, we can use them to find islands and then generate heuristics. The reason we need to run clustering/mode-finding on top of them (as opposed to taking top n) is that across multiple searches, there could be multiple exits from a large local minima which could decrease our coverage of the map (as there is a restriction on the number of islands we can have). Each cluster center (after clustering) will roughly correspond to distinct a local minimum.

##Future Plan

30th July - 31st July

  • Test island heuristics with different DOF combinations (on the bottleneck data).

1st Aug- 7th Aug

  • Start with bare admissible heuristics to generate training data and use that to improve search.

  • Try doing that over multiple iterations.

8th Aug- 14th Aug

  • Consider alternative approaches to come out of the local minima (Dynamic MHA ?)

  • Can the relevant subspace for each heuristic be automatically figured out? Or can we automatically construct a heuristic function that correctly combines the different DOF's?

15th Aug- 21st Aug

  • Test planner on gazebo.

  • Buffer period.

22nd Aug- 28th Aug

  • Start doing experiments on the PR2 and writing the paper.
Add a custom footer
Add a custom sidebar
Clone this wiki locally