Name
Abstract | ||
|---|---|---|
A method for solving visibility-based terrain path planning problems using massively parallel hypercube machines is proposed. A typical example is to find a path that is hidden from moving adversaries. This kind of problem can be generalized as a time-varying constrained path planning problem and is proven to be computationally hard. An approximation based on both temporal and, spatial sampling is proposed. Since a 2-D grid cell representation of terrain can be embedded into a hypercube with extra links for fast communication, the method can be very efficient when implemented on hypercube machines. The time complexity is in general O(T×E×log N) using O (N) processors, where T is the number of temporal samples, E is the number of adversary agents, and N is the number of grid cells on the terrain. It is also shown that the method can be applied to several realistic problems with a variety of path optimizations. All algorithms have been implemented on the Connection Machine CM-2 and results of experiments are presented |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1109/21.214770 | Systems, Man and Cybernetics, IEEE Transactions |
Keywords | Field | DocType |
computational complexity,cooperative systems,hypercube networks,mobile robots,parallel machines,path planning,spatial reasoning,temporal reasoning,2D grid cell representation,Connection Machine CM-2,massively parallel hypercube machines,path optimizations,spatial sampling,stealth terrain navigation,temporal sampling,time complexity,time-varying constrained path planning problem,visibility-based terrain path planning problems | Motion planning,Binary logarithm,Spatial intelligence,Mathematical optimization,Computer science,Massively parallel,Terrain,Artificial intelligence,Time complexity,Machine learning,Hypercube,Computational complexity theory | Journal |
Volume | Issue | ISSN |
23 | 1 | 0018-9472 |
Citations | PageRank | References |
20 | 1.53 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Teng, Y.A. | 1 | 20 | 1.53 |
| Daniel Dementhon | 2 | 1327 | 139.94 |
| Larry S. Davis | 3 | 14201 | 2690.83 |