问题标签 [planning]

我正在编写一个小型软件应用程序，该应用程序需要用作当地学校的简单规划工具。它需要解决的“问题”是相当基本的。也就是说，教师需要与所有孩子的父母交谈。但是，有些孩子当然有兄弟姐妹在不同的小组，所以这些谈话需要安排在彼此旁边，以避免父母在晚上 6 点谈话和晚上 10 点谈话的情况。因此，简而言之，给定n 个孩子的集合，其中一些孩子有 1 个或多个兄弟或姐妹，生成一个时间表，其中这些孩子的所有谈话都安排在彼此旁边。

现在，也许这个问题可以非常容易地解决，但另一方面我感觉这可能是一个非常复杂的问题，需要并且可以用某种算法来解决。优雅地。但我说得对吗？有没有？我看过匈牙利算法，但它并不完全适用于这个特定问题。

编辑：我忘了提，所有的谈话都需要同样的时间。

谢谢！

有人知道用 Python 或 Java 实现的分层任务网络规划器吗？我发现了一些开源系统，但它们都是看似死气沉沉的项目，并且多年没有得到维护。

我正在尝试创建一个简单的基于STRIPS的规划器。我已经完成了计算将达到目标的单独概率计划的基本功能，但现在我正在尝试确定如何根据它们的初始操作聚合这些计划，以确定在时间 t0 的“整体”最佳操作是什么.

考虑以下示例。效用，介于 0 和 1 之间，表示计划实现目标的程度。CF 也介于 0 和 1 之间，表示确定性因子，或执行计划将产生给定效用的概率。

如果所有三个互斥的计划都从动作 A1 开始，我应该如何聚合它们以确定使用动作 A1 的整体“适合度”？我的第一个想法是将确定性因素相加，然后乘以公用事业的平均值。这看起来正确吗？

所以我目前的结果看起来像：

或者我应该计算个人可能的效用，然后取平均值？

有没有理论上更合理的方法？

我试图找到网格中 2 个节点之间的所有路径，并且路径必须从头到尾穿过所有节点。示例（开始 = S，结束 = E）

0 0 0
0 S 0
0 0 E

上面的答案是 2 条路径：（忽略 '.''s）

0-0-0
|.......|
0 S-0
|
0-0-E

0-0-0
|......|
0 S 0
|...|...|
0-0 E

我想过使用递归，但由于每次调用的高开销而放弃了......并决定使用堆栈的迭代方法。（有点像递归但不是......固定的内存开销）。该解决方案适用于大小（4x7）的网格，但在 8x8 网格上进行了尝试……但它没有在 4 小时内完成……这是有道理的，因为可能性的总数约为 3** 62（大约），因为不在边缘的每个节点都有 3 种可能的遍历方式......因此该解决方案失败了。

我想过将 8x8 网格分成 2 个，使用垂直和水平分割......但这会导致找到不太理想的路径。

有什么我想念的吗？？？？可以做些什么来让它更快吗？我将发布我明天的解决方案（在 C 中完成）。

是否有任何软件可以充当当代 OWL/RDF 推理器与旧的STRIPS风格的自动计划器和调度器之间的交叉点？两个系统都使用基于 RETE 的模式匹配，但似乎只有自动规划器将“动作”的概念形式化。不幸的是，我发现的所有项目都实现了自动化规划，比如Graphplan或SOAR，似乎已经死了或垂死了，而且似乎从一开始就没有很好地扩展。当前的数据存储是在 RDMS 上实现的，可以扩展到数百万个三元组并进行推理，但我还没有找到任何专门尝试和推理动作的数据存储。我可以设想如何在传统的 RDF 中表示动作的概念，但我敢肯定，如果没有官方支持，它仍然会非常复杂和骇人听闻。不幸的是，我找不到太多的现有技术。以前有这样做过吗？

