go_away

Author Topic: Algorithm Design class - project  (Read 2956 times)

0 Members and 1 Guest are viewing this topic.

Offline pomprockerTopic starter

  • Supreme Robot
  • *****
  • Posts: 1,430
  • Helpful? 16
  • Sorry miss, I was giving myself an oil-job.
Algorithm Design class - project
« on: September 07, 2008, 02:49:20 PM »
I have to do a project for my algorithm design class. Not sure what exactly is needed yet except that it has to be about an algorithm. I asked if A* or D* would be alright, and was told it would be.

Now I don't know anything about those two algorithms except that is has to do with path planning.

If someone could link me to some tutorials for dummies that you recommend on one of those two algorithms it would be appreciated.

Offline MadMax

  • Full Member
  • ***
  • Posts: 58
  • Helpful? 0
Re: Algorithm Design class - project
« Reply #1 on: September 08, 2008, 06:14:21 AM »
voila,
voila
et voila

All about A*, you can go really in-depth about this algorithm if you want to, I would advise you to do so ;)

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,657
  • Helpful? 169
    • Society of Robots
Re: Algorithm Design class - project
« Reply #2 on: September 16, 2008, 11:22:45 AM »
There are a few good links on the forum here too. Might be hard to find them tho, since I've never seen a search program that likes the * character . . .

Offline pomprockerTopic starter

  • Supreme Robot
  • *****
  • Posts: 1,430
  • Helpful? 16
  • Sorry miss, I was giving myself an oil-job.
Re: Algorithm Design class - project
« Reply #3 on: September 16, 2008, 11:24:46 AM »
The more I read about this algorithm, the more I notice that it's implemented if the target node is known. Good for mazes?

What if you don't know the target node?

What is a good pathfinding algorithm if you just want to find a clear path and thats all?

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,657
  • Helpful? 169
    • Society of Robots
Re: Algorithm Design class - project
« Reply #4 on: September 16, 2008, 11:31:51 AM »
Well, your robot would be wandering aimlessly if it didn't have a goal location. (clear path to what? :P)

Three goals:
Map an area, so you set unmapped locations as a temporary goal locations.
Find a hidden goal location, so you keep mapping until the goal is found (with another sensor).
Goal location is known, but obstacle locations aren't known beforehand. Find a clear path.

There is nothing wrong about redefining goal locations as your robot learns more about the surroundings.

Offline pomprockerTopic starter

  • Supreme Robot
  • *****
  • Posts: 1,430
  • Helpful? 16
  • Sorry miss, I was giving myself an oil-job.
Re: Algorithm Design class - project
« Reply #5 on: September 16, 2008, 11:39:44 AM »
well i guess my robot doesnt really have a purpose in life at this time, other than to be able to navigate around the 2nd story of the house, being able to go from room to room, and without falling down the stairs.

I guess it could be a wandering robot for now, or an exploratory robot.

So I figure If I can just make it find the clear path, and map out the room, then It can send any data back over my BlueSMiRF connection.


as of right now I just have a sharp IR mounted on a scanning servo, and a parallax ping mounted on the very front of the chassis pointing forward. I also have the two photosensors which are unprogrammed at this time.

What would you do with those sensors to make an exploratory robot? What sensors would you implement to improve its capabilities?

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,657
  • Helpful? 169
    • Society of Robots
Re: Algorithm Design class - project
« Reply #6 on: September 18, 2008, 08:46:06 AM »
Here is a goal for you. Have it map your entire room, then when its done, it goes over to your PC to request an upload of the entire map to your PC. Make it so it prints out the map to Hyperterminal. By looking at the map, you can see where the errors are.

That's pretty darn challenging because you have to devise ways to defeat encoder drift. But if you can do that, then its ready to explore larger areas like your house. Start off with the basic wavefront algorithm, then you can improve the algorithm as you get the hang of it.

Offline Webbot

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 2,132
  • Helpful? 108
Re: Algorithm Design class - project
« Reply #7 on: September 18, 2008, 04:53:27 PM »
There is nothing wrong about redefining goal locations as your robot learns more about the surroundings.

You could even make the 'goal' to find another robot which is just aimlessly wandering !
Webbot Home: http://webbot.org.uk/
WebbotLib online docs: http://webbot.org.uk/WebbotLibDocs
If your in the neighbourhood: http://www.hovinghamspa.co.uk

 


Get Your Ad Here