# Robots in Partially Known and Unknown Environments:
## 2 Related Work  
Robot motion planning has been studied since 1960. Its original version was the Piano Mover's Problem, which aims to move a piano or complex object from one room to another with obstacles in the way [5]. The path planning problem is demonstrated to be NP-hard in [6]. Several approaches have been proposed to solve the robot motion planning problem. Most of these are focused on completely known environments, the offline motion planning problem, and the newest ones are focused on unknown environments, the online motion planning version. Moreover, these approaches can be classified as classic methods and heuristic-based methods [7]. Most classic methods can be classified as planning by construction, while heuristic optimization algorithms are classified as planning by modification. The classic roadmap methods model the space without obstacles onto a network of lines, transforming the offline path planning problem into a graph searching problem. Visibility graphs use the search space to trace lines between different parts of the obstacles. Including the starting and target points, it is possible to create a graph in which a graph search algorithm is used [8]. In these graphs, all the lines must be feasible paths. Voronoi diagrams aim to create graphs of paths similar to visibility graphs, but, instead of using vertices, Voronoi diagrams create additional space around the obstacles [9]. The specific goal considered by these approaches is to obtain the clearest paths. In cell decomposition approaches, the search space is divided into cells, which are then used to search a path that begins at the starting point and ends at the target point connected by cells in sequence [7]. In potential fields, the robot is treated as a point under the influence of an artificial potential field, while the target attracts the robot, and the obstacles push the robot away [10]. Sampling-based techniques aim to find paths in different samples of the free workspace and then join them [11]. This method obtains good results for robots with a high degree of freedom in static environments. The two main classifications of these methods are probabilistic roadmap methods and rapidly exploring random trees. Probabilistic roadmap methods locate a set of configurations in the free space, which are connected using a local planner. The starting and target positions are added to the path. Finally, a graph-search-based algorithm is used to find the shortest path [12]. A large number of approaches can be found in the literature, all based on the rapidly exploring random trees [13]. The basic method works by iteratively growing a tree from the starting point to the goal node by generating random points in the space that are linked to the closest point in the current tree. The basic algorithm and its variants can be classified as sampling methods. In [14; 15], reviews of these RTT methods are presented. Most of the recent approaches consider the use of several trees [16] that enable balancing the processes of the exploration and exploitation of the robot search space by generating random heuristic trees that are used to connect the rooted tree towards the goal area. In [17], the authors propose a path planning algorithm focused on the consideration of collision risk. The approach combines a trajectory estimation algorithm and A* to select the low-risk points to conform to the path. Also, ref. [18] considers the inclusion of spatial-temporal specifications. Heuristic algorithms have also been used to solve the offline motion planning problem. In [19], a genetic algorithm is introduced. The goal is to find an adaptable path according to changes in the environment. Each individual of the population corresponds to a candidate solution using a binary representation. In [20], the use of simulated annealing with potential fields is proposed. Once a local minima is found using potential fields, simulated annealing is used with a high initial temperature to enable changing to a worse solution to escape the local minima.