next topic »

[on:]

Hi
I am trying to find an algorithm so that my bot finds its way to the centre avoiding the obstacles in way.....
sample track is http://tinypic.com/r/w7ivwi/4
the bot gets travel only once. so recording paths in trial runs wont work  :'(  it needs to travel from start to end in 1 go and fast not hitting any obstacles...
my current algorithm is right hand rule at the intersection but they seem a little too exhaustive way to go to centre...   is there some algorithm which can provide me with a faster time?
Thanx in advance  

[Reply #1 on:]

If you know the position of the obstacles: http://en.wikipedia.org/wiki/A*_search_algorithm

[Reply #2 on:]

nope.... obstacles position dunno   else i could have hard coded it any other suggestions?

[Reply #3 on:]

You're in for a real treat if you're trying to find a solution to a maze without a left/right rule, or multiple trials.

Are you allowed to backtrack? Then you could 'remember' each decision made and try the other one(s) if the current did not lead to the target.

[Reply #4 on:]

AlphaBeta was soooo close:

http://en.wikipedia.org/wiki/D*

Haven't tried this one yet though, can't say how it works.

[Reply #5 on:]

yup i am allowed to back track   I have made it like that... so if my bot finds a obstacle it puts a negative value on that path which tells my bot never to go there again. so when it reaches junction it will choose an of the other paths...   but still i feel its a rubbish algorithm... takes too much time... is there an faster solution. becoz my destination is always center... and i face another problem too..  
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1254793692

[Reply #6 on:]

now these guys have changed the rules. now they tell the bot can go 4 multiple runs around the track for 7mins ie) it reaches the destination in middle and bot must trace back to starting position automatically (then timer resets) and then choose the shortest path. how do i do that?
i am using this as reference http://www.pololu.com/file/download/line-maze-algorithm.pdf?file_id=0J195
problem is that i only have around 2.5KB to code this storing the path and retracing and find the shortest path so can it be done in this space? rest of my code took around 4.7KB i only have a total 7.1KB  :-[

[Reply #7 on:]

You should have plenty of space to implement a backtracking search in that space.

Each desicion need only two bits.
B00 = NOT_SET
B01 = left
B10 = right
B11 = straight ahed

This means you can store four desicions per byte, thus you have room for about 9600 decisions

[Reply #8 on:]

I didnt understand... 2 bits? is it a datatype?   B00 ?

[Reply #9 on:]

http://en.wikipedia.org/wiki/Byte
http://en.wikipedia.org/wiki/Bit

B00 is the same as 0
B01 is the same as 1
B10 is the same as 2
B11 is the same as 3


Keep asking if it's still unclear

[Reply #10 on:]

Ok. I understood that. How do I set individual bytes? (or preferrably bits :-/) Is there a data type for managing bytes, other than char?

And this sort of looks like assembly programming. Can I do assembly programming with arduino?

What is the size of an int variable. Is there any smaller data type like short int?

[Reply #11 on:]

http://arduino.cc/en/Reference/Byte
http://arduino.cc/en/Reference/BitRead
http://arduino.cc/en/Reference/BitWrite
http://arduino.cc/en/Reference/BitSet
http://arduino.cc/en/Reference/BitClear