Hey, sorry for the delay, been a bit busy.
No I am using it for Robot motion planing.
Cool.
DO U HAVE ANY MORE INFO ON THIS? COULD U EXPLAIN ME ME THE OPEN SPARSE GRAPH?
TUTORIAL, SITES, PUBLICATIONS E.T.C
Well, it's open
space graph, but the sparseness of the environment
is a factor in choosing the method used to generate the graph... There isn't a one-size-fits-all method, because you get a better result using a different method for different environments.
E.g. for an environment that's mostly open space, with a few obstacles that are roughly the same size, you can create the Voronoi tesselation (
http://mathworld.wolfram.com/VoronoiDiagram.html ) of the obstacles ( treating each obstacle as a point ), if you look at the picture on that site, treat the lines as the arcs and the junctions as the nodes of a space graph, following any path through that graph will keep the agent at a maximal distance at all times between obstacles, running standard a-star on that graph will give the shortest path that maintains such a maximal distance ( although this isn't necessarily the shortest path through the space itself, since the constraints conflict somewhat ). However, with obstacles that are different sizes, or very large, you have to do a lot of 'repair work' on the graph before it's useable...
If the environment is mostly obstacles, or narrow paths ( like a maze ), you'd get a better graph by generating the polytope of the open space, approximating the medial axis of that polytope
http://www.ics.uci.edu/~eppstein/gina/medial.html ( which would basically be the Voronoi tesselation of the actual shape of the obstacles; rather than just treating them as points ), and create a graph from that.
Both of these methods sacrifice some detail in the environment in order to improve computational efficiency.
Since like aforementioned there are no moving obstacles I don’t have to consider it.
That makes things easier.. =)
I use a time constrain to avoid this.
I limit partitioning up to 2 more resolutions besides the initial (totally=3)
Wise
I didn’t understand this one… Could u maybe explain this to me? ( recursive A-star )
Well, when I wrote that, I thought you were asking if A-star can be implemented as a recursive function (i.e. getting rid of the open set and spawning off a new function call for every newly expanded node ), and I guess it can, since Djisktra's algorithm can be in a uniform grid ( with a few caveats )...
Now I read again, I think I get that you mean can you use a recursive ( hierachical ) representation in the grid, i.e. with a dynamically generated(?) oct-tree as each cell.. and I invision you doing something like this.. ( most is 'vanilla' A-star, changed parts are emboldened ).
create open set, create closed set
add start node to the open set
while open set isn't empty {
x = smallest h in open set,
remove x from open set, add x to closed set
if x contains obstacles and not subdivision limit reached for node x {
subdivide x and splice it into the current environment *
}
loop through neighbours of x {
calculate h for each neighbour, add each neighbour to open set
}
} * here, you modify the data used to determine the neighbours of cells so that the subdivided cells show up as neighbours of non-subdivided adjacent cells.
Is that similar to what you're trying to do? It seems like it should work, although the splicing bit would need some careful thought, and it might be better to subidivide ALL nodes opened to avoid strange changes in the granularity of the path.
I haven't ever tested that, or read anything specifically saying such a method is either a) still an optimal graph search, or b) that it provides a massive performance boost... but! that's not to say that either of those things aren't possible.
Alternatively, you can implement the whole A-star algorithm at multiple resolutions, instead of creating obstacles that can't be walked into, just give each cell a heuristic relative to its occupation density ( or use a rough waypoint graph as suggested above ), then run A-star again on the low-resolution nodes that were intersected by a path, and repeat until done.. that algorithm is non-admissable in terms of finding the global shortest path, and could fail to find a valid path in some cases.
I didn’t understand this one… Could u maybe explain this to me? ( closed set / open set )
Hashed sets compute ( for each value ) an n-bit key using a one way, chaotic function, with the guarantee that hash(x) == hash(y) if x==y, but that hash(x) == hash(y) does not imply that x==y. A perfect hash key is a set of value->key mappings where no collisions occur, i.e. where every unique value gets mapped to a unique hash key, ( this would imply that x==y ). Importantly, you CAN generate a perfect hash of 3D co-ordinates in a bounded space at a given resolution, simply 'fit' the values into a certain range, and then shift and binary-or the result.. e.g. create an integer that has the ( bounded ) x, y, and z co-ordinates stuck next to each other.. ( use a 64-bit int if you like, you get decent resolution then: int ( 64/3 ) = 21, 2^21 = 2097152, thus 2097152 unique integer values. ) Using a perfect hash key in a standard tree container will remove any need to perform hash-key collision resolution ( which a hashed set performs under the hood ).
I was told that:
map, set, multimap, and multiset are implemented using a red-black tree and thus have the following asymptotic run times:
Insertion: O(log n)
Lookup: O(log n)
Deletion: O(log n)
while
hash_map, hash_set, hash_multimap, and hash_multiset are implemented using hash tables having the following runtimes:
Insertion: O(1) expected, O(n) worst case
Lookup: O(1) expected, O(n) worst case
Deletion: O(1) expected, O(n) worst case
And if I use a proper hash function, I will almost never see the worst case behavior.
So I guess that u dont agree with this... but I didnt understand the why
No, I completely agree with that ( at least in theory ), but the O(1/n/log n) hide multiplicative and additive factors, big-O notation is always normalized, so you'd never see O(2000*n), just O(n). But, by all means benchmark and find out which is best for your situation, a hash is one of those structures than can be great in circumstance A, but not so great in circumstance B, with any benefit afforded only partially depending on the hashing function used.
Also, the time expectactions say nothing in terms of memory - a tree grows as data is added in a roughly linear fashion; adding one entry allocates a single linked-list node. Adding something to a hash implemented with a single array ( with one space for each potential hash-key ) could result in an massive array with only one occupied element, so typically a hash has some memory optimization, either to reduce the resolution of the key-set, or to use a structure other than an array ( i.e. a linked list ) to implement the entries array... the second optimization would no longer provide O(1) access, and the first optimization will result in an occasional need to re-hash, because the REAL worst case in a well-memory-optimized hash involves ditching all of the data in the hash, reallocating all of the data, and recomputing all of the hash keys..
Anyway.. good luck =)
Unsolved 
Offline 
