Welcome to cuAstar's documentation!

introduction

usage api

Indices and tables

• Index

• Search Page

template<typename NodeType, typename T>
class AstarPlanner

#include <cuAStar.hpp>

divide the datset into chunks of max 1024 node, maxium , compute the best node into, each chunk on a single grid block, each block , writes the best node (wich is the closed to target), to the global device memory,each chunk has a root node and a sucessor the sucessor parent points to the root,and the cost function , the chunk sum_cost of root is 0 and for the child is the distance btewwen the both , start with the chunk wich have the mimum cost function, (p_sum + heursitic) wich is assumed to be the final chunk that have the goal node, named the endChunk, now we sav the nodes into a new_array include the start and gaolnode and the chunks 2-nodes , we llok fro the trajectory that pass from all thes points , with minium path cost, so, we allocte this array on the device global meomry, and for a single block each thread compute, 1 < chunk_size < 1024, each thred within the same only block will compute a possible combinition, each thred will loop all the nodes in the array, starting from the endnode, if this has a parent it go throug else , it computes the nereast neighbood node , and if this also

after computing the chunks and save each chunk nodes (2*NodeType), and the matric: cost to got from chunk root to child chunk + the heuristic % to-go node the number of chunks is : N/threadsPerBlock afther constructing the nodes grid

Public Functions

AstarPlanner()

default constructor, allocate momory for class attributes on host and device, this function, sets the node number to thredsPerBlock var and allocate memeory

AstarPlanner(NodeType &h_nodesArray_, int numNodes_)

construct from a user defined point clouds array init number nodes allocate and fill member attributes , copy them to device and init memebr attributes device vars

AstarPlanner(const std::string &plyFilePath)

fill the host and device memory with the nodes from the a point cloud data file .ply

Note

this method fill only host attributes class mmeber, no device initlisation when need create a device var and copy from it

AstarPlanner(int numNodes_, unsigned int seed)

init the host and device memory with random nodes, if the number of ndodes given os diffrent from class alraedy vars old, ovveride them

Parameters:

seed -- : random seed initilization

void setInitialNode(NodeType *startNode_)

set the start nodes either in 3d or 2d, check if the node exsits in the h_nodesArray first, if the start are set, it defaulted to the first and last node in the nodes array.

Parameters:

startNode_ -- a construted nodeType for the given node the given node should exsit in the point cloud,

void setTargetNode(NodeType *endNode_)

set the end node , it should exsit in the point cloud and it should be diffrent from

void computeChunkOpenSet(const int chunkSize_ = threadsPerBlock)

computes he chunks open set array for all chunks in the point cloud array , divide into chunks, compute the knns , reoder by fmin values and append to the h_chunksOpenSetArray , the rest of nodes are divided inti chunks and and reorded, the default size of chunks is the bloc size

void computeTrajectory()

given the the map tree construted, satart from the end node and, given that each node has unique parent, it saves the nodes and copy up to the start node

void writeTrajectory2csv(const std::string outputFilePath)

saves a trajectory to pointcloud file .ply using happly library

void saveTrajectory2png(const std::string &outputFilePath)

read a point cloud data file (now only PLy supported) and fill the gridMap object memebr of the class with nodes consruted from the point cloud

Parameters:

outputFilePath -- image fil path to save to

void visualize2dPointCloud(const std::string imageFilePath)

saves the point cloud data array into a 2d, view along z-axis, to a png file, the setting for this function are taken to default, this function require the host array or nodes filled, the color used for each node is the default in r , g ,b arrtibutes in each node to update them use updateNodesColor()

void visualize2dTreeMap()

this method take an array reprsent a map and debug it in 2d, nodes are not displayed a unicolor lines between child-parent is ploted

~AstarPlanner()

free all memory on deice or on host memory allocation in the constructor or over functions

Private Functions

bool isTargetReached(const NodeType *n, const T eps)

Check wahat ever we get into the goal node or not, using a threshold value esplion for proximity checking.

void computeOpenSetArray()

Private Members

int numNodes

int chunkSize

the chunks size controls the

NodeType *h_nodesArray

NodeType *h_chunksOpenSetArray

Pointer to an array of NodeType objects, where each element represents the open set of nodes for a specific chunk. The open set is used to store nodes ordered by their f value, ranging from minimum to maximum. These nodes are derived from the chunk's k-nearest neighbor (kNN) array. The computeNodesSuccessor function is used to sort these nodes, which computes nodes with the minimum f(n) values and organizes them in the array.

