DPS调度算法详解 - 版本历史

Artheru：/* 使用搜索方法来预测/规划多车之间的通行顺序。 */

2024-11-27T09:48:28Z

使用搜索方法来预测/规划多车之间的通行顺序。

←上一版本		2024年11月27日 (三) 17:48的版本
第41行：		第41行：
	* 当一台车请求获取新资源时，系统会模拟其他车辆的推进过程，检查是否存在死锁风险		* 当一台车请求获取新资源时，系统会模拟其他车辆的推进过程，检查是否存在死锁风险

	* 如果所有车辆都能推进到各自的目标位置，则允许该车获取资源；否则视情况拒绝请求这种方法虽然不能保证找到最优解，但能在可接受的时间内找到可行解，且能有效预防死锁的发生。在实践中，我们还引入了"汇点"（永远允许通过）和"逃逸路径"~~（当检测到死锁风险时的备选路径）等机制来提高系统的鲁棒性。（ai配图~~-推进算法示意）		* 如果所有车辆都能推进到各自的目标位置，则允许该车获取资源；否则视情况拒绝请求这种方法虽然不能保证找到最优解，但能在可接受的时间内找到可行解，且能有效预防死锁的发生。在实践中，我们还引入了"汇点"（永远允许通过）和"逃逸路径"（当检测到死锁风险时的预备路径）等机制来提高系统的鲁棒性。（ai配图-推进算法示意）

	=== 实际工程需要处理地细节问题 ===		=== 实际工程需要处理地细节问题 ===

2024年11月27日 (三) 09:47 Artheru

2024-11-27T09:47:31Z

←上一版本		2024年11月27日 (三) 17:47的版本
第41行：		第41行：
	* 当一台车请求获取新资源时，系统会模拟其他车辆的推进过程，检查是否存在死锁风险		* 当一台车请求获取新资源时，系统会模拟其他车辆的推进过程，检查是否存在死锁风险

	* 如果所有车辆都能推进到各自的目标位置，则允许该车获取资源；否则视情况拒绝请求这种方法虽然不能保证找到最优解，但能在可接受的时间内找到可行解，且能有效预防死锁的发生。在实践中，我们还引入了"汇点"（永远允许通过）和"~~逃生路径~~"（当检测到死锁风险时的备选路径）等机制来提高系统的鲁棒性。（ai配图-推进算法示意）		* 如果所有车辆都能推进到各自的目标位置，则允许该车获取资源；否则视情况拒绝请求这种方法虽然不能保证找到最优解，但能在可接受的时间内找到可行解，且能有效预防死锁的发生。在实践中，我们还引入了"汇点"（永远允许通过）和"逃逸路径"（当检测到死锁风险时的备选路径）等机制来提高系统的鲁棒性。（ai配图-推进算法示意）

	=== 实际工程需要处理地细节问题 ===		=== 实际工程需要处理地细节问题 ===

2024年11月27日 (三) 07:40 Artheru

2024-11-27T07:40:51Z

←上一版本		2024年11月27日 (三) 15:40的版本
第1行：		第1行：
	~~--AI gen introduction--~~

	实际上AGV调度系统问题已经被研究的很多了，这个问题的有很多相关的纯数学研究，如 Flowshop scheduling:https://en.wikipedia.org/wiki/Flow-shop_scheduling<nowiki/>。在Simple的调度逻辑中，我们使用以下思路：		实际上AGV调度系统问题已经被研究的很多了，这个问题的有很多相关的纯数学研究，如 Flowshop scheduling:https://en.wikipedia.org/wiki/Flow-shop_scheduling<nowiki/>。在Simple的调度逻辑中，我们使用以下思路：

第8行：		第6行：

	====== 使用动态规划方法来规划两车之间的通行顺序。 ======		====== 使用动态规划方法来规划两车之间的通行顺序。 ======
	~~使用动态规划方法来规划两车之间的通行顺序。设矩阵D~~[i,j]表示车A获得了第i个资源、车B获得了第j个资源时的状态。D[i,j]=1表示该状态可达，D[i,j]=0表示该状态不可达。那么有如下状态转移方程：		使用动态规划方法来规划两车之间的通行顺序。设通行矩阵D[i,j]表示车A获得了第i个资源、车B获得了第j个资源时的状态。D[i,j]=1表示该状态可达，D[i,j]=0表示该状态不可达。那么有如下状态转移方程：

	D[i,j] = 1 当且仅当：		D[i,j] = 1 当且仅当：