所有强化学习我读过的算法通常应用于具有固定数量动作的单个代理。是否有任何强化学习算法可以在考虑可变数量的动作的同时做出决策？例如，您将如何在一个玩家控制 N 个士兵的计算机游戏中应用 RL 算法，并且每个士兵根据其条件有随机数量的动作？您无法为全局决策者（即“将军”）制定固定数量的行动，因为随着士兵的创建和杀死，可用的行动会不断变化。而且你不能在士兵级别制定固定数量的行动，因为士兵的行动是基于其直接环境的条件。如果一个士兵看不到对手，那么它可能只能走路，

Let's assume food delivery for multiple restaurants (say 20). There are (say 10) drivers available. Further, let's say we get 100 orders over a 4 hour period to deliver food from these restaurants to homes.

So drivers have to be coordinated to pickup food at a location and deliver to customers at home.

Primary goal is to minimize time to delivery, i.e. time between order and arrival at homes. The secondary goal is to maximize driver capacity (i.e., least amount of time to deliver all orders).

Bear in mind that the orders come in over a four hour period, so let's say evenly, i.e. one very 3 minutes. Also, let's assume the orders are randomly to the 20 restaurants.

Assume that I can calculate time to travel from any location to a destination to the second.

I know the location of all drivers in realtime. I also know their statuses, i.e. are they currently on their way to pick up an order (to take to a known destination), have they already picked up an order and are enroute to a known destination.

Constraints are: 1) Must pick up an order after a given time (i.e. meal preparation time for restaurant) 2) Must deliver order in under 45 mins (otherwise alert thrown) 3) Must pad time with "x" minutes to accommodate for time spent walking to store to pickup order, etc. 4) Must pad time with "y" minutes to accommodate for time spent delivering order to customer and collecting payment. 5) Drivers have only a given set of payment methods (e.g. Cash, Visa, Amex, MasterCard). We must match customer request (cash, visa, etc) with driver capability (cash, visa, amex, etc).

So for example, if I get two orders with close by destination and close by pickup locations, even if there is another "Free" driver (not doing anything), it would be more efficient to use the same driver to pickup both orders and deliver both orders.

You can assume there will be delivery zones enforced for each restaurant, meaning, most people ordering from them will most likely be close to them. Therefore, this algorithm should manage to segment drivers automatically into city zones, and favor drivers within the zone already.

我正在尝试在 C 中实现一些 AI 规划算法，但被基本概念卡住了 :)
在跳到主要问题之前，我尝试实现一些支持命题逻辑的小框架：

现在，问题是我不想在定义公式时评估像 'a + 3 > 0' 这样的表达式，而是在以后的某个阶段：

我想在这种情况下闭包会很方便，但不幸的是我也喜欢坚持使用 C99。

任何的想法 ？
将其扩展到谓词逻辑怎么样？

最终目标（理想情况下）是构建一个 AI 规划库，可以直接插入到应用程序中，而不是将问题作为 STRIPS 程序字符串接收。

谢谢

您将如何获得描述街道互连和估计驾驶时间的图表，并使用 Python 对其进行解析？

作为练习，我正在尝试实现一个基本的 A* 规划器来绘制在地图上的两点之间导航的路线（即 TomTom、Garmin、Google Nav 等）。我可以模拟一些数据，但如果可能的话，我想使用真实的地图数据。

我知道Open Street Map，虽然他们允许将地图的一小部分导出到 OSM XML 数据中，但我很难找到工具来轻松解析我可以使用的表单。我找到了 imposm，但没有别的了。任何人都可以推荐任何其他工具吗？

有人知道为任务创建最佳时间表的工具吗？我有许多服务器，运行多个数据库，以及从每个数据库导入和转换数据的各种脚本。

我目前正在手动安排各种 cronjobs，但这很容易出错并且难以解释异常情况，例如由于异常大的数据负载而需要异常长时间运行的作业。我正在考虑对每个任务之间的资源和依赖关系进行编码，并创建一个规划器来搜索任务执行的最佳顺序，以便每个任务在最不可能干扰任何其他任务的时间运行。

我见过Drools Planner，但它不合适，因为它具有巨大的复杂性和开销。