简介

基于样本的运动规划。

本项目旨在作为几个通用思想的Educational Replication。

• 稀疏性
• 运动基元
• 重要性抽样

本项目的子目标是将这些思想的一些优势集成到混合解决方案中。

程序输入

• 系统动力学和各种约束以函数形式提供
• 环境障碍物

包含内容

• 稀疏性
  • 稳定的稀疏RRT (https://www.cs.rutgers.edu/~kb572/pubs/stable_sparse_rrt_WAFR14_LLB.pdf)
  • 使用随机搜索的近似最近邻
• 运动基元
  • 查找可行的控制以向特定方向转向 (https://arxiv.org/pdf/1809.02399.pdf)
  • 编译标志，启用其使用
  • 适用于运行时查找填充的修改版
  • 基于非网格的贪婪目标邻域搜索
• 重要性抽样
  • 自适应采样 (https://journals.sagepub.com/doi/pdf/10.1177/0278364912444543)
  • 用于具有给定适应度函数的轨迹优化

论文、基准等

项目

运行规划器

• 先决条件
  • 安装Rust: https://rustup.rs/
  • 互联网连接（构建项目时需要拉取软件依赖项）
  • Make（如果使用自定义地图，则构建三角剖分工具，或从： https://www.cs.cmu.edu/~quake/triangle.html 获取可执行文件）
• 以发布模式构建和运行
  • 要么
    • 已经生成了自定义地图（请参阅生成自定义地图部分）
    • cargo run --release --bin planner -- -p <problem_instance_name> (其他程序参数...)
    • 请参阅prob_instances.rs以获取预定义的问题领域列表
  • 要么
    • cargo run --release --bin planner -- -o <file_obstacle> (其他程序参数...)
    • 示例障碍物文件：obstacles/obs3.txt（随机生成的盒子）
  • 要么
    • 已经生成了自定义地图（请参阅生成自定义地图部分）
    • cargo run --release --bin planner -- -e <.ele文件路径> -n <.node文件路径> (其他程序参数...)
      • 例如：cargo run --release --bin planner -- -e maps_custom/dragon_age/poly/ost100d.1.ele -n maps_custom/dragon_age/poly/ost100d.1.node -p orz000d -i 1000000 -b 300 -m dubins
    • 需要修改动力学模型文件以更改目标状态等
    • 请参阅自定义地图部分以获取关于(ele和.node)的详细信息
• 可选参数
  • 显示见证节点和见证代表对
    • 以红色线条绘制，端点分别为（紫色：见证），（蓝色：见证代表）
  • -i <N>：最大迭代次数
  • -m <model>：动态模型选择（见 src/dynamics_* 文件）
    • 变体：Dubins，飞机（默认为Dubins）
  • -b <N>：在渲染调用之间批量执行N次迭代
  • -h：帮助
• 可选编译时功能
  • 用法
    • cargo run --release --bin planner --features nn_naive,disable_pruning,(其他功能...) -- -p <problem_instance_name> (其他程序参数...)
  • 变体：查看 Cargo.toml 的 [features] 部分
• 示例程序
  • cargo run --release --bin planner --features nn_sample_log,state_propagate_sample,path_optimize -- -p obs3 -m dubins -i 1000000 -b 200

生成随机障碍物（障碍物/文件夹中存在一些障碍物）

• 使用 cargo run --release --bin gen_obs -- -f <output_file_path> 构建和以发布模式运行
• 必需参数
  • -f <output_file_path>（例如：cargo run --release --bin gen_obs -- -f obstacles/obs99.txt）
• 可选参数
  • -n <N>：要生成的障碍物数量（默认：30）
• 可选功能
  • gen_obs_3d：在3D域内生成盒子（默认为平面域）

使用随机障碍物

• cargo run --release --bin planner -- -o <file_obstacle>
  • -o <file_obstacle>：障碍物文件路径（例如：-o obstacles/obs2.txt）

生成自定义地图（需要运行一次才能使用自定义地图）

• 一组主要用于基准测试的地图，可从https://www.movingai.com/benchmarks/grids.html 获取，这些地图位于 /maps_custom 文件夹中
• 地图内的可移动空间被三角剖分以作为规划器中的配置自由空间使用
• 使用来自http://www.cs.cmu.edu/~quake/triangle.html 的Triangle软件进行三角剖分
• 地图被转换为Triangle处理和输出的格式，输出可以加载到我们的规划器中，并进一步扩展为三角形棱柱，用于通用3D障碍物检测器，这些中间文件存储在 /maps_custom//poly 中
• 一些地图可能存在不良的三角剖分，无法用于规划器（我旨在与Dragon Age地图一起使用）
• 为我们的规划器生成中间文件和地图资源
  • 1. 首先编译Triangle
    • cd Triangle_v1_6
    • make
  • 2. 运行 ./script_map2poly.sh（为Triangle生成格式化文件，可能需要一些时间）
  • 3. 运行 ./script_triangulate_poly.sh（输出二维三角剖分结果为 .ele 和 .node 文件）
  • 一切准备就绪...

截图

简单环境

困难游戏地图