审视不同的体验如何为我们在计算问题方面提供新的视角，这经常会给人带来启发。在当前的情况下，这种不同的体验源自居家隔离。与你们中的许多人一样，在写这篇文章的时候，我正在一个处于封锁状态的城市。我们被限制待在家中，只能在购买食物或锻炼身体时外出。
锻炼身体开始变得有些困难，因为我们唯一能做的就是散步。走在街上，我们必须与其他人保持至少两米的距离，因此我们花了大量时间来规划步行路径。我们需要分辨每一个将要走近我们的人，猜测他们会继续走过来还是会拐进一座房子里，然后找到一条前进的路线，以便与他人保持足够的距离。
如果你需要遛狗，事情就会变得更加复杂，因为宠物狗会给问题带来新的活力和新的不确定性。如果附近还有松鼠，路线的选择会变得难上加难，因为大多数宠物狗似乎对捕捉松鼠很感兴趣（尽管它们通常都捉不到）。也许在本文中我们应该简化问题，至少应假设没有松鼠（尽管这样的假设会让宠物狗很不开心）。本文的核心问题是路径规划，这一课题已被部分解决，但遗留的部分仍旧难以攻克，而且它是在智慧城市的发展中常常被忽视的一个因素。
路径规划与智慧城市的联系非常明显。我们发展智慧城市并不是让城市变“聪明”，而是希望它更高效，这将使得更多的人从群体生活中受益，帮助城市更好地为区域乃至整个国家生产产品和提供服务。路径规划可以帮助城市最有效地利用一种关键资源——空间。它可以引导车辆、机器人或者其他实体从一个地点移动到另一个地点，使它们避免与固定的或移动的障碍物发生碰撞。这项技术也可以应用到其他场景，如工厂和仓库之中，帮助避开柱子、墙壁、人、家具、其他车辆，以及松鼠（如果有的话）。
尽管大多数路径规划算法不一定能求出最优解，但这显然是一个与最优化紧密相关的计算密集型问题，通常有一个可行解就足够了。路径规划的基本方法是在20世纪70年代末80年代初发展起来的，当然也可以很容易地找到一些更早的相关工作，文献[1]概述了解决该问题的基本方法。
从一开始，路径规划就面临着一个特殊的挑战：一方面它需要大量的计算，另一方面我们又常常希望它可以实时进行。我们想为行进中的车辆设置路径，以穿过拥挤的城市街道，或是堆满货物的仓库地板。我们已经看到了许多关于低能耗和边缘计算路径规划的最新工作，但这些工作还不能完全解决如何确定从一个地点到另一个地点的完美路径问题。因此，我们采用了一些传统的工程解决方案，例如限制车辆的路线选择，事先规划尽可能多的路线等。当所有的方法都失效时，我们将通过限制流量来改善路况。
在过去5年左右的时间里，该领域的主要进展是不断发展的采样算法。这些算法通过识别出一组可用于创建基本路径的关键位置集合，简化了车辆所必须通过的空间。然后路径规划软件的任务就变得简单得多：连接这些节点以形成一条可行的路线，并确保在每一段上都不会发生碰撞。最近的一篇综述指出：“基于采样的方法给路径规划领域带来了革命性突破，这些方法通常易于实现，并且可以在机器人上部署[2]。”
在我看来，基于采样的路径规划者似乎在模仿人类规划路线的方式，尤其是当我们在出行受限的大街上遛狗时，而且宠物狗还在不停地搜寻模型中不一定存在的松鼠。我们会提前做一个粗略的路线规划，连接路线上的主要地标，并在遇到障碍物、行人或者松鼠等改变了我们的约束条件时不断地调整路线。但是我猜想，真正的挑战将是理解不同的路径规划者与路径规划算法之间是如何相互作用的，以及这些作用在异构环境中给路径规划者带来的后果。
许多评论员认为，随着新冠疫情全球大流行所暴露出来的在密集环境中生活的种种问题，我们将向着一个居住更加分散化的世界发展。我对此深表怀疑。城市是财富的来源，我们不会因为一场传染病的大流行而放弃城市。即使我们这样去做，我们也必须将规模更小的生产中心和人群连接起来，这将导致更加复杂的路径规划问题。未来无人机配送服务得到推广后，我们将不得不面对这样的问题：如何让成群的飞行器从一个地点移动到另外一个地点，再从那里返回，还要在这个过程中避免相互碰撞，并避开挡在飞行路线上的大量障碍物。
在我回顾最近的文献时，我发现了一篇有趣的文章《跳跃超级英雄的弹道路径规划》（Ballistic Motion Planning for Jumping Superheroes）[3]。该文章的方法可能适用于自动飞行的无人机编队，或者帮助陆地上的松鼠躲开过于急切的宠物狗。它是一篇写给视频游戏设计者的文章，提出了一种用于规划超级英雄在建筑物之间来回跳跃的技术。过去的经验反复地提醒着我们，人类总会面临从未预料到的新问题，而解决这些问题需要有创意、广泛且行之有效的方案，即使这些方案设计的初衷可能是为了其他目的。 ■