Classic path finding algorithms are not adequate in real world path planning, where environment information is incomplete or dynamic and Markov Decision Processes have been used as an alternative. The problem with the MDP formalism is that its state space grows exponentially with the number of domain variables, and its inference methods grow with the […]

December 9, 2015 by hgpu

We present a parallel algorithm for finding the shortest path whose total weight is smaller than a pre-determined value. The passage times over the edges are assumed to be positive integers. In each step the processing elements are not analyzing the entire graph. Instead they are focusing on a subset of vertices called active vertices. […]

November 24, 2015 by hgpu

The implementation of parallel genetic algorithms on a graphic processor GPU to solve the Travelling Salesman Problem instances is presented. Two versions of parallel genetic algorithms are implemented, a Parallel Genetic Algorithm with Islands Model and a Parallel Genetic Algorithm with Elite Island; the two versions were executed on a GPU. In both cases, each […]

April 27, 2015 by hgpu

General sparse matrix-matrix multiplication (SpGEMM) is a fundamental building block for numerous applications such as algebraic multigrid method (AMG), breadth first search and shortest path problem. Compared to other sparse BLAS routines, an efficient parallel SpGEMM implementation has to handle extra irregularity from three aspects: (1) the number of nonzero entries in the resulting sparse […]

April 23, 2015 by hgpu

Since DARPA Urban Challenge 2007 (DUC), the development of autonomous vehicles has attracted increasing attention from both academic institutes and the automotive industry. It is believed that autonomous vehicles sophisticated and reliable enough would redefine mobility. The motion planner and sensor simulation presented in this thesis are intended to contribute to this prospect. The task […]

April 7, 2015 by hgpu

We develop an efficient parallel algorithm for answering shortest-path queries in planar graphs and implement it on a multi-node CPU/GPU clusters. The algorithm uses a divide-and-conquer approach for decomposing the input graph into small and roughly equal subgraphs and constructs a distributed data structure containing shortest distances within each of those subgraphs and between their […]

March 28, 2015 by hgpu

All-pairs shortest path problem(APSP) finds a large number of practical applications in real world. We owe to present a highly parallel and recursive solution for solving APSP problem based on Kleene’s algorithm. The proposed parallel approach for APSP is implemented using an open standard framework OpenCL which provides a development environment for utilizing massive parallel […]

December 20, 2014 by hgpu

This work introduces a bilevel, stochastic optimization problem aimed at robust, regional evacuation network design and shelter location under uncertain hazards. A regional planner, acting as a Stackelberg leader, chooses among evacuation-route contraflow operation and shelter location to minimize the expected risk exposure to evacuees. Evacuees then seek an equilibrium with respect to risk exposure […]

October 25, 2014 by hgpu

In recent years, Unmanned Aerial Vehicles (UAVs) are emerged as an attractive technology for different types of military and civil applications which have gained importance in academic researches. In these emerging research areas, UAV autonomy gets a great part and mainly it refers the ability for automatic take-off, landing and path planning of UAVs. In […]

August 11, 2014 by hgpu

In this paper, different parallel implementations of Bellman-Ford algorithm on GPU using OpenCL are presented. These variants include Bellman-Ford for solving single source shortest path (SSSP) having two variants and Bellman-Ford for all pair shortest path (APSP) problems. Also, a comparative analysis of their performances on CPU and GPU is discussed in this paper.Write-write consistency […]

July 12, 2014 by hgpu

The exponential growth in bioinformatics data generation and the stagnation of processor frequencies in modern processors stress the need for efficient implementations that fully exploit the parallel capabilities offered by modern computers. This thesis focuses on parallel algorithms and implementations for bioinformatics problems. Various types of parallelism are described and exploited. This thesis presents applications […]

July 3, 2014 by hgpu

Computing driving directions interactively on continental road networks requires preprocessing. This step can be costly, limiting our ability to incorporate new optimization functions, including traffic information or personal preferences. We show how the performance of the state-of-the-art customizable route planning (CRP) framework is boosted by GPUs, even though it has highly irregular structure. Our experimental […]

June 25, 2014 by hgpu