ABSTRACT
Robot activity planning encompasses task planning, motion planning, and the integration of robot task and motion planning. Key points and main steps of all types of algorithms for robot activity planning are described. Search algorithms used in robot task and motion planning are discussed including the A* search algorithm (a graph traversal and pathfinding algorithm using a heuristic function to estimate the distance to the goal from each node), Dijkstra’s algorithm (a classic, deterministic method to determine the shortest path between two points in a graph), rapidly exploring random tree algorithm (randomly sampling points in the search space, connecting them to the existing tree and gradually expanding the tree until it reaches the goal point) and probabilistic roadmap (randomly sampling points in the free space to create a network of connected nodes and then searching for a path between the start and goal nodes within this roadmap). A* search and Dijkstra are ‘informed search algorithms’ prioritizing exploration of closer nodes to the goal, while the rapidly exploring random tree algorithm and the probabilistic roadmap are both randomized algorithms used in complex, high-dimensional spaces.
