D*与D* Lite的时间、空间复杂度及推导方法技术问询

Hey there! Let's dive into the time and space complexities of D* and D* Lite, plus break down how we derive those figures. I’ll tie everything back to the core mechanics of each algorithm since that’s where these complexities originate.

Time Complexity #

• Static Environment (no changes post-planning): O(n + m), where n is the number of nodes and m is the number of edges in the graph.
• Dynamic Environment (with k edge cost updates): Cumulative re-planning time is O(k*m).

Derivation #

D* operates using a reverse search—it starts from the goal node and propagates costs back to the start node, maintaining an open list (priority queue) of nodes that need re-evaluation.

• For the initial static plan: We process each node and edge exactly once during the initial propagation, hence the linear O(n + m) cost.
• For dynamic updates: When an edge’s cost changes (e.g., an obstacle appears/disappears), D* only re-evaluates nodes directly affected by that edge and their downstream neighbors. Each edge update triggers a linear scan of related nodes, and with k such updates, the total re-planning cost scales linearly with k*m. Since each edge is processed a constant number of times per update, this holds true for the cumulative cost.

Space Complexity #

O(n + m)

Derivation #

D* needs to store:

• The graph structure (adjacency lists) which takes O(n + m) space (storing all nodes and their connected edges).
• The open list (priority queue), which in the worst case holds all n nodes, adding O(n) space.
• Auxiliary data for each node (like cost-to-go values, state flags), which is O(n) space.
  Adding these up, the total space scales linearly with the number of nodes and edges.

D* Lite is an optimized successor to D*, designed to reduce redundant computations and use a forward search approach with smarter priority queue management.

Time Complexity #

• Static Environment: O(m + n log n)
• Dynamic Environment (with k edge cost updates): Cumulative time is O(m + n log n + k log n)

Derivation #

D* Lite uses a forward search (from start to goal) and maintains two key values for each node: g (actual cost from start to node) and rhs (the "right-hand side" value, an estimate of the minimal cost to reach the goal from the node). It relies on a priority queue (typically a binary heap) to select the next node to process.

• Static case: We process each edge once (O(m)) and each node is inserted/extracted from the priority queue a constant number of times. Each heap operation takes O(log n) time, leading to O(n log n) for heap operations—adding up to O(m + n log n).
• Dynamic case: When an edge’s cost changes, D* Lite only updates the rhs values of affected nodes and re-inserts them into the priority queue if needed. Each such update triggers O(log n) heap operations, and with k updates, this adds O(k log n) to the total cost. The initial static planning cost remains O(m + n log n), so the total cumulative time is the sum of these.

Space Complexity #

O(n + m)

Derivation #

Similar to D*, D* Lite requires:

• Adjacency lists for the graph (O(n + m) space).
• Storage for g and rhs values for each node (O(n) space).
• The priority queue, which in the worst case holds all n nodes (O(n) space).
  All these components scale linearly with the number of nodes and edges, leading to an overall O(n + m) space complexity.

内容的提问来源于stack exchange，提问作者J.Dow