A Graphing Problem

I did something similar once for a physics project, where each node represented an atom... you need to clarfiy one point first - you are going to have to have some measurement of how inaccurate a given situation is, so that you can compare it to another one - the mean square deviation from the optimum would be a fairly common approach.

In that way, it looks a lot like a bunch of springs which can be allowed to find their lowest energy point.

However, they will find lots of local minima which aren't the best solution overall. You can get around that by trying a few tens of thousands of random initial conditions, or by applying random moves to random nodes once in a while to jiggle it out of little holes it finds. If it needs to be real time, you can just accept that a the first local minima you find is probably good enough :o)

Yes there are a few images that ping my mind on such a problem :

- That's somehow the opposite of the Delaunay triangulation. But I see no trivial connection between the problems in details though.

- Yes GA may work. I am not expert enough to see if convergence conditions are met. Intuitively I would say yes, imagining that you have another algorithm to give a quick guess of the initial positions. Then try the AI forum.

- Energy minimilization. Else I remember physics interactions used to solve complex graphical problems. Set repulsive and attractive (polynomial fractions) forces between pairs of nodes and see if you end up with a blanced state. Each pair is stable when the distance is the one you target. So surely the whole system is stable when each pair is close to its balance point.

Certainly the last is the most relevant track to follow.

The idea that you both had relating the problem to physics is very interesting and exactly the kind of twist I was looking for. As for the way to measure the desired from the actual, I was just assuming I would be using the sum of the RMS values for each constraint.

One thing I am worried about is how many local minimum there might be. Did you find this to be a problem in your physics project with atoms? I guess it's going to depend a lot on the constraints and how possible they are. As long the local minimum are all generally the same, or represent the smae pattern rotated, transformed, etc, that is ok. I am trying to use this visualize all of the distances between nodes and where groups form, etc. The goal is to have more of a visual representation of the clustering of nodes, as long as the information presented by local minimum are consistant, they are acceptable.

Any other ideas/comments/suggestions?

Thanks so far!

Dwiel

well, your problem differs from that with atoms in that for me every node wanted to be a particular distance from every other one, but didnt care very much about ones which were a long way away (yes, atoms are weird). Local minima included various anomalies that show up in real life crystals, like gaps, sheers, extra atoms squished into small holes...

I suspect your most likely issue will be things getting 'tangled'.
Imagine all but one node has settled down nicely. That one is attached to 4 others which are arranged in a tetrahedron. It would like to sit in the middle, but it is outside and it finds that the 3 nodes nearest it prevent it moving inside (there is a small increase in energy on the way through - it is at a local minima).

You could let it reach the minima, then look for the node with the worst RMS and simply scan space in a regular pattern, and 'teleport' it to the lowest energy point you see. If all the springs are equal length, this is simply the average position of all nodes to which it is attached. Then let the system relax, then repeat, untill you get below some threshold. You could even just ditch the whole physics thing and do this from the start. I think you would end up in a pretty good position with very few problem cases.

Experiment. This is going to be one of those systems where the best approach depends on the kind of input data you have.

Quote:

Original post by Squirm Experiment. This is going to be one of those systems where the best approach depends on the kind of input data you have.

Thats kinda what I was thinking. Which is a problem because I am afraid my data is going to be very diverse. There are also going to be just as many constraints between distant nodes as there will be between close ones. The probobality that the constraints connecting a node will all be the same is about nil.

It might help if I told what I am graphing. Each node represents a program in my genetic programming system. The distance between two nodes is determined by how close of a match they play together. Say they are to be 'learning' to play pong. The programs which have close matches will be close together in the final solution. The hope is to display some interesting patterns about the population or a sample from it.

Anyway, I like the idea of reaching the local minimum and then either giving nodes with high error a random jolt or a calculated movement towards its actual minimum.

Thanks for the help!

Dwiel

I see that I wrote my last post simultaneously with Squirm, and published it right after. I did not intend to make any plagia.

Still I'd like to know by curiosity if you intend to choose a plain physical model or a GA with physics related evaluation functions.

I suppose a plain physics simulation is more performant, with the right force fields definitions and damping parameters to converge quickly. It's fully deterministic thus maybe faster than random throws in a GA. For the force functions, classical springs (k*Dx*Dx) or gravitationnal 1/r^n stuff ?

If the pure physical model does not work well with random starting positions, I would maybe try a quick first rush with a GA and a discretized problem. For instance try the combinations in a 16*16 grid. Then let the physics test the stability and refine the various GA solutions.

PS : I think the Graphic Gems collections treated a problem similar to yours, maybe the number 3 or 4.

The first thing I will try is simply using random starting locations, letting the springs (traditional force is directly proportional to the distance from equalibrium) converge. Then I will loop through the nodes and manually fix say 10$ of the nodes with the worst error. Manually fixing would probobly involve something like:

newx = (1 / Sum(wi, 0, n)) * Sum(wi * xi, 0 n)

where wi is the 'weight' of constraint i, and xi is the x position of the node on the other end. The same would be done. This in a way, takes a weighted average and should probobly be a fairly good guesstimate of where the abs minimum for that node is given that the others can't change. I would keep 'fixing' them and then letting them rearrange themselfs until the error stops decreasing.

I'm not sure how close that average deal will put the node to the abs minimum, but offhand, I couldnt think of a better analitcal solution to the problem, although I assume there is one...

Due to the fact that this system's purpose is for visualizing, some of the choises I have made, might very well be changed if alternate methods produce more meaningful graphs. One thing I was thinking about with conventional springs is that if there are a couple constraints that are very far away, the node will be biased by those much much more than others. I can see this being a poor quality for the system as well as a posible good one. It's simply going to take some trial and error.

BTW, how does my current algorithm sound?

I've been looking into something similar recently.

Try google for "simulated annealing" (something I remember from A.I. at uni) I think it's best described as a 'multi-pass jiggling algorithm' ;) with the added bonus of avoiding local minima.

[ed] This one is especially good.

Quote:

Original post by Tazzel3D (traditional force is directly proportional to the distance from equalibrium)

My mind is going, there is no question about it ... :) Sure. But anyway you can try various powers of elongations or distances to see which one is converging best. That's not the most painful part when ou can test a bunch of idea in a few mionutes by just adding a function of a few lines.

Quote:

BTW, how does my current algorithm sound ?

Modifying the weights conditionnally for the needs of your algo sounds good. But then apply a continuous transition in weight changes to keep your system balanced. But frankly that's a far too complex subject to see in advance if any idea is a really good one. Plus I don't have any feeling of physician. I am more attracted by more certain and predictable math ;)

Pls keep us informed back here if it works. I keep track of threads (GD bookmarks) for quite a while. It's not such a specific problem. I feel it is fairly generic. Any experiment is thus interesting.


Else n constraints (di), m outputs (xj,yj). Wouldn't linear programming (used in constraint solving for physics sim) solve the 'equations'. It's quite similar to your minimization algo, except the underlying theory is maybe more robust and documented on the www. Not so ez though.