NodeType *h_openSetArray

form a new arra and compute the gloabl openset, n pallel way

given the local opensets, of chunks, it gets the roots of each chunk,

NodeType *h_closedSetArray

any node not in openset is in closed set,

NodeType *startNode

NodeType *endNode

NodeType *h_pathArray

for storing the final computed traj on host ,

NodeType *d_pathArray

..... on device;

struct Circle

#include <cuAStar.hpp>

Public Members

int x

int y

int radius

struct Color

#include <cuAStar.hpp>

rgb color base struture

Public Members

unsigned char r

unsigned char g

unsigned char b

template<typename T>
class Node2d

#include <cuAStar.hpp>

Base class for 2D nodes representation.

Template Parameters:

T -- Numeric type for the sum_cost (e.g., T, float)

Param x:

: x-coordinate in the grid

Param y:

: y-coordinate in the grid

Param z:

= 0 : this coordinate is used only to ensure generic function call that do not throw an error in using 3d nodes specific operations to 2d nodes based template methods.

Param sum_cost:

: cumulative cost from the start node to the current node

Param p_node:

: pointer to the parent node

Public Functions

inline Node2d()

default constructor for the Node2d class

inline Node2d(T x_, T y_, T sum_cost_, Node2d *p_node_)

Constructor for the Node2d class.

inline Node2d(T x_, T y_, T z_)

Overlaoding Constructor for the general puropse template calls.

inline bool isEqual(const Node2d &other, T eps = static_cast<T>(1e-6)) const

Checks if two nodes are equal based on their positions.

inline T distanceTo(const Node2d &other) const

Computes the Euclidean distance to another node.

Public Members

T x

T y

T z = static_cast<T>(0)

T sum_cost

Node2d *p_node

int r = 125

int g = 100

int b = 120

template<typename T>
class Node3d

#include <cuAStar.hpp>

Base class for 3D nodes representation.

Template Parameters:

T -- Numeric type for the sum_cost (e.g., T, float)

Param x:

: x-coordinate in the grid

Param y:

: y-coordinate in the grid

Param z:

: z-coordinate in the grid

Param sum_cost:

: cumulative cost from the start node to the current node

Param p_node:

: pointer to the parent node

Public Functions

inline Node3d()

Default constructor for the Node3d class.

inline Node3d(unsigned int seed)

init a random node, position bounds is in [0,1]

inline Node3d(T x_, T y_, T z_, T sum_cost_ = 0, Node3d *p_node_ = nullptr)

Constructor for the Node3d class.

inline T distanceTo(const Node3d &other) const

Computes the Euclidean distance to another node.

inline bool isEqual(const Node3d &other, T eps = static_cast<T>(1e-6)) const

Checks if two nodes are equal based on their positions.

Public Members

T x

T y

T z

T sum_cost

Node3d *p_node

int r = 125

int g = 100

int b = 120

file cuAStar.hpp

#include <cstdint>

#include <cfloat>

#include <array>

#include <chrono>

#include <ctime>

#include <string>

#include <stdexcept>

#include <algorithm>

#include <filesystem>

#include <vector>

#include <cmath>

#include "../extern/rapidcsv/rapidcsv.h"

#include "../extern/happly/happly.h"

#include "../extern/stb/stb_image.h"

#include "../extern/stb/stb_image_write.h"

https://towardsdatascience.com/understanding-a-path-algorithms-and-implementation-with-python-4d8458d6ccc7

Version

0.1.0

Author

wissem chiha

Date

03-09-2024

Defines

HOST_FUN

DEVICE_FUN

HOST_DEVICE_FUN

STB_IMAGE_WRITE_IMPLEMENTATION

ARRAY_SIZE(arr)

CUDA_CHECK_ERROR(err)

LOG_MESSAGE(level, format, ...)

Functions

template<typename T> __global__ void curandx (unsigned int seed, T *d_val)

Generates a random float between 0 and 1 with precision up to 1e-6.

__device__ float fatomicMin (float *addr, float value)

implemntation of atomic min for float type as cuda do not support it original implentation by : https://forums.developer.nvidia.com/t/atomicmin-with-float/22033

__device__ float fatomicMax (float *addr, float value)

bool isPlyValid(const std::string plyFilePath)

