AtsushiSakai / AtsushiSakai/PythonRobotics

[Optimization] Enhancing D* Lite performance using heapq and lazy deletion

Abierto
#1,333 0 comentarios 0 reacciones 0 asignados Ver en GitHub
Lenguaje dominante
Python
Estrellas
30.5k
Forks
7.4k
Merge medio
1 d 9 h
PR fusionados (30 d)
3

Descripción

Hi,

The current implementation of the D* Lite algorithm in `PathPlanning/DStarLite` uses a standard Python list for the priority queue `U`, which is sorted using `.sort()` during every `update_vertex` and `compute_shortest_path` call. This leads to a time complexity of approximately $O(n \log n)$ for queue operations in each iteration.

I have developed an optimized version that utilizes a **Min-Heap** (`heapq`) and an **Entry Finder** dictionary to implement **Lazy Deletion**. This reduces the complexity of priority queue updates to $O(\log n)$ and lookups to $O(1)$.

### Reason for Change
1. **Scalability:** The current sorting-based approach becomes significantly slow as the grid size increases or when the map has high-frequency obstacle updates.
2. **Efficiency:** Using `heapq` with a dictionary for node tracking is the standard, high-performance way to implement incremental search algorithms.

### Proposed Changes
* Replace the `list.sort()` mechanism with `heapq`.
* Introduce an `entry_finder` to handle node priority updates efficiently.
* Maintain consistency in the animation logic with the existing implementation.

I have already implemented and tested these changes locally and would like to submit a Pull Request.

Guía de contribución

Abrir la guía de contribución

Línea de trabajo

Comienza en PathPlanning/DStarLite e inspecciona cómo se ordena la lista U durante update_vertex y compute_shortest_path. Compara el comportamiento actual de la cola con heapq de Python y con el enfoque propuesto de eliminación diferida mediante entry_finder, incluida la lógica de animación. Se considera completado cuando las actualizaciones de la cola evitan ordenar repetidamente la lista y preservan el comportamiento y la animación existentes de D* Lite.

Escrito por el modelo de indexación a partir del texto del issue.

Evaluación

Stack tecnológico
python
Área
robotics
Tipo de issue
Refactorización
Dificultad
4/5
Tiempo estimado
3-5 días
Estado de actividad
Estancado
Claridad
Bastante claro
Aptitud para principiantes
45/100

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.