# Robot Path Planning

In general, research on various robots can be divided into three categories
of **design and manufacture**, **navigation and guidance**, and their **application**.

Whatever the mission of the robot, it doesn't have any impact on the role of navigation and the guidance of the robot. Given the wide extent of research in the field of **navigating and guidance** the robot, it breaks into four general areas of

- Positioning
- Path planning (routing)
- Motion planning (control)
- Mapping

Internet Search

Even before the development of robots, two well-known issues such as the "Traveling Salesman Problem" and "Piano Mover's Problem" have been around for many years and have been solved in various ways.me case, these applications can be transferred onto the physical robot (or rebuilt) without modifications.

Generally, a robot must proceed to **calculate positions** for conducting navigation and guidance.
These positions could be quantitative (namely, coordinates in terms of unit length) or symbolic
(such as color signs, etc.).

After this step, the robot should identify a **route** or **path** based on their
current position, destination position (target) and the perception from the environment (whether
with or without a map). How to specify the path is called "path planning".

After identifying path, the robot must be controlled such that it moves along this path. Robot motion control, is
referred as **motion planning**. Some of the robots, including humanoid robots map their
environment so they can use the map for their next routing purpose.

According to the available information from the environment, robotic path
planning can be divided into **three** general categories of path planning in a **known environment**,
path planning in a **semi-known environment**, and path planning in an **unknown environment**.

## Map representations

In order to plan a path, we somehow need to represent the environment in the computer. We differentiate between two complementary approaches: **discrete** (`Relational representation`

) and **continuous** approximations (`Coordinate-based representation`

).

In a **discrete approximation**, a map is sub-divided into chunks of equal (e.g., a grid or hexagonal map) or differing sizes (e.g., rooms in a building). The latter maps are also known as `topological maps`

.

Discrete maps lend themselves well to a `graph`

representation. Here, every chunk of the map corresponds to a vertex (also known as “node”), which are connected by edges, if a robot can navigate from one vertex to the other. Discrete maps are the dominant representation in robotics.

### Types of Relational representation

#### View graph representations

In view graph representations the nodes are directly associated with the particular sen- sor input, called a view, available at a particular location.

#### Route Graph Representations

A general model for environmental knowledge gained by integrating route information into sur- vey knowledge by humans and animals, and also by artificial agents. We adopt it here for graph representations in which the nodes stand for distinctive places induced by the environment. The edges reflect distinctive paths connecting these places, allowing travel from one place to another.

A **continuous approximation** requires the definition of inner (obstacles) and outer boundaries, typically in the form of a polygon, whereas paths can be encoded as sequences of real numbers.

Currently the most common map is the **occupancy grid map**. In a grid map, the environment is discretized into squares of arbitrary resolution, e.g. 1cm x 1cm, on which obstacles are marked.

### Types of Coordinate Based Representations

#### Occupancy Based Representations

Occupancy-based representations represent occupied and free parts of space equitably by decomposing space into cells and storing for each cell whether it is (at least par- tially) occupied or (entirely) free. Typically, the decomposition is independent of the distribution of objects in space and uniform in the sense that all cells have the same shape and size.

#### Geometric Representations

Geometric representations use parameterized primitive geometric objects, i.e., points, lines, curves, planes, etc. For these objects, we will adopt the term geom here. A geometric representation basically consists of a list of geoms describing the boundaries of free space located in a single coordinate system. Most approaches used for mobile robots employ a single kind of geom.

##### Landmark-Based Representations

Landmark-based representations represent the world as a set of salient objects (the landmarks) extracted from the sensor data.

There is no **silver bullet**, and each application might require a different solution that could be a combination of different map types.

## Simulator Map representation

We will be using Coordinate based representation `Occupancy Based Representations`

for our simulated environment.

For this we have to form grid , We can also perform planning in pixel basic grid but it takes a lot of computation power and complex map representation.

`Speed`

VS `Accuracy`

)

Size of grid (## Path Planning Algorithms

### Dijkstra’s algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks

#### Dijkstra's algorithm to find the shortest path between a and b.

It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.