Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?

Genetic Algorithm Generated Lego Bridge 77

mvicuna writes "[according to a Yahoo News story] Scientists programmed a computer to use "evolutionary steps" to build a bridge made out of Legos. Is this a Lego story or an AI story? :> " A good question. Some of each, perhaps? And they apparently did it without 1000 Pentiums, too. Here's the home page of the project itself. Tres cool stuff!
This discussion has been archived. No new comments can be posted.

Genetic Algorithm Generated Lego Bridge

Comments Filter:
  • by Anonymous Coward
    Well, it's a little more sophisticated than that. There are a lot of different ways to combine bricks, way too many for exhaustive search. What they've done is come up with a genetic-type encoding of a particular structure, generated a bunch of random structures, tested their fitness, and then crossed the most fit with each other to make new designs. This allows you to find effective designs in far fewer attempts than exhaustive search.
  • by Anonymous Coward
    good point, it isn't clear what exactly the role of randomness is in the kind of optimization problem at hand... but I would suspect that what they really want to do is experiment with the characteristics of GA's rather than try to build better bridges.

    At least, giving the GA this kind of problem will be informative in that it will show how well a GA (a search algorithm) can be adapted to a problem from the physical world. In many cases, optimization algorithms are used to perform relatively simple, brute force tasks. The strength of a GA is that it can hit upon a few good building blocks in the beginning and evolve a solution in much less time and with much less effort than other kinds of algorithms.

    I think I see your point here, though. What is there about the "bridge building problem" that can allow for a direct measurement of a GA's strengths (relative to other kinds of search algorithms)?

    Maybe the computer optimized at various levels, all with GA's... i.e., what kind of blocks, how much redundancy in connections, etc.

    There must be something that we weren't told in the article which is specific to this particular problem domain that makes a GA's performance particularly interesting....

    Any thoughts, anyone?

  • a genetic algorithm is a search algorithm which is often used to perform optimization... given a space of possible 'solutions', the algorithm tries a group of possibilities, evaluates them according to some kind of fitness criterion, and then uses genetic machinery (mutation, crossover) to create the next "generation" of possibilities.

    All in all, it can be a relatively messy search path. What makes a GA powerful is that it can sometimes find a solution very efficiently compared with sim.annealing, hillclimbing, etc.

    People don't seem to understand that using GA's in engineering is only as effective as the fitness criteria. The GA is just a dumb search algorithm, and it doesn't know if it's found a good solution unless you tell it what a good solution is beforehand.

  • :)
    Lego comes from Denmark...
    It means 'play well'...

  • As a grown up kid who grew up with legos (before all the specialized peices for the models came out), and a parent:

    seem to be manufactured to less exacting tolerances, because they tend to fit very loosely together, to the point where they're no better off structurally than stackable building blocks.

    Lego structural integrity:
    Some wicked-strong members can be fabricated by laminating staggered flat peices. Although you're somewhat limited geometrically, those 1-wide 6 to 8 long blocks can be used to build walls, to connect two of these flat laminates, to create fairly strong tubes. As long as the joints remain staggered, and reinforced, these can be fairly strong.

    "The number of suckers born each minute doubles every 18 months."
  • This got moderated UP?
    --Conquering the Earth Since 1978.
  • This appeared as a side-bar to an article about circuits designed using genetic algorithms. Unfortunately, the article isn't available online, but you can see the references here [sciencenews.org]. The article itself reported on using FPGAs to evolve an electronic circuit.
  • Give 1000 monkeys 1000 years and they will write Shakespeare.

    Give a computer a genetic algorithm and it will build you a bridge.

    Give a geek open source software and they will start a revolution.


  • Yeah.. I agree that the "Let's Beowolf it!" response to every /. article is getting a tad bit old...
  • I'm curious how good a design it came up with. How do you test the structural soundness of a lego bridge? What do you define as structuraly sound anyway? If it supports it's own weight? If I can stand on it?
  • 1) Godel's Incompleteness Theory
    2) The Church/Turing hypothesis
    3) Heisenberg Uncertainty Principle
    4) Taoism (or Zen Buddhism if you perfer)

    Aside from those things listed, what we would consider intelligent is based on common sense, which, as any AI researcher can tell you, is not so common for a computer. We the have the experience of years of aquired problem solving skills under our belts before learn common sense (which some of us never do). Add to that at least 4.4 million years of genetics to get our brains to the point where they can aquire those problem solving skills, and you have a monumental task on your hands to develop Artificial Intelligence.

    I think AL techniques will come closer to Intelligence then AI techniques in the long run.
  • Artificial Intelligence refers to the search for a human generated algorithm that will simulate intelligence on a computer. (notice I said simulate) I, for one, think that this is an impossibility.

    Artificial Life is the use of evolutionary techniques to allow a computer to "build" a program itself and refers to Cellular Automata, Genetic Programming, and Evolutionary Computing. Neural Nets are included in this category also. Artificial Life techniques use concepts found in biology to solve problems on computers.

    It's interesting that Neural Nets are all the rage now, since they have been around since the early sixties. AI Researchers ignored them to focus on find that human defined algorithm. The basic concept of neural nets hasn't changed much, except the bit about timing of the pulse being critical. It's such an obvious thing, but it allows the neural net to store an order of magnitude more information then one that doesn't depend on timing.

  • Yes, but doesn't Lego sue anyone who manufactures pieces that interconnect with theirs? Not very open source, is it?
  • My advisor and I used genetic algorithms to do optimizations for an NP-complete problem which arises in building certain types of genetic sequencing "chips" (the paper is here (postscript) [sunysb.edu]. This is a practical application which seems much harder to me. Our optimizer ran on a *single* Sparcstation 5 in a matter of minutes.

    The Intelligent Robotics Laboratory [vanderbilt.edu] at Vanderbilt University (where I spent a summer) was doing things [vanderbilt.edu] back in 1994 that were much more difficult to do than this project without having to resort to GA's (which are generally considered by real algorithmicists to be a last resort (it was in our paper cited above)). And neither of these were the "cutting edge" environments you get at places like CalTech, MIT, or some industrial labs.

    And, I wish I could give you a link (but I can't remember the fellow's name) to the research (which may have appeared on Slashdot) being done in simulating evolution in physical environments. The main researcher in question gave a seminar at my former employer (a company which does mathematical modelling of complex phenomena) a year and a half ago showing film clips of "evolved" computer "life forms" which solved physical motion problems in ways eerily similar to extant "real" creatures. Same lab (I've searched for 45 minutes now for a link or an old email about the presentation and am coming up dry so don't ask -- if I find it I'll post it) was doing visualizations of "evolved programs" where they were finding evolved (GA's) redundancies in coding operations similar to those found in actual natural DNA/RNA.

    So using 1000 pentiums to make a lego bridge via GA's is newsworthy? Bah! Gimme a break.

  • My advisor and I used genetic algorithms to do optimizations...

    It's late and it's been a few years. I meant simulated annealing instead of genetic algorithms. We looked at both and found SA better than GA for our particular optimization problem. Doesn't affect the post otherwise :-)

  • That the Ig Noble [bbc.co.uk] prizes have just been handed out; this seems like a prime contender...

    Not to say that the research is worthless, just as the biscuit dunking research could lead to new insights into starch liquid absorption. Demonstrating a new technology/algorithm with a lego bridge reinforces the general public's idea that science is somehow trivial (the "Wacky Boffins" view)
  • Artificial Intelligence refers to the search for a human generated algorithm that will simulate intelligence on a computer.(notice I said simulate) I, for one, think that this is an impossibility.

    What makes you think it's an impossibility?
  • It's been a long time, but I seem to remember a story being told in one of my Information Systems courses that went along the lines of:

    An group of engineers built a powerful supercomputer, meant to be totally independent of human control and interaction. One that would not be dependent on outside factors, and that could reprogram and enhance itself. One day one of these engineers decided to have a little fun, so he logged in and asked the computer a question, "Is there a God?"

    The computer examined whether there were any portions of its power or supply chain that were under human control any longer, concluded there wasn't, and spoke in a voice of thunder, "Now there is."

    Don't remove that reset button yet :)

    William X. Walsh
    Email: william@dso.net Fax:(209) 671-7934
    Editor of http://www.dnspolicy.com/ [dnspolicy.com]

  • Check out this site: genetic-programming.com [genetic-programming.com] they have quite a lot introductory information and examples etc.
  • It's kind of hard to determine if the point you have found is a local maxima or minima when you are working with 3d graphs and irregular definition sets. A "look and solve" solution is only valuable when the problem is easy enough for a high-school kid to solve it, and then you hardly need a computer.

    So I don't believe that is a workable solution at all. There are naturally nice algorithms for these types of problems, and they can be used, to some extent, by computers as well.

    GA are not generally used to solve easy functions or similar trival problems. Rather they are used when no other solution is apparent. You are naturally not guaranteed that you get the best solution, but as long as you get one that is "good enough" then that is sufficient.

    An example of such a situation is where they made a filter circuit (highpass or lowpass, can't remember) with roughly 40 components. This problem is virtually insolvable with general algorithms, but genetic algorithms saved the day. (They did also create some "dead parts" of the circuit, that were removed. Apparently latent genes are found here as well. ;-)
  • No, you were talking about Unix. =P At last check, *BSD, Linux and Solaris can do this too. But then again...
  • I haven't missed one at all. I mention Unix, people think it's a program. It may not be nessesary, but it exists.
  • In the image gallery [brandeis.edu] there is a picture of the actual lego bridge.
  • A) General public/media think it's just dirt.
    B) Scientists and engineers play with dirt every day.
    C) Made from small, re-usable molecules that plug together.
    D) There's lots of dirt to go around and everyone can build mudpies together.
    E) No rules other than physics and making sure mommy doesn't spank you when you come home dirty.
    F) Who would want to play with dirt instead of earning money for their proprietary bricks?
  • it's incredibly hard to build a viable robot with legos. Legos really aren't structured to make vehicles. I was part of a team for my school that made one. All we had to do drive across a board and collect balls.
    But in order to make it turn you have to write that in the program, and you program has to use dead reckoning because there is no lego gps(or something similar). you also have to worry about hitting the other robot on the field. and a lego block can only use 3 motors and 3 sensors(well it can atually use like 6, but to do that you must have two motors moving at the same time, and programming for that gets downright nasty at times.
    Also if you collide with the other robot your program can get off and you will end up wandering all over the board. Which is fine, unless your points don't count if you aren't at a certain point when you finish.

    Anyway programming for legos is hellish work. And you should have respect for people who can do it. It isn't easy, and if you think it is i encourage you to try it.
    char *stupidsig = "this is my dumb sig";
  • This is a pretty old application. I remember the guy who inventing thinking machines corporation writing a program that taught itself to match colours...matching paint chips to actual paint is pretty difficult..this thing could do it automatically and "learnt" from its errors using a GA if im not mistaken. TMC is bankrupt now of course...

  • Actually, the solution was the "best" in the fact that it fullfilled all the requirements given. The computer has no way of putting further requirements on its construction, so anything that solved the problem would be equally "best" for it.

    Had they mandated that the bridge should be able to hold a weight of so many grams at any point once finished, the simulation probably would have ran longer - and resulted in a "better" bridge.

    /. is like a steer's horns, a point here, a point there and a lot of bull in between.
  • I knew I read this story a while ago... here. [sciencedaily.com]

    Hmm. Could this be like genetic programming, but computers could design themselves to make generations of improvement incredibly quickly? If so, that'd be pretty scary. Once computers have that much control over themselves, we would begin to lose some. Granted, control is something of an illusion, but it's one I like to have.
  • The page has several interesting links to projects they've been working on. A few even include playable games (a kind of hocky game and tron). These people know their stuff :). (the tron game is still kicking my butt even after an hour -- the hockey game I can beat on occasion however, but some of those AI dudes kick my butt...)
  • I probably ought to note that I really really suck at the game, so someone who can play it well might not have as many problems as myself ;).
  • To grow up and be paid to play with both computers AND Lego Bricks? Oh, man. Heaven!

    Two meters is pretty impressive for most any Lego structure. I wonder what types of bricks it used; long flats, long full-heights, or some combination? (Actually, this would be a good job for Duplo blocks, since they're designed to take abuse anyway and they work perfectly with "regular" Lego bricks too.)

    I sure hope the computer was programmed to know the difference between imperial and metric measurements, though...

  • Cool! I should get that, it'll be a far cry from KTron, which regularly commits suicide on the Expert level.
  • These computer(s) were given a set of criteria, and a goal to complete, as the article says. This means that the computer was told what the bridge was supposed to look like,

    Wrong, it was NOT told what the bridge should look like. It was told 'You have these pieces, make something from here to there that won't fall down'. And it did.

  • pictures look interesting to say the least! But i would be really interested in knowing how they were implementing the GA. As in how was each generation chosen, mutations, and matching up!

    for someone who does not know much about where GAs are being used... are there any REAL_World applications that use them. I know that some while ago there was a database engine that was trying to use a form of neural nets! Could it be
    po9siible to use some GAs to build data miners ?
    Interesting things too come.... but now i return to working on algorithms (HW) :)

  • Make a better mousetrap, and a computer genetic algorithm will build a bridge to your door.
  • What are humans, then? If these people took fast computer, gave them a specialized program, and called it intelligence, then why aren't human brains simply advanced computers. Ones that have evolved for thousands of year...
  • What these people have done, is not create a form of intelligence, as they claim, but rather simply use a computer for what is what meant to be. These computer(s) were given a set of criteria, and a goal to complete, as the article says. This means that the computer was told what the bridge was supposed to look like, and what it could be built out of... It was a simple physical simulation, and unless they were using 286s, for the whole thing to take a day and a half, means that the computer simply tried the lego blocks in every position possible. It then simply chose the one that was most effective...

    I once saw a program called "Interactive Physics" in which you would set up a situation, and the computer would immediatly and accurately simulate the situation for you; this ran even on a 100mhz Macintosh. This 'intelligence' is nothing more than a constant random generation of scenarios, and then input of this scenario into a physical simulation. Its not intelligence, its computing.

    "The more you know, the more you realize how little you know."

  • I had thought that there was an error in the media, but perhaps you're right, and the simulation's requirements were met at the point the bridge hovers over the other side. This perhaps could be rationalized by allowing a straight, narrow pillar support it. But that ignores the resource cost of such a pillar.

    Which leads me to agree that there should be an additional "touch the other side" requirement.
  • As wave after wave of human test subjects rate the faces on attractiveness, a face evolves that matches most people's conception of beauty.

    About five years ago, Time magazine ran a story on ethnic diversity. The photo on the cover was constructed by morphing images of people from a variety of ethnic backgrounds. I don't think Time necessarily intended that the resulting photo should be of an attractive woman, but I expect that fact didn't hurt their circulation that week. To me, she looked a bit like Terry Farrell.

    Unfortunately, I don't remember the exact publication date.
  • Although all they did was solve for a straight line.

    Seriously, what I'd like to see is legos that can follow instructions to build a particular type of bridge.

    Set up a server that contains the design. .
    Use seed legos to attract the blocks to their positions.
    Have them send their position to the central server.
    When a block is in place set some surfaces of the placed block to repel and some to attract.
    Virtually every lego will be forced into a position within the design.

    I think I'll put this in my personal prior art database.
  • After watching the animated .gif of the bridge building process I have a stupid question: What was the holding strength of the legos in the computer model?
    I believe them when they say that the end result was structurally sound, but, as someone who has played with a lot of legos, those expansion bits were simply too far away from the base to hold together.
    Unless they were glued, those legos would have fallen apart.
  • First off, while you can get to it from the links above, the impatient among you can click here [brandeis.edu] for an animation (animated gif) of the bridge building process.

    Second, after watching that, can someone explain to me how, in this case, GA show any advantage over boring old Newell and Simon means-ends analysis? I mean, in general, yes, I see the advantages of GA, but this looks like a case for "identify your situation", "identify your goal", "identify an operator that might reduce the distance between your situation and goal", "apply operator", "repeat." Why let randomness figure into it?
  • let go my lego
    a day and a half to design a bridge. bah humbuig I can do it in a minute with three lego blocks:)

  • There was an NYT article like 6 mo. ago about the behavior of ants simulating cellular automata. When the ants approach an obstacle, like a gap between two important branches of trees, they will actually evolve a bridge using simple where-should-I-be-in-relation-to-this-ant tactics. When the bridge is formed, the rest of the ants march over the bridge and then the bridge collects itself back on the other tree.

    Cellular automata with genetically-programmed instructions could prove to be a very important field in ten, twenty years.

    I wish I could find the article, but I don't quite have the time.

  • how about first evolving their bridge as they did
    requiring it to physically touch the target zone (theirs seems to just have to float over it?)
    next using this result as input for evolving towards symmetry
    next work towards minimum number/size of elements
    next make it load-bearing at the center
    and i think you'd be pretty close to a 'real' bridge,not?
  • And they do it again!
    Wow! Amazing!

    I grew out of legos when I was 8 years old, and so did all of my friends, and everone I knew (untill last week when I found one in the backseat of my friends Plymouth Satalite, but thats another story).

    Anyway, how hard can it be to figure out how to connect pieces of plastic together to create anything?

    So they have created a program that can connect legos together to form a bridge. So what? Did the computer design the bridge itself? Did it say to itself "I want to build a bridge, I want it to look like "insert generic bridge name here", because that is a pretty bridge."?

    Thats the real feat, instead of creating something that dosent need to take a series of orders, or design specefications, to make something. I will be truely shocked when they actually make something that can understand beauty, not just archetecture, or art, not just brushstrokes.

  • good point, it isn't clear what exactly the role of randomness is in the kind of optimization problem at hand... but I would suspect that what they really want to do is experiment with the characteristics of GA's rather than try to build better bridges.

    Having worked in an optimisation methods research group, I tend to agree.

    I think I see your point here, though. What is there about the "bridge building problem" that can allow for a direct measurement of a GA's strengths (relative to other kinds of search algorithms)?

    I haven't read any articles from the group, but my guess is that viewing the sequence of bricks added as a "gene string" might make LEGO constructions an obvious task for genetic algorithm optimisation.

    Can anyone tell me what information the elements of the strings contain besides the type of LEGO brick? They have to encode where the brick is placed relative to the previous addtion, otherwise almost any mixing of two strings will result is an unusable design.

    This seems to be an appropriate time for a plug for LDraw [ldraw.org] - a free (beer, not code) program for drawing LEGO models.

    http://www.newscientist.com/ns/971115/features.h tml

    Further reading: A collection of Adrian Thompson's papers is posted on
    his Web site at

    http://www.cogs.susx.ac.uk/users/adrianth/ade.ht ml

    Microsoft funds software that writes and fixes itself

    http://www.the-times.co.uk/news/pages/sti/99/08/ 22/stiinnnws01003.html?1902395

    Evolving A Conscious Machine By Gary Taubes

    Virtual Mathematics
    http://www.labs.bt.com/library/cochrane/papers/v irtualm.htm
  • >Actually, the solution was the "best" in the fact
    >that it fullfilled all the requirements given.
    >The computer has no way of putting further
    >requirements on its construction, so anything
    >that solved the problem would be equally "best"
    >for it.

    No. That's plain and simply not how GA's work.l

    They evaluate solutions based upon a fitness function, and choose some from among the solutions with higher fitness to "breed" in some form to get the next generation of solutions.

    In some cases, there may be a known and reachable maximum fitness, but this is the exception, rather than the rule.

    I'd be surprised to see "makes it all the way across" recieve full fitness. More likely, the number of bricks should be included, perhaps the width of the bridge at the narrowest point, etc.

    GA's are not (usually) used to find "a" solution, but the best reachable solution.

    I should note, though, that GA's are susceptible to local maxima; once one is reached, it may be difficult to change to the global optimum. However, there are techniques that address this problem in a wide variety of cases.
  • Hmmm, interesting.

    But Terry Farrell is (or has the looks of) a standard Western Caucasian female. Where's the "ethnic" bit, outside of the Jadzia lineage that is? :-)
  • What's that tube of Superglue doing in the corner of the picture? ;-)
  • Give computers a worldview and they'll see us as rivals.

    We have to go there, but let's go prepared.
  • Note that the bridge that was built (the end point of their problem) is merely the first point in the solution space.

    If a *real* bridge was desired then the solution space could be populated more fully with many more GA-generated solutions, and then searched using conventional AI techniques for points satisfying a heuristic based on other criteria, eg. no excess material, smoothness of form, and so on.

    Alternatively one could add these criteria to the GA survival metrics. This would slow down evolution dramatically because the probability of survival of offspring would be drastically reduced, but it would deliver "real" solutions directly.
  • Although methods that don't get stuck in local minima despite using a worm's eye view of the world are valuable, the best answer is to use a bird's eye view instead so that local minima are directly observable for what they are. (The "view" is in solution space, ie. it doesn't necessarily have anything to do with the usual 4 dimensions.)

    That's what humans do. For problem spaces a little smaller than we are, we actually supply the bird's eye view directly. For problem spaces much smaller or much larger than ourselves, we create mental models and plan our solutions within our mental bird's eye view of that model space.

    Machinery can be made to do that too, although the overall problem belongs to Strong AI and is difficult (an understatement) in its most general form. There's no reason why this approach can't be used without much difficulty within small problem domains though, in which "full understanding" can be programmed quite simply using a good old-fashioned expert system.
  • Actually, craw was right in part. The only reason why GAs don't usually get stuck in local minima is because of one of two things (or both): either the ancestors live in different valleys in the first place and therefore part of the genome will always have a worldspan greater than any local minimum, or else the sensitivity to mutations is set such that the GA can break out of the largest expected local minimum.

    If the original ancestors come from the same valley, and there is no other mechanism for inserting external genes, and mutations do not create solutions outside of the parameters of the original genome then there is no possibility of escape from the local valley. The main reason why this is rare is that mutations are not usually limited in this way, which is why craw was more or less right.
  • Leading off a number of contributions in this thread, does anyone here working in GAs/GP today know of anything approximating a possible "information mutation theory"? Anything that relates to combination or transformation of information descriptors or of domain parameters would be of interest.

  • Linked off the "1000 pentiums" story re Genetic Programming, the Salon article says:

    Recently, researcher Lee Spector, an associate professor of computer science at Hampshire College in Massachusetts, used genetic programming to create a fast algorithm for evaluating data structures known as and/or trees. The GP-evolved algorithm was faster than any created by humans and led to the discovery of a new quantum rule.

    If anyone thinks that Terminator/Matrix/Borg scenarios are totally unrealistic, they just don't understand the ability of GAs/GP to go beyond human potential. Our capabilities occupy just one local minimum in the solution space. AI machinery won't be constrained to that small valley of possibilities, as the research highlighted in Salon shows.

    And on a lighter note:

    The Faceprints project uses genetic programming to study human perceptions of physical beauty. Human test subjects are presented with several computer-generated images of faces. They vote on which faces are most attractive. The faces that the test subjects consider most attractive are crossbred, using GP techniques. As wave after wave of human test subjects rate the faces on attractiveness, a face evolves that matches most people's conception of beauty. The "most evolved face" in the Caucasian Female category is a green-eyed, Teutonic vixen [nmsu.edu] who would not be out of place on "Baywatch."

    Hmmm .... :--)
  • Yes indeed, and we can see dead parts aplenty in the Lego bridge.

    Nobody was talking about bird's eye views for "look and solve" though, but for guiding worm's eye view-based searching out of local minima that are not perceivable in the dimensions of the worm's eye search space. It's not a first-order constraint, just second order.

    As to the value of a bird's eye view, it is subject to the same rule that governs the success of worm's eye views in searching: a bad evaluation heuristic produces bad results, by definition and in practice too.

    What this means is that you have to get your heuristics right when producing your success metrics in both views, and if you don't then success is not likely, in either one.
  • Yes, their model parameters can't be sound. Real Lego is nowhere near that good.

    However, that doesn't invalidate the work, as reducing bond strength could be expected to modify only local constructs, not progress in the direction of the distant goal.
  • As opposed to the naysayers who have already posted, I think that this work is very useful and difficult. As far as I can tell, they developed a system that, knowing the physical properties of legos, found a way to span a defined gap with no external support other than the initial lego. On the surface, this looks silly, but by implementing an "intelligent" algorithm to do a fairly complicated task is a good thing in my book. Though this is one of many small steps, it will help to further the progress of intelligent machines.
    Gregory J. Barlow
    fight bloat. use blackbox [themes.org].
  • Yes, but your missing two points the general public doesn't think Unix is a toy (assuming they know wtf unix is) and the whole play nice thing isn't generally nessesary in the Unix world. So the answer then is No
  • A major problem with non-linear models is that one can get stuck in a local error minimum of the solution. To get out of these minima, one needs to seriously perturb the model parameters. In a genetic algorithm this is done by mutations.

    This is incorrect: mutation fulfills a very different function. The crossover operator allows intermediate solutions to be generated which will hopefully break out of local minima. Genetic algorithms and genetic programming are population-based optimisation methods: the initial population will hopefully span the entire search space. Thus by generating intermediate solutions we will break out of local minima. Mutation is usually (in sensible GAs) small scale, and consequently causes us to search the area around current solutions. If mutation is too large then the algorithm becomes random search.

  • The problem ofcourse with the task is that the descision on a structure has to be made without testing, i.e. the testing process has to be abstracted, which is where I see the potential for advance coming in, the first steps towards machines with actual or simulated abstract thought processes, this being an admittedly primitve and slightly less abstract example of these processes. But it's a start!
  • by craw ( 6958 ) on Saturday October 02, 1999 @08:11PM (#1643056) Homepage
    The Genetic algorithm is a means of solving a non-linear inverse problem; another notable method is simulated annealing. In the old days, the Monte Carlo method was used; Monte Carlo is where the casino are where all solutions are a matter of chance (hence, try them all). Start with an initial model, then incrementally move to a better solution. In a non-linear model, one perturbs the parameters then checks to see if the solution is better than the previous one. In a linear model, one can compute the correct direction to go by using the invariant derivatives of the defining mathematical model.

    A major problem with non-linear models is that one can get stuck in a local error minimum of the solution. To get out of these minima, one needs to seriously perturb the model parameters. In a genetic algorithm this is done by mutations.

    It has been a long time (in a galaxy far, far away) since I took a statics engineering course. But it would seem to me that a critical aspect would be the configuration of the starting model. Additionally, a lego bridge is a fairly simple geometry/model. Remember, the concept of an arch bridge was figured out by people without computers.

  • It had to design a structure that could be built from one side of a gap to the other. In other words start building at one side, and eventually reach the other, without anchoring to anything but the top of the first side, and without any additional supports during construction.
  • by ftobin ( 48814 ) on Saturday October 02, 1999 @07:45PM (#1643058) Homepage
    This has more impact than most people realize. It goes way beyond legos. The ability to connect the 'here' and 'there' is essentially what every problem is about. One assesses what one's current knowledge is, and through various connections of this knowledge, one assertain rules for getting closer to the solution. If this is too much of a vague statement, let me try a more concrete example. The computer is given a programming language, and told of each function's syntax, purpose, etc. Next, the computer is given a task, such as 'build a system which does blah blah blah', where blah blah blah is some sort of task that would generally be delegated to a programmer. This is essentially what this machine did; it was given a certain base knowledge (that of legos), and given a task which would normally be given to an engineer. Granted, the solution probably wasn't the 'best' (whatever that means), but that is most likely due to 'best' being ill-defined.

    As machines get faster and faster, AI will become much more powerful, as it will be able to analyze exponential problems (those that branch out, such as learning) within a reasonable time.

    We certainly do live in a great time to witness such events as this. :)
  • by JoeShmoe ( 90109 ) <askjoeshmoe@hotmail.com> on Saturday October 02, 1999 @06:58PM (#1643059)
    Think about it...

    A) General public/media thinks it's a toy
    B) A favorite among scientists and engineers the world over
    C) Made from small, re-usuable pieces that plug together
    D) Several people can play with it at once, working together to form a large, complex structures
    E) There are no rules other than the physics of how the pieces fit and the morals of playing nice with others.

    Now, was I just talking about a bunch of kids using Legos or a bunch of geeks using Linux?

    - JoeShmoe

    PS - other noteworthy comparisons should probably be tacked on to this thread as a reply.

    -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= -=-=-=-=-=-=-=-

I've noticed several design suggestions in your code.