Go Down

Topic: Need Help for Genetic Algorithm (Read 382 times) previous topic - next topic

RobotMaker12

Hello,

I have recently decided to take up a genetic algorithm project with Arduino...

I want to write a program that would make a robot  learn to navigate, move, etc. I have searched Google and the forums but nobody seemed to even give a simple sample program. Can somebody please help by giving some sort of path for me to follow?

I hope I'm not asking for too much...

Thanks

Caltoa

That would require a lot of memory. It is something to calculate on a computer, or perhaps the Raspberry Pi.

PeterH

I think the general approach should be to understand what a genetic algorithm is, and then decide how that will work within the context of your project (presumably it's an algorithm which your project will use to do something), and then choose the genetic algorithm you intend to implement, and then select the hardware you're going to use, then find or write any code necessary to manage that hardware, and then implement your chosen algorithm in code. Finally test and fix, repeating as necessary until its good enough.
I only provide help via the forum - please do not contact me for private consultancy.

PaulS

Quote
but nobody seemed to even give a simple sample program.

Hmmm. I wonder why. Perhaps, because the program is NOT simple.

KeithRB

This is the simplist I know:
http://www.ro.feri.uni-mb.si/predmeti/int_reg/Predavanja/Eng/3.Genetic%20algorithm/_04.html

But the point about genetic algorithms is that the program does lots of trials and mixes the results of the trials genetically to determine the optimum. This works well in simulations and nature, not so well for your robot. Do you really want it to fall off a cliff to determine that that is a "bad" outcome?

mirith

I would look at Udacity's AI course.  I don't know if they cover that algorithm but its a good idea for how it would generally work.
That being said, the Arduino is probably underpowered to handle the AI.  It could act as the motor controller and you could connect Via bluetooth to a PC.

tgsuperspec

I believe you are using the wrong term here, GENERIC algorithms determine possible outcomes from specific situations by fuzzy logic and starcastic matrix algebra.

Asimov wrote about positronic brains which would be the ultimate Generic algorithm. What do you actually want to do?

If its a learn about environment you can study AI techniques on learning algorithms but again the maths is horrible and the Arduino would be vastly underpowered. An alternative is to look at the simply tile map used in many computer games since year zero
of platform games.  The ideas can be transposed into learning quite simply rather than as in the game the path is pre defined the player just has to locate it.

Unfortunately the fly in the ointment is the need to use recursive algorithms otherwise the code becomes unmanageable,  infact most AI has to be based on recusion (the calling by a function of itself.) read up on the towers of hanoi or factorial solutions.

Why recursion if robot is in a maze then it needs to check as a minimum 4 directions of travel  but if one direction offers possible route to an adjacent square then it has to check 4 directions in that square  If you code without recursion you need to store possible routes tried and backtrack-by direction reversal based on info stored using recursion as the recursive calls unstack the info needed becomes instantly available.

I built a robot 4 wheel drive car with a mega using the tile and recursive solution, I also plotted the map to sd card to avoid learning from scratch each time. The mega managed the maths but was slow to learn some of this was my doing as I wanted to folow the algorithm so I wifi linked to a IMac but most time was taken by the volume of computations 

Suggest you avoid learning and mapping have fun see what the arduino is capable of with simple avoidance detection and you own avoidance algorithm a standard technique for avoidance isto always turn in same direction when theres noway forward.

Its a victorian solution to a maze, you keep one hand on hedge at all times so you are forced to turn one way.

  8) 8) 8) happy coding..

Robin2


I believe you are using the wrong term here, GENERIC algorithms determine possible outcomes from specific situations by fuzzy logic and starcastic matrix algebra.


I don't know whether it should be "genetic" or "generic" - neither seems very informative. However I suspect it should be "stochastic"

However that's just an amusing digression ...

+1 for the rest of the Post.

This is a concept that will be hard for the human brain to figure out and describe in terms that could make an effective program on a powerful computer.

...R

KeithRB

No, "genetic" a class of algorithms that mimic inheritance and natural selection to perform optimization. I am not sure what he wants to optimise, but GA's work better for simulations.

OT Fact: They are really good for "think outside the box" optimizations. The example I like is the FPGA design that used an EM quirk:

"A field-programmable gate array, or FPGA for short, is a special type of circuit board with an array of logic cells, each of which can act as any type of logic gate, connected by flexible interlinks which can connect cells. Both of these functions are controlled by software, so merely by loading a special program into the board, it can be altered on the fly to perform the functions of any one of a vast variety of hardware devices.

Dr. Adrian Thompson has exploited this device, in conjunction with the principles of evolution, to produce a prototype voice-recognition circuit that can distinguish between and respond to spoken commands using only 37 logic gates - a task that would have been considered impossible for any human engineer. He generated random bit strings of 0s and 1s and used them as configurations for the FPGA, selecting the fittest individuals from each generation, reproducing and randomly mutating them, swapping sections of their code and passing them on to another round of selection. His goal was to evolve a device that could at first discriminate between tones of different frequencies (1 and 10 kilohertz), then distinguish between the spoken words "go" and "stop".

This aim was achieved within 3000 generations, but the success was even greater than had been anticipated. The evolved system uses far fewer cells than anything a human engineer could have designed, and it does not even need the most critical component of human-built systems - a clock. How does it work? Thompson has no idea, though he has traced the input signal through a complex arrangement of feedback loops within the evolved circuit. In fact, out of the 37 logic gates the final product uses, five of them are not even connected to the rest of the circuit in any way - yet if their power supply is removed, the circuit stops working. It seems that evolution has exploited some subtle electromagnetic effect of these cells to come up with its solution, yet the exact workings of the complex and intricate evolved structure remain a mystery "

Another good reference:
http://www.talkorigins.org/faqs/genalg/genalg.html

PeterH


The example I like is the FPGA design that used an EM quirk:


Wow!
I only provide help via the forum - please do not contact me for private consultancy.

Go Up