Path planning on a two-dimensional grid is a well-studied problem in robotics. It usually involves searching for a shortest path between two vertices on a grid given that some of the grid cells are impassable (occupie...
详细信息
Path planning on a two-dimensional grid is a well-studied problem in robotics. It usually involves searching for a shortest path between two vertices on a grid given that some of the grid cells are impassable (occupied by obstacles). Single-source path planning finds shortest paths from a given source vertex to all other vertices of the grid. Singles-source path planning enhances robot autonomy by calculating multiple possible paths for various navigation scenarios when the destination state is unknown. A high-performance algorithm for single-source any-angle path planning on a grid called CWave is proposed here. Any-angle attribute implies that the algorithm calculates paths which can include line segments at any angle, as opposed to standard A* that runs on an 8-connected graph, which permits turns with 45 degrees increments only. The key idea of CWave is to abandon the graph model and operate directly on the grid geometry using discrete geometric primitives (instead of individual vertices) to represent the wave front. In its most basic form (CWaveInt), CWave requires only integer arithmetics. CWaveInt, however, can accumulate the distance error at turning points. A modified version of CWave (CWaveFpuSrc) with minimal usage of floating-point calculations is also developed to eliminate any accumulative errors, which is proven mathematically and experimentally on several maps. The performance of the algorithm on most of the tested maps is demonstrated to be significantly faster than that of Theta*, Lazy Theta*, Field A*, ANYA, Block A*, and A* adapted for single-source planning (on maps with lower number of isolated obstacles, CWaveFpuSrc is 2-3 times faster than its fastest tested alternative Block A*). An N-threaded implementation (CWaveN) of CWave is presented and tested to demonstrate an improved performance (multithreaded implementation is 1.5-3 times faster than single-threaded CWave). The paper discusses foundations and experimental validation of CWave, and p
This work presents the analysis of three-dimensional polycrystals in the microscale with different lattice structures, hexagonal closed package (HCP) and face centered cubic (FCC). In these materials, the grained medi...
详细信息
This work presents the analysis of three-dimensional polycrystals in the microscale with different lattice structures, hexagonal closed package (HCP) and face centered cubic (FCC). In these materials, the grained medium is considered as a continuum elastic body. An artificial polycrystalline structure is modeled using the Voronoi tessellation to generate random morphological microstructures. To reproduce the stochastic effects, arbitrary crystalline orientations are distributed over the structure. The boundary element method (BEM) is used to obtain the static displacement and traction fields, with a fundamental solution for 3D general anisotropic materials based on double Fourier's series. The macroscopic effective elastic properties are evaluated using the average homogenization technique and compared to the reference values through convergence statistical analysis. Explicit schemes are presented in order to improve the computational load and decrease the time required by the main BEM application implemented on distributed memory architectures. Numerical examples are presented showing the convergence of the results and comparisons of anisotropy level between these FCC and HCP materials using a recently proposed anisotropy factor.
This paper describes computational models for particle-laden flows based on a fully resolved fluid-structure interaction. The flow simulation uses the Lattice Boltzmann method, while the particles are handled by a rig...
详细信息
ISBN:
(纸本)9781424475599
This paper describes computational models for particle-laden flows based on a fully resolved fluid-structure interaction. The flow simulation uses the Lattice Boltzmann method, while the particles are handled by a rigid body dynamics algorithm. The particles can have individual non-spherical shapes, creating the need for a non-trivial collision detection and special contact models. An explicit coupling algorithm transfers momenta from the fluid to the particles in each time step, while the particles impose moving boundaries for the flow solver. All algorithms and their interaction are fully parallelized. Scaling experiments and a careful performance analysis are presented for up to 294912 processor cores of the Blue Gene at the JuÌlich Supercomputing center. The largest simulations involve 264 million particles that are coupled to a fluid which is simultaneously resolved by 150 billion cells for the Lattice Boltzmann method. The paper will conclude with a computational experiment for the segregation of suspensions of particles of different density, as an example of the many industrial applications that are enabled by this new methodology.
暂无评论