M-File Help: Dstar | View code for Dstar

# Dstar

D* navigation class

A concrete subclass of the Navigation class that implements the D* navigation algorithm. This provides minimum distance paths and facilitates incremental replanning.

## Methods

plan | Compute the cost map given a goal and map
path | Compute a path to the goal
visualize | Display the obstacle map (deprecated)
plot | Display the obstacle map
costmap_modify | Modify the costmap
modify_cost | Modify the costmap (deprecated, use costmap_modify)
costmap_get | Return the current costmap
costmap_set | Set the current costmap
distancemap_get | Set the current distance map
display | Print the parameters in human readable form
char | Convert to string

## Properties

costmap | Distance from each point to the goal.

## Example

    load map1           % load map
    goal = [50,30];
    start=[20,10];
    ds = Dstar(map);    % create navigation object
    ds.plan(goal)       % create plan for specified goal
    ds.path(start)      % animate path from this start location

## Notes

- Obstacles are represented by Inf in the costmap.
- The value of each element in the costmap is the shortest distance from the corresponding point in the map to the current goal.

## References

- The D* algorithm for real-time planning of optimal traverses, A. Stentz, Tech. Rep. CMU-RI-TR-94-37, The Robotics Institute, Carnegie-Mellon University, 1994.
- Robotics, Vision & Control, Sec 5.2.2, Peter Corke, Springer, 2011.

## See also

Navigation, DXform, PRM

# Dstar.Dstar

D* constructor

ds = Dstar(map, options) is a D* navigation object, and map is an occupancy grid, a representation of a planar world as a matrix whose elements are 0 (free space) or 1 (occupied). The occupancy grid is coverted to a costmap with a unit cost for traversing a cell.

## Options

'goal', G | Specify the goal point (2x1)
'metric', M | Specify the distance metric as 'euclidean' (default) or 'cityblock'.
'inflate', K | Inflate all obstacles by K cells.
'quiet' | Don't display the progress spinner

Other options are supported by the Navigation superclass.

## See also

Navigation.Navigation

# Dstar.char

Convert navigation object to string

DS.char() is a string representing the state of the Dstar object in human-readable form.

## See also

Dstar.display, Navigation.char

# Dstar.costmap_get

Get the current costmap

C = DS.costmap_get() is the current costmap. The cost map is the same size as the occupancy grid and the value of each element represents the cost of traversing the cell. It is autogenerated by the class constructor from the occupancy grid such that:

- free cell (occupancy 0) has a cost of 1
- occupied cell (occupancy >0) has a cost of Inf

## See also

Dstar.costmap_set, Dstar.costmap_modify

# Dstar.costmap_modify

Modify cost map

DS.costmap_modify(p, new) modifies the cost map at p=[X,Y] to have the value new. If p (2xM) and new (1xM) then the cost of the points defined by the columns of p are set to the corresponding elements of new.

## Notes

- After one or more point costs have been updated the path should be replanned by calling DS.plan().
- Replaces modify_cost, same syntax.

## See also

Dstar.costmap_set, Dstar.costmap_get

# Dstar.costmap_set

Set the current costmap

DS.costmap_set(C) sets the current costmap. The cost map is the same size as the occupancy grid and the value of each element represents the cost of traversing the cell. A high value indicates that the cell is more costly (difficult) to traverese. A value of Inf indicates an obstacle.

## Notes

- After the cost map is changed the path should be replanned by calling DS.plan().

## See also

Dstar.costmap_get, Dstar.costmap_modify

# Dstar.distancemap_get

Get the current distance map

C = DS.distancemap_get() is the current distance map. This map is the same size as the occupancy grid and the value of each element is the shortest distance from the corresponding point in the map to the current goal. It is computed by Dstar.plan.

## See also

Dstar.plan

# Dstar.modify_cost

Modify cost map

## Notes

- Deprecated: use modify_cost instead instead.

## See also

Dstar.costmap_set, Dstar.costmap_get

# Dstar.plan

Plan path to goal

DS.plan() updates DS with a costmap of distance to the goal from every non-obstacle point in the map. The goal is as specified to the constructor.

DS.plan(goal) as above but uses the specified goal.

## Note

- If a path has already been planned, but the costmap was modified, then reinvoking this method will replan, incrementally updating the plan at lower cost than a full replan.

# Dstar.plot

Visualize navigation environment

DS.plot() displays the occupancy grid and the goal distance in a new figure. The goal distance is shown by intensity which increases with distance from the goal. Obstacles are overlaid and shown in red.

DS.plot(p) as above but also overlays a path given by the set of points p (Mx2).

## See also

Navigation.plot

# Dstar.reset

Reset the planner

DS.reset() resets the D* planner. The next instantiation of DS.plan() will perform a global replan.

© 1990-2014 Peter Corke.