第16行：		第15行：
	** D[i-1,j]=1 且车A从i-1到i的路径不与车B在j位置发生冲突		** D[i-1,j]=1 且车A从i-1到i的路径不与车B在j位置发生冲突
	** D[i,j-1]=1 且车B从j-1到j的路径不与车A在i位置发生冲突		** D[i,j-1]=1 且车B从j-1到j的路径不与车A在i位置发生冲突
	** D[i-1,j-1]=1 ~~且两车同时移动不发生冲突~~		<math>D[i,j] =
	边界条件为D[0,0]=~~1。如果D~~[m,n]=1则说明存在可行的通行顺序。（ai配图-动态规划状态转移）		\begin{cases}
	这个动态规划算法的时间复杂度为O(mn)，空间复杂度为O(mn)。在实际实现中，我们使用一个1024''1024的循环数组来存储这个状态矩阵，并用位运算来记录更多的状态信息（如是否检查过该状态、是否存在轨道冲突等）。''		1, & \text{if and only if all the following conditions are satisfied:} \\
			& (i,j)\text{-th resource has no direct conflict} \\
			& \quad \text{and} \\
			& (D[i-1,j]=1 \land \text{path of A from } i-1 \text{ to } i \text{ does not conflict with B at } j) \\
			& \quad \lor \\
			& (D[i,j-1]=1 \land \text{path of B from } j-1 \text{ to } j \text{ does not conflict with A at } i) \\
			0, & \text{otherwise}
			\end{cases}</math>

			边界条件为D[0,0]=1，意为AB辆车初始状态没有冲突。如果D[m,n]=1则说明存在可行的通行顺序。（ai配图-动态规划状态转移）

			这个动态规划算法的时间复杂度为O(mn)，空间复杂度为O(mn)。在实际实现中，我们使用一个1024x1024的二维循环数组来存储这个状态矩阵，并用位运算来记录更多的状态信息（如是否检查过该状态、是否存在道路冲突等）。

			这种动态规划方法可以处理大多数冲突类型：如基于[[使用手册 - Simple:包络如何定义\|包络]]判断运动路线冲突、[[可达性状态编程\|可达性]]等；只要能将这些约束规约为两车之间的约束的都能使用通行矩阵表达。这些冲突类型仅仅是增加了一些状态递推时判断的条件。

	====== 使用搜索方法来预测/规划多车之间的通行顺序。 ======		====== 使用搜索方法来预测/规划多车之间的通行顺序。 ======
	~~# 实际工程时，处理以下细节问题：~~		虽然使用动态规划方法已经能够遍历地处理两车之间地通行情况，然而当车辆数量超过2台时，问题的复杂度会急剧上升。对于N台车的情况，如果仍然使用类似的动态规划方法，需要一个N维的状态矩阵，时间复杂度将达到O(M^N)，其中M为平均每台车需要获取的资源数量。这在实际应用中是不可接受的。
	## 每个“进程”，aka，车：虽然最少拿到两个资源。不一定会拿到下一个资源时立刻释放上一个资源。
	## 路线可能只发一半，可能到了某个位置后才会确认车辆接下来继续走到哪里，但那个位置会堵塞交通，导致路线规划不了。（使用escape）		SimpleCore中采用了一种启发式的"推进"算法来处理多车的情况：
	## 比较复杂的冲突关系，包括业务冲突、运动路线冲突等。（使用包络）
	## 路线可能会因为业务的改变而中途改变，立刻停车位置可能堵塞交通，继续行走浪费里程（使用劫持）		* 首先使用上述动态规划方法计算任意两车之间的可行通行顺序
	## 有些车因为业务需要，需要相对于其他车提前到达某个点来操作。（使用资源冲突矩阵）
	## 配发资源的时候需要最优化发放顺序。虽然可能多种方案都可行，但可能有些方案更好。（Johnson's rule）https://en.wikipedia.org/wiki/Johnson%27s_rule		* 当一台车请求获取新资源时，系统会模拟其他车辆的推进过程，检查是否存在死锁风险

			* 如果所有车辆都能推进到各自的目标位置，则允许该车获取资源；否则视情况拒绝请求这种方法虽然不能保证找到最优解，但能在可接受的时间内找到可行解，且能有效预防死锁的发生。在实践中，我们还引入了"汇点"（永远允许通过）和"逃生路径"（当检测到死锁风险时的备选路径）等机制来提高系统的鲁棒性。（ai配图-推进算法示意）

			=== 实际工程需要处理地细节问题 ===
			以上是一个大致的系统描述，在实际工程应用中还需要处理以下问题：
			# 每个“进程”，aka，车：虽然最少拿到两个资源。不一定会拿到下一个资源时立刻释放上一个资源。
			# 路线可能只发一半，可能到了某个位置后才会确认车辆接下来继续走到哪里，但那个位置会堵塞交通，导致路线规划不了。（使用escape）
			# 比较复杂的冲突关系，包括业务冲突、运动路线冲突等。（使用包络）
			# 路线可能会因为业务的改变而中途改变，立刻停车位置可能堵塞交通，继续行走浪费里程（使用劫持）
			# 有些车因为业务需要，需要相对于其他车提前到达某个点来操作。（使用资源冲突矩阵）
			# 配发资源的时候需要最优化发放顺序。虽然可能多种方案都可行，但可能有些方案更好。（Johnson's rule）https://en.wikipedia.org/wiki/Johnson%27s_rule

