3
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ You may be interested in the D* algorithm and in general how many motion planning algorithms can be made efficiently "incremental" $\endgroup$
    – jnez71
    Commented Jan 13, 2018 at 2:50

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Remus Ventanus
    Commented Dec 25, 2017 at 15:17
  • $\begingroup$ 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). $\endgroup$
    – Eric Lavigne
    Commented Dec 25, 2017 at 15:24
  • $\begingroup$ 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! $\endgroup$
    – Remus Ventanus
    Commented Dec 25, 2017 at 16:24
  • $\begingroup$ 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 $\endgroup$
    – Eric Lavigne
    Commented Dec 25, 2017 at 16:38
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Eric Lavigne
    Commented Dec 25, 2017 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.