Mapping based navigation
Kool: Tallinna Tehnikaülikool (TalTech, TTÜ)
Aine: Robootika
Kategooria: Robootika
Postitatud: 13 märts 2025
Postitaja: ArmastusväärneHamster
Kirjeldus
Mapping-Based Navigation Dijkstras Algorithm Dijkstra described his algorithm for a discrete graph of nodes and edges. Here we describe it for a grid map of cells (Fig. 10.1a). Cell S is the starting cell of the robot and its task is to move to the goal cell G. Cells that contain obstacles are shown in black. The robot can sense and move to a neighbor of the cell c it occupies. For simplicity we specify that the neighbors of c are the four cells next to it horizontally and vertically but not diagonally. Figure 10.1b shows a shortest path from S to G The algorithm incrementally marks each cell c with the number of steps needed to reach c from the start cell S. In the figures the step count is shown as a number in the upper left hand corner of a cell. Initially mark cell S with 0 since no steps are needed to reach S from S. Now mark every neighbor of S with 1 since they are one step away from S then mark every neighbor of a cell marked 1 with 2. Figure 10.2b shows the grid map after the…