2024年11月27日 (三) 07:24 Artheru

2024-11-27T07:24:18Z

←上一版本		2024年11月27日 (三) 15:24的版本
第1行：		第1行：
	--AI gen introduction--		--AI gen introduction--

	~~实际上AGV调度系统问题已经被研究的很多了，这个问题的正式名字叫~~ Flowshop scheduling:https://en.wikipedia.org/wiki/Flow-shop_scheduling		实际上AGV调度系统问题已经被研究的很多了，这个问题的有很多相关的纯数学研究，如 Flowshop scheduling:https://en.wikipedia.org/wiki/Flow-shop_scheduling<nowiki/>。在Simple的调度逻辑中，我们使用以下思路：

	~~为了解决以上调度问题，我们使用以下思路：~~		# 定义交管问题为资源的获取和释放。一个场景中具有多个路点。一台车可以拿着一个或多个路点的占用权。当一台车只拿着一个路点的占用权时，它只能呆在原地不懂。如果它拿着一个或多个路点的权限时，则可在这些路点间任意移动。车不应该处于它没有拿到路点权限的位置。（ai配图）
			# 将交管需求简化为该数学问题：“有N个进程，每个进程各自有M_{n}个要顺序获取的资源R_{mn}，每个进程拿到了下一个资源就会释放上一个资源。问是否存在至少一种资源获取序列，使得所有进程都能拿到最后一个资源？”。（ai配图-问题A）
			我们先考虑两车间的情况：两台车A,B分别要顺序获取m,n个资源。容易想到用一个m*n的矩阵就可以穷尽A,B两车的全部获取资源的状态。于是我们可以得到问题A中N=2的情况的精确解：

	# 定义交管问题为资源的获取和释放。一个场景中具有多个路点。一台车可以拿着一个或多个路点的占用权。当一台车只拿着一个路点的占用权时，它只能呆在原地不懂。如果它拿着一个或多个路点的权限时，则可在这些路点间任意移动。车不应该处于它没有拿到路点权限的位置。（ai配图）		====== 使用动态规划方法来规划两车之间的通行顺序。 ======
	~~# 将交管需求简化为该数学问题：“有N个进程，每个进程各自有M_{~~n~~}个要顺序获取的资源R_{~~mn}，每个进程拿到了下一个资源就会释放上一个资源。有一个资源冲突矩阵C，定义资源两两间是否能同时获取。问是否存在至少一种资源获取序列，使得所有进程都能拿到最后一个资源？”。（ai配图）		使用动态规划方法来规划两车之间的通行顺序。设矩阵D[i,j]表示车A获得了第i个资源、车B获得了第j个资源时的状态。D[i,j]=1表示该状态可达，D[i,j]=0表示该状态不可达。那么有如下状态转移方程：
	~~## 首先考虑冲突矩阵就是单位阵（不考虑过于复杂的冲突情况）。~~		D[i,j] = 1 当且仅当：
	~~## 使用动态规划方法来规划两车之间的通行顺序。~~
	## 使用搜索方法来预测/规划多车之间的通行顺序。		* (i,j)位置的资源不存在直接冲突

			* 满足下列条件之一：
			** D[i-1,j]=1 且车A从i-1到i的路径不与车B在j位置发生冲突
			** D[i,j-1]=1 且车B从j-1到j的路径不与车A在i位置发生冲突
			** D[i-1,j-1]=1 且两车同时移动不发生冲突
			边界条件为D[0,0]=1。如果D[m,n]=1则说明存在可行的通行顺序。（ai配图-动态规划状态转移）
			这个动态规划算法的时间复杂度为O(mn)，空间复杂度为O(mn)。在实际实现中，我们使用一个1024''1024的循环数组来存储这个状态矩阵，并用位运算来记录更多的状态信息（如是否检查过该状态、是否存在轨道冲突等）。''

			====== 使用搜索方法来预测/规划多车之间的通行顺序。 ======
	# 实际工程时，处理以下细节问题：		# 实际工程时，处理以下细节问题：
	## 每个“进程”，aka，车：虽然最少拿到两个资源。不一定会拿到下一个资源时立刻释放上一个资源。		## 每个“进程”，aka，车：虽然最少拿到两个资源。不一定会拿到下一个资源时立刻释放上一个资源。