Check if a given point cloud data file .ply file path exists or not.

Throws:

a -- user error to cmd in debug mode, else none.

template<typename NodeType, typename T>
NodeType readPlyNode(const std::string &plyFilePath, const size_t idx)

extract a Node object from a .ply file defined by index idx, in the file, reprsent the line number of point coordiantes, it is computioanlly slow , not use in loops or other , just for single node extrcation, this method will be decapred in other versions

void drawFilledCircle(unsigned char *image, int width, int height, const Circle *circle, const Color *color)

Draw a 2D sphere (plain circle) given radius, center, and color.

void drawFilledCircles(unsigned char *image, int width, int height, const int *centersX, const int *centersY, const unsigned char *colorsR, const unsigned char *colorsG, const unsigned char *colorsB, int numCircles, double radiusRatio)

Draw a sample of point cloud nodes as 2D colored circles.

void savePointCloudImage(const char *filePath, int width, int height, const int *centersX, const int *centersY, const unsigned char *colorsR, const unsigned char *colorsG, const unsigned char *colorsB, int numCircles, double radiusRatio)

Draw and save a given 2D points cloud of nodes as an image.

template<typename NodeType> __global__ void computePointCloudBoundBox (const NodeType *h_arrayNodes, int N, float *minX, float *maxX, float *minY, float *maxY)

compute the 2d bound box dimension for 2d plotting scaling issues for N nodes elments the minimal block grid number is : (N + thredsPerBlock - 1) / thredsPerBlock; interblock synhonization , usen shared memory Thread 0 of each block updates the global min/max values using atomic operations note we cannot template the function with double , because cuda cannot use atomic operation for doubles , just for cuda computation cabolit >6.0 see: https://forums.developer.nvidia.com/t/atomic-functions-for-double-precision/9963 https://forums.developer.nvidia.com/t/why-does-atomicadd-not-work-with-doubles-as-input/56429 atomic operations is only supported by devices of compute capability 5.0 and higher.

Todo:

Use of Local Reductions per Block

template<typename NodeType>
void array2PointCloudImg(const NodeType *h_arrayNodes, int numNodes, const char *pngFilePath, double scaleFactor = 100, double radiusRatio = 0.01)

Draw and save a given 2D point cloud of nodes as an image, the data is given as a 1d host array of NodeType template objects.

Parameters:

• scaleFactor -- : zoom image coffienct

• radiusRatio -- :

size_t getPlyPointNum(const std::string plyFilePath)

Return the number of points stored in a .ply file.

template<typename T> __global__ void enumerationSort (T *a, int N, T *b)

CUDA kernel for sorting a numerical array using the enumeration sort algorithm. Original implementation by: Meng Hongyu, Guo Fangjin, UCAS, China https://arxiv.org/pdf/1505.07605 Modified by: Wissem Chiha, 01-09-2024, using templates.

template<typename NodeType, typename T> __global__ void enumerationSortNodes (NodeType *d_nodesArray, int N, int ax, NodeType *d_nodesArraySorted)

CUDA kernel that sorts an array of nodes based on a specified axis. This kernel sorts the nodes in ascending order according to their value along the given axis (1: x, 2: y, 3: z).

Note

the call of this kernel with ax = 3 and Node2d class has no effect, and it do not throw any error

Parameters:

• d_nodesArray -- Device pointer to the array of nodes to be sorted.

• ax -- Axis to sort by (1: x, 2: y, 3: z).

• N -- Number of nodes in the array.

• d_nodesArraySorted -- Device pointer to the array where sorted nodes will be stored.

template<typename NodeType, typename T>
void updateNearest(NodeType *nearestNodes, T *distances, const NodeType &node, const NodeType &otherNode, int k)

Update nearest neighbors list if the new node is closer

template<typename NodeType, typename T> __global__ void computeKnnNodes (NodeType *d_sortedX, NodeType *d_sortedY, NodeType *d_sortedZ, NodeType targetNode, int N, int k, int range, NodeType *d_kNodes)

Computes the K-nereast neighoods of a given node in a device array structure , by sorting x, y, z attributes, without using the K-D tree this kernel should excute on 1 block, so the maxium nodes number sorted arrays is 1024.

Parameters:

• range -- control the exploration range of the KNN, fixed , adjustee based on the point cloud distribution density , low for high dense data and high for low dense distrubution

• k -- should be < threadsPerBlock

