Advertisement

AI method to approximate the maximum volume?

Started by June 21, 2011 01:50 PM
20 comments, last by willh 13 years, 5 months ago
Is the solution always a subset of the convex hull of the point cloud? If true, that would simplify the search enormously.
I trust exceptions about as far as I can throw them.

The first thing that comes to mind is simulated annealing. Start with a random subset of the desired size and then try changing a random point A in the subset by a random point B not in the subset: If the volume increases, accept the change; if it doesn't, accept the change with some probability that depends on how bad the change in volume is, and on a parameter called "temperature".

P(A -> B) = exp((volume_with_B-volume_with_A)/temperature)

I think if you lower the temperature slowly enough, the probability of ending up at the optimal solution is arbitrarily high. And if you rush it, you still get a decent approximation.

[EDIT: You only need to pick B from the points that are not in the convex hull of the subset. That's probably an improvement.]

What A Brain in a Vat proposed isn't even well defined. What do you do in sectors with no points?
[font=arial, verdana, tahoma, sans-serif][size=2]What does "arbitrarily high" mean here, exactly? The OP is asking for an exact solution, not an approximation. While it's true that the more annealing you do, the closer to 1 the probability of finding the optimal solution becomes, the time required to be reasonably close to sure that you've found the optimal solution almost definitely exceeds the time it would have taken if you did a brute-force search.

My "proposed solution" wasn't one. It was put forth as a question and was intended as one. While you're right that it's not fully defined (because I didn't bother, since it wasn't a proposed solution); and while I'm positive, even if it was fully defined, it can be shown to not be optimal, I think it certainly is a smarter solution than the simulated annealing, given that you were accepting non-optimal solutions. In particular, that an optimal solution would almost definitely include points from most "sectors", and that those points would likely be spaced farther from the centroid rather than closer, is common-sense that should probably be part of a proposed solution.[/font]

In fact, my question is very similar to the (smarter) question asked by Storyyeller.
Advertisement

Is the solution always a subset of the convex hull of the point cloud? If true, that would simplify the search enormously.

One problem with that is that N (being the number of points in your solution) could easily contain more points than the convex hull. But you maybe could show that one of the following must be true:
Either:

1. Every point in the convex hull is in the solution (in the case that N > the number of points in the convex hull)
OR
2. Every point in the solution is on the convex hull (in the case that N <= the number of points in the convex hull)

I'm not sure how you'd go about it though.
@A Brain in a Vat: If this is the case, then my already proposed method of calculating the convex hull and eliminating the points based on how much their elimination reduce the volume would work. But I'm not sure how to approach the proof. I guess you can use something like the sum of the angle around the points in the convex hull to decide if a point should be removed. If the number of points in the convex hull is less than the required number of points, you can simply choose other points at random since they won't influence the volume.

[font="arial, verdana, tahoma, sans-serif"]What does "arbitrarily high" mean here, exactly?

It means that if you tell me how high you want the probability to be (less than 1, of course), there is a schedule of cooling for which the global optimum is found with at least that probability.

The OP is asking for an exact solution, not an approximation.[/quote]
After rereading the OP, I have to say you are probably right. His asking for an "AI method" confused me into thinking he meant a heuristic method.

While it's true that the more annealing you do, the closer to 1 the probability of finding the optimal solution becomes[...][/quote]
Wait, so you did know what "arbitrarily high" meant...

[/font]

[quote name='A Brain in a Vat' timestamp='1308685009' post='4826113']
[font="arial, verdana, tahoma, sans-serif"]What does "arbitrarily high" mean here, exactly?

It means that if you tell me how high you want the probability to be (less than 1, of course), there is a schedule of cooling for which the global optimum is found with at least that probability.

The OP is asking for an exact solution, not an approximation.[/quote]
After rereading the OP, I have to say you are probably right. His asking for an "AI method" confused me into thinking he meant a heuristic method.

While it's true that the more annealing you do, the closer to 1 the probability of finding the optimal solution becomes[...][/quote]
Wait, so you did know what "arbitrarily high" meant...

[/font]
[/quote]

Hi again,
I have been experiencing minor server-side ironing difficulties (I don't know what it is but it made me unable to log in for a few days), so I sincerely apologize all of you for the controversy I have arisen



(Huuh?)
The very first thing that I should mention here is that the OP can hardly have an exact solution as it seems to be in NP; and, by "AI method", I actually meant an approximative method. I thank you all for your help, as it has brought me to the edge of finding a solution; Gradual elimination was the way I originally considered but it got complicated as I went by. The "sector" solution, interesting though it might be, was what I couldn't understand as it has not yet been thoroughly defined here; simulated annealing is so far the best way to do it. Yet a seemingly small sub-problem has hindered my way to overcome the main problem:
What I had rarely thought about until now is how to build a polyhedron from an arbitrary set of points? Or (a simpler question) how to measure the volume change resulting from swapping a point A with another point B?
Advertisement
This is something that is, indeed, lodged squarely in NP but likely NP-Complete. In a way, it is similar to Travelling Salesman, vertex cover, exact cover, etc.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

I would also go for computing the convex hull. Intuitively speaking, if the point cloud comes from a reasonable random distribution, the number of points on its boundary should be at most something like the 2/3-rd power of the total number of points (because volume is cubic while surface is square), and so it's quite possible that the convex hull is small enough from the start for reasonable instances.

I remember seeing a paper which computed the expected number of points on the convex hull of a uniformly drawn sample in the unit square, but I don't remember anything about it (neither the result nor the title or authors).
Widelands - laid back, free software strategy

[...]Or (a simpler question) how to measure the volume change resulting from swapping a point A with another point B?


I thought about that a bit before posting my suggestion of using simulated annealing, but I don't have a really simple way to do it. One fairly naive solution is to compute the convex hull of the points without either A or B, and then measure the volume that A or B would add to the convex hull. The second part is really fast to execute: Just loop over the faces of the convex hull and add up the volumes of the pyramids formed with the new point, but only if the orientation is right (in the natural implementation this turns out to be "only if the volume is positive").
You could try a modified form of Sequential Minimial Optimization (SMO).


What you're looking for are very similar to support vectors-- i.e. the minimal number of points used to define the space within a covex hull of some sort.


Edit: Actually, this is excatly what SMO is used for. I'd show you screen shots but I'm too lazy right now. Without knowing anything about your data, I'll assume that the clouds are random; if so, there will multiple best answers, and these will depend on what your criteria for 'best' is.

This topic is closed to new replies.

Advertisement