Artheru：创建页面，内容为“--AI gen introduction-- 实际上AGV调度系统问题已经被研究的很多了，这个问题的正式名字叫 Flowshop scheduling:https://en.wikipedia.org/wiki/Flow-shop_scheduling 为了解决以上调度问题，我们使用以下思路： # 定义交管问题为资源的获取和释放。一个场景中具有多个路点。一台车可以拿着一个或多个路点的占用权。当一台车只拿着一个路点的占用权时，它只能呆在原地…”

2024-04-23T15:39:15Z

创建页面，内容为“--AI gen introduction-- 实际上AGV调度系统问题已经被研究的很多了，这个问题的正式名字叫 Flowshop scheduling:https://en.wikipedia.org/wiki/Flow-shop_scheduling 为了解决以上调度问题，我们使用以下思路： # 定义交管问题为资源的获取和释放。一个场景中具有多个路点。一台车可以拿着一个或多个路点的占用权。当一台车只拿着一个路点的占用权时，它只能呆在原地…”

新页面

--AI gen introduction--

实际上AGV调度系统问题已经被研究的很多了，这个问题的正式名字叫 Flowshop scheduling:https://en.wikipedia.org/wiki/Flow-shop_scheduling

为了解决以上调度问题，我们使用以下思路：

# 定义交管问题为资源的获取和释放。一个场景中具有多个路点。一台车可以拿着一个或多个路点的占用权。当一台车只拿着一个路点的占用权时，它只能呆在原地不懂。如果它拿着一个或多个路点的权限时，则可在这些路点间任意移动。车不应该处于它没有拿到路点权限的位置。（ai配图）
# 将交管需求简化为该数学问题：“有N个进程，每个进程各自有M_{n}个要顺序获取的资源R_{mn}，每个进程拿到了下一个资源就会释放上一个资源。有一个资源冲突矩阵C，定义资源两两间是否能同时获取。问是否存在至少一种资源获取序列，使得所有进程都能拿到最后一个资源？”。（ai配图）
## 首先考虑冲突矩阵就是单位阵（不考虑过于复杂的冲突情况）。
## 使用动态规划方法来规划两车之间的通行顺序。
## 使用搜索方法来预测/规划多车之间的通行顺序。
# 实际工程时，处理以下细节问题：
## 每个“进程”，aka，车：虽然最少拿到两个资源。不一定会拿到下一个资源时立刻释放上一个资源。
## 路线可能只发一半，可能到了某个位置后才会确认车辆接下来继续走到哪里，但那个位置会堵塞交通，导致路线规划不了。（使用escape）
## 比较复杂的冲突关系，包括业务冲突、运动路线冲突等。（使用包络）
## 路线可能会因为业务的改变而中途改变，立刻停车位置可能堵塞交通，继续行走浪费里程（使用劫持）
## 有些车因为业务需要，需要相对于其他车提前到达某个点来操作。（使用资源冲突矩阵）
## 配发资源的时候需要最优化发放顺序。虽然可能多种方案都可行，但可能有些方案更好。（Johnson's rule）https://en.wikipedia.org/wiki/Johnson%27s_rule

DPS调度算法详解 - 版本历史

Artheru：​/* 使用搜索方法来预测/规划多车之间的通行顺序。 */

2024年11月27日 (三) 09:47 Artheru

2024年11月27日 (三) 07:40 Artheru

2024年11月27日 (三) 07:24 Artheru

Artheru：/* 使用搜索方法来预测/规划多车之间的通行顺序。 */