template<typename NodeType, typename T> __global__ void checkNodeExsist (const NodeType *d_nodesArray, int numNodes, const NodeType *nodeToCheck, int *status)

Checks if a given node exists in the device nodes array.

Note

This method will be deprecated in future versions.

Note

we use atomic exchange to ensure thred safty writtin value to the we reprsent by : 0 FALSE and any other int the TRUE value, perform chek if only nly perform check if the index is within bounds and status is still false (0)

template<typename NodeType, typename T>
void computeHeuristicDistance(const NodeType &node, const NodeType &targetNode, T *hfun)

heuristic function which computes the estimated cost to the goal node, starting from the current given node, it simply the euclidian distances or the manthetn distance could be used

template<typename NodeType, typename T>
void computeNodeTrajectoryCost(const NodeType &node, const NodeType &targetNode, T *p_cost_)

Computes the trajectory cost metric starting from a given node. The objective function is: f(n) = g(n) + h(n), where g(n) is the path cost from the start node to the current node, and h(n) is the heuristic function value.

Parameters:

node -- The current node representing the position in the trajectory.

template<typename NodeType, typename T> __global__ void computeSucessorNode (const NodeType *d_knnNodesArray, int k, const NodeType *endNode, NodeType *d_bestNode)

Computes the best successor node based on path metric f(n) = g(n) + h(n) from the k nearest neighbor nodes. Each thread will compute the trajectory cost and then determine the node with the minimum cost. This function is designed to execute within a single block.

Parameters:

d_knnNodesArray -- Array of k-nearest neighbor nodes of the current node to be checked. The maximum size is 1024.

template<typename NodeType, typename T>
void computeTrajectoryCost(const NodeType *d_tarjNodesArray, int N, T *cost_)

Given a trajectory path represented by a device array of nodes, it computes the path cost: the Euclidean distance between the start and destination nodes. The start node is the first node in the array, and the destination node is the last node.

Note

Boundary checks are not performed; N is assumed to be within the array size range.

template<typename NodeType, typename T> __global__ void smoothTrajectory (const NodeType *d_trajNodesArray, int N, int k, NodeType *d_trajNodesArraySmooth)

soothing the distcreate computed trajectory, using either spline basis or bezier curves , or just normale interpolations.

Parameters:

• N -- number of points or control points in the trajectory

• k -- number of the evaulation point of the new trajectory

template<typename NodeType, typename T> __global__ void getRootNodes (const NodeType *d_nodesArray, int numNodes, NodeType *d_rootsArray)

Extracts nodes without a parent from an array of N nodes. Iterates over the input array, where each node has a p_node attribute (pointer to its parent). Constructs a new array containing only nodes where p_node == nullptr (i.e., no parent).

template<typename NodeType, typename T> __global__ void hasOrphanNodes (const NodeType *d_nodesArray, int N, bool *status)

Given an array of nodes, checks if there are any nodes without a parent, referred to as orphan nodes. Each thread in each block checks its assigned node.

Parameters:

• N -- The number of nodes.

• status -- A boolean flag to indicate if an orphan node is found.

Variables

const int threadsPerBlock = 1024

This is the default threads number, but you can choose up to 1024.

page todo

Member computePointCloudBoundBox  (const NodeType *h_arrayNodes, int N, float *minX, float *maxX, float *minY, float *maxY)

Use of Local Reductions per Block

dir include

page index

If there are no blocked cells/obstacles then we can just find the exact value of h without any pre-computation using the distance formula/Euclidean Distance all memory errors checks foe cuda are in debug mode ! $ g++ -std=c++0x main.cpp -pthread nvcc -o random_gen_example random_gen_example.cu -lcurand divide the point cloud data into small region called bubles a N pt cloud is divided into N/k where k is the window size , for each subarea , inti a substarting node explore (like running the normal A star on that subgroups nodes) with one setp the surouding and at each step , synchonize all subregions

https://pantelis.github.io/artificial-intelligence/aiml-common/lectures/planning/search/a-star/index.html

Note

for the multithreding and concurrency support computations support the c++ 11 standard is required More Info : https://en.cppreference.com/w/cpp/thread https://github.com/arvkr/ransac_cuda_eecse4750

Note

: 3D visulisation and rending is enabled only throut VTK,wich should be installed , we use VTK version 9.3.1, for more information refre to VTK installation guide

Warning

hhh