Path Optimization

Hello David,

Im trying to build a definition (potentially using Galapagos) that could optimize a path along a surface (topography).

I basically want to go from points A to B along the surface and find the most "comfortable" path for doing so. This means being within a tolerable distance in Z from the previous point while eventually finding your way to destination B.

So far Ive tried populating the surface with a grid of points and testing neighbors for potential next point destinations along the route.

Do you think Galapagos is the right tool for this? My problem is that

1. I cannot loop the next point along after the first iteration
2. With only one fitness criteria I dont know that out of the potential points along the route its picking up the one that gets me to B eventually.

The other thing I thought of was to instantiate random routes along the grid from A to B and then testing for a desired average slope but I'm having trouble getting that to work as well (new to galapagos).

Thanks in advance for your time and efforts

M

Tags: algorithm, galapagos, genetic, optimization, path, topography

▶ Reply to This

Replies to This Discussion

Permalink Reply by Jacek Jaskólski on September 13, 2010 at 12:56pm

This is interesting. Have you managed to get somewhere?
Maybe this topic could be of some help.

▶ Reply

Permalink Reply by msgrom on September 13, 2010 at 1:19pm

Hi,

Thanks for the link. Thats very helpful.

To help describe the problem the attached image describes the better routes along a topography. What im trying to build to get there is a series of evaluation parameters so that the path understands where it would be better to go and what routes to try to avoid.

Im still having trouble building it though

Thank you for your interest and if anyone has any thoughts Id greatly appreciate it.

M

Attachments:

Screen shot 2010-09-13 at 11.10.53 AM.png, 316 KB

▶ Reply

Permalink Reply by Jacek Jaskólski on September 14, 2010 at 1:41am

Here's a little something I've managed to do with Galapagos:

The path is created by the Curve on Surface component with two intermediate points.
The solver tries to minimize the sum of the slopes at N=100 division points on the curve, by controlling the uv coordinates of the intermediate points. At the same time it tries to make the path as short as possible.

I've attached the definition.

Attachments:

test_19_optimized road.ghx, 315 KB

▶ Reply

Permalink Reply by Wiet Mazairac on September 14, 2010 at 1:46am

Hello,

You say; "...being within a tolerable distance in Z from the previous point...".

This means if the point differ to much in height no route will be found. Is this what you want or do you want to find the route which rises the least?

▶ Reply

Permalink Reply by Paul N Jeffries on September 14, 2010 at 6:56am

Hello Mateo,

If you wanted to do this properly (which you probably don't), you could try writing an A* pathfinding algorithm for it between a set (wouldn't necessarily have to be a grid) of nodes on the surface, where the 'movement cost' was a function of distance and height increase (or anything else you wanted, that's the beauty of it). This would obviously require a bit of semi-tricky VB.NET scripting, but then you did learn from the best...

Of course you might get the same result through galapagos eventually, but this method would be (computationally, at least) a lot faster and more exact.

Paul

▶ Reply

Permalink Reply by msgrom on September 14, 2010 at 10:34am

Hello Jeffries...

It seems like an A* pathfinding algorithm is the way forward for someone looking forward to doing this properly (that would be me). Ill get back to you when I get stuck with the semi tricky scripting.

Dont forget to say hi to mr. Clark for me. Good to hear from you.

Best,

M

▶ Reply

Permalink Reply by brendon_carlin on September 17, 2010 at 8:38am

Hey Paul and Mateo,

i guess i also learned from the best (thanks paul), though i hope my lack of skills doesnt reflect on you. ;)

here is a very quickly resolved version of an pathfinding code, the fitness test is very simple and not well tested. but this might help.

best

Attachments: