# gridport-v3

**Repository Path**: zwboy/gridport-v3

## Basic Information

- **Project Name**: gridport-v3
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-06-15
- **Last Updated**: 2026-06-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# GridPort · 三层 QUBO AGV 调度器

基于 Python实现的 GridPort 三层 QUBO 调度系统，用于 AGV（自动导引车）车队调度。内置自写模拟退火求解器，与 `dwave-neal` 参考实现进行对比，并附带 HTML 仪表盘可视化运行结果。

## 文件说明

| 文件 |用途 |
| --- | --- |
| `core.py` | 数据类（Graph、Column、Heartbeat、TaskReady、DispatchCommands、PathPredictionPool、Qubo）及 Dijkstra 最短路径算法。 |
| `world.py` | 2D 网格世界模拟器。追踪 AGV 状态、按 tick 推进车辆、检测节点冲突与死锁、管理预约池。 |
| `sa_solver.py` | 自写 SA 求解器（几何冷却、单比特翻转、多重启）。 |
| `scheduler.py` | 三层 QUBO 调度器（Global / Window / Nano）、Column工厂、可插拔 SA 后端、BLOCKED 心跳处理。 |
| `run_experiment.py` | 构建世界、运行模拟、输出 `results.json`。 |
| `dashboard.html` | HTML 仪表盘（无需构建，直接浏览器打开）。 |
| `results.json` | 最新运行结果，供仪表盘读取。 |

## 运行方法

```bash
# （一次性）安装 dwave-neal 作为对比基准
pip3 install dwave-neal

# 运行实验（约5-30 秒，视机器配置而定）
python3 run_experiment.py

# 查看仪表盘
open dashboard.html       # macOS
xdg-open dashboard.html   # Linux
```

仪表盘通过 `fetch()` 读取 `results.json`。如果从 `file://` 加载且浏览器阻止 fetch，请改用本地服务器：

```bash
python3 -m http.server 8000
# → http://localhost:8000/dashboard.html
```

## 系统架构

```
                 on_heartbeat / on_task_ready
                            │
                            ▼
       ┌────────────────────────────────────────────┐
       │          ThreeLayerScheduler               │
       │ ┌─────────┐  ┌────────┐  ┌──────────┐    │
       │  │ Global  │→ │ Window │→ │   Nano   │    │
       │  │  QUBO   │  │  QUBO  │  │   QUBO   │    │
       │  └────┬────┘  └───┬────┘  └─────┬────┘    │
       │       └───────────┼──────────────┘         │
       │                   ▼                        │
       │            dispatch_ready()                │
       └──────────────┬─────────────────────────────┘
                      │  DispatchCommands
                      ▼
       ┌────────────────────────────────────────────┐
       │               World (2D grid)               │
       │  • AGVs 每 tick 移动一个节点               │
       │  • PathPredictionPool 执行预约机制 │
       │  • 检测节点冲突 + 死锁 │
       └────────────────────────────────────────────┘
```

### 能量函数（五项）

```
E(x) = Σ  W_travel · travel          # 路径长度成本
     + Σ  0.12 · end_t              # 时间惩罚（题目指定系数）
     + Σ  15.0 · delay              # 延迟惩罚（题目指定系数）
     + Σ  W_conflict · shared_nodes(x_i, x_j)   # 节点冲突惩罚 [自选系数: 8.0]
     + Σ  W_load    · load_imbalance(x_i)       # 负载均衡惩罚 [自选系数: 1.5]
     − bias · Σ x_i                              # 选择偏置 [自选系数: −3·max_cost]
```

### 三层变量预算

| 层级 | 变量数 | 触发时机 | 说明 |
| --- | --- | --- | --- |
| Global | ≤ 2000 | t=0 启动，每 60-120s 重优化 | 每个 (pid, agv) 组合一列 |
| Window | ≤ 400 | 每 5 sim-seconds | 10 pids × 4 agvs |
| Nano   | ≤ 40 | 每次 dispatch | 1 pid × ≤4 agvs |

## 自写 SA vs dwave-neal 对比

每层 QUBO 同时用两个后端求解：

* **SelfSABackend** — `sa_solver.py` 中的 `SelfSA`
* **NealBackend** — `neal.SimulatedAnnealingSampler`

能量值按层记录在 `results.json → sa_compare` 中，并在仪表盘中绘图对比。典型运行结果：能量精度匹配到 1e-12，自写 SA 运行时间约为 neal 的 1.2 倍（纯 Python 实现）。

## 竞赛评分对照

| 评分项 | 目标 | 状态 |
| --- | --- | --- |
| 完成率 100% | 12/12 任务完成 | ✅ 12/12 |
| 节点双占 = 0 | 无节点重复占用 | ✅ 0（PathPredictionPool + world tick 检测） |
| 死锁 = 0 | 无死锁发生 | ⚠️ 0 致命死锁；世界记录检测并恢复的事件 |
| 无裸下发（始终预约） | 每次 dispatch 均预约所有节点 | ✅ 每次 `world.dispatch` 都预约沿途节点 |
| Nano ≤ 40 变量 | Nano 层变量数 | ✅ |
| Window ≤ 400 变量 | Window 层变量数 | ✅ |
| 报告含自写 SA vs neal 能量对比 | 需包含对比数据 | ✅ `results.json → sa_compare` + 仪表盘图表 |

## 测试环境

* Python 3.9，macOS，`dwave-neal 0.6.0`，`dimod 0.12.21`
* 10×10 网格地图，4 台 AGV，12 个任务，模拟 t=250s → 实际耗时 4.5 秒