A* Path Planning

[camieac]

I have found a number of resources that you may find useful:

• Solving mazes using Python: Simple recursivity and A* search
• Searching using A* (A-Star) - MIT

  Tasks

• Create a new python file in the navigation module, for our A* implementation.
• The world will need to be represented in a grid form, the size of the grid will determine the precision of the path. The width and height of the grid should always be the same (square grid). The size of each square should be easily modified.
• An object representing a square should be created to store information about it's weight, GPS location, boolean for goal, boolean for start location (these are guesses).
• You'll need to decide how big your 2D array of squares is going to be, and how you want to manage it. Do you want a centre square to always represent your current location or do you want to dynamically add more squares to the edge of the array as you approach it?

• The algorithm itself: You'll need an accessible function similar to this:

  def drive_to_destination(self, lat, long):
    # source and destination are Square objects
    destination = self.find_square(lat, long)
    source = self.find_square(my_lat, my_long)
    route = find_path(source, destination)
    navigation.followPath(route, 1, 100)

  In order to find this square object you'll need some sort of mapping between GPS lat/long and squares. I've just made a find_square() function that searches through the 2D array of squares for a square that contains the lat and long that you passed in. This can be worked out using the width of the square and the gps location of the centre of the square.

  find_path(source, destination) takes in the source square and the destination square and returns the array of points in the correct format to be passed to navigation.followPath(). This is where the actual A* algorithm will take place, in find_path(source, destination).

When you commit your code it would be nice of you add #47 at the start to attach the commit to this issue.

[StuartThain]

Created the module for A* in navigation and started the code. The next step is to communicate with the database to get sensor data. the Cell object has been created but does not yet contain all the aspects that will be included, mainly because I didn't read the bit about GPS location in the issue. on that note the the current code does not include the function that it will be called from, i.e. the given example. Some additions that i thought of are written as comments at the top of a_star_algorithm.py.