# A* algorithm for Arduino robot path planning

Im in the process of getting into robotics. I have decent experience with symbolic AI and am wanting to start off using symbolic AI strategies to give a wheel, arduino based robot some "intelligence". (later I hope to use neural networks, but baby steps). Anyways, I started researching various symbolic approaches, and I found the the A* algorithm is one that can be used, but this puzzled me. My experience with A* is that the problem needs to be fully observable for it to work, so I dont see how a robot could use it to solve a maze for example. Would the robot first need to randomly explore the maze, store all paths taken, then apply A* to find the optimal path?

Thanks for the help

• You may be interested in the D* algorithm and in general how many motion planning algorithms can be made efficiently "incremental" Commented Jan 13, 2018 at 2:50

You may find this example useful. I recently used A* for highway driving in traffic, driving at 50 mph and passing other cars.

https://github.com/ericlavigne/CarND-Path-Planning

The A* algorithm supports decision-making only in discrete problems. I discretized highway driving by only considering positions that are either in the middle of a lane or halfway between lanes and by only allowing changes in direction once per second.

Even with incomplete information, you can still create a cost function based on the information that you do have. A* can be used for guiding the exploration process, such as by considering "explore a new area" as a good result in your cost function. For highway driving, I don't know what the other cars will do even one second later, but I model their likely behavior and use A* to plan a route several seconds out.

• how would one represent and generate new states if using A*? I used A* to create a maze solver, each state was simply the person at a different spot in the maze. For a robot in real time, would each state be the robots position at a given instant of time? Commented Dec 25, 2017 at 15:17
• Here is a more specific link to discussion of state in the example I linked before: github.com/ericlavigne/CarND-Path-Planning#trajectory-state State can include whatever information about a robot's state that you care about. My state included four variables: s (distance along highway), d (distance across highway), v (speed along highway), and t (time in seconds). Commented Dec 25, 2017 at 15:24
• I think I get the idea now! The robot ill be using is a quadruped with arduino mega. Ive never programmed an arduino so it will be a new experience. Hopefully I can use A* to solve simple mazes to start off with! Commented Dec 25, 2017 at 16:24
• You also mentioned an interest in neural networks. When you're ready, two of my other projects can help you with that as well. One project detects lane lines and vehicles: github.com/ericlavigne/CarND-Detect-Lane-Lines-And-Vehicles The other project controls a car's behavior based only on examples of images and what behavior is expected for each image: github.com/ericlavigne/CarND-Behavioral-Cloning Commented Dec 25, 2017 at 16:38

Well, if you want the optimal path to be found over the entire course, irrespective of the planner you use, you will require the map before hand.

Although, the issues with A* are that it is meant for a Holonomic robot (or entity for the path is being planned) and also the one you have encountered, its ease of implementation makes it so popular for planning. There are quite a few other planning algorithms which circumvent these issues. Take a look at RRT (Rapidly-exploring Random Tree) and other similar algorithms for that.

If you wish to use A* only, and do not have prior information about the entire course, may I suggest you try using locally optimal path to navigate by generating local goal points for the observable map at every certain instance of time.

• Minor correction: A* is a graph search algorithm. There is no requirement that the graph be created by a holonomic process. You are probably thinking of a very specific example of using A* on a grid. A* can be used much more widely by allowing the nodes to represent whatever states would arise by applying a finite list of control options to the current state for one more timestep. Commented Dec 25, 2017 at 15:37