Attraction, Repulsion, and Facility Location

吸引力、排斥力和设施位置

• 批准号: RGPIN-2020-05404
• 负责人: Shermer, Thomas
• 金额: $ 1.75万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750576
• 关键词: Attraction; Repulsion; Facility; Location

My main objective is to investigate algorithms and basic mathematics for attraction and repulsion, with a focus on facility location problems. Attraction (also known as beacon attraction) was recently introduced by Biro with substantial other work from Kostitsnya and Kouhestani. In this model, an activated beacon will cause all particles to move directly towards it, or to slide along a wall if that brings it closer to the beacon. (Here the particles model robots, or messages in a network.) Bose and I introduced a corresponding notion of repulsion. The attraction relation includes visibility, and visibility has a rich theory with many algorithms and combinatorial results. Finding counterparts of these results for attraction is a wide open and exciting new direction, but it also encounters difficulties, often to do with the fact that attraction is not a symmetric relation, whereas visibility is. It is thus ripe for serious study. The study of repulsion encounters even more difficulties than attraction. Visibility and attraction are relations amongst two points (point a can see point b, or a can attract b), and thus their problem formulations and some methodology regarding them are derived from graph theory. Repulsion is a relation amongst three points: point a can repulse point b to some third point c. Therefore even the usual problem formulations may not apply; this makes the area of repulsion particularly interesting. I intend to employ classic computational geometry methodology in my investigation of these topics. This involves studying the basic geometry and combinatorial properties of the relations and designing algorithms that use these properties to answer questions about particular situations. For example, one particular problem that I will investigate is how to preprocess a polygonal domain D so that one may efficiently answer questions of the form: given an attraction beacon b and a point p in D, where does the point p move to if we activate the beacon b? Here, we also get a meaningful question if we replace the attraction beacon with a repulsion actuator. The intended research is a mix of basic research (studying the geometric and combinatorial properties of these relations) and applied research (designing algorithms to answer relevant questions). There are at least three possible application areas of this study. The first is in message routing in sensor networks; the idea of greedy geographical routing is a discretization of attraction. The second application would be in robotics, to understand the behaviour of a robot operating to move towards (attraction) or away from (repulsion) a homing beacon. A third application might be in modelling crowd behaviour, where there may be stimuli of attraction (a place where everyone wants to be) and repulsion (a place that everyone wants to get away from, such as a fire).

我的主要目标是研究吸引和排斥的算法和基本数学，重点是设施选址问题。吸引(也称为灯塔吸引)是比罗最近介绍的，科斯提斯尼亚和库赫斯塔尼也做了大量的其他工作。在这个模型中，被激活的信标将导致所有粒子直接向它移动，或者沿着墙滑动，如果这使它更接近信标的话。(这里的粒子是机器人的模型，也就是网络中的消息。)玻色和我引入了一个相应的斥力概念。吸引关系包含可见性，可见性有丰富的理论，有许多算法和组合结果。为吸引力找到这些结果的对应物是一个开放而令人兴奋的新方向，但它也遇到了困难，通常与吸引力不是对称关系，而可见性是对称关系的事实有关。因此，认真研究它的时机已经成熟。排斥力的研究遇到了比吸引更多的困难。可见性和吸引力是两点之间的关系(点a可以看到b点，或者a可以吸引b点)，因此它们的问题公式和有关它们的一些方法都是从图论中推导出来的。排斥力是三个点之间的关系：a点可以将b点排斥到c点。因此，即使是通常的问题公式也可能不适用；这使得排斥区域特别有趣。我打算用经典的计算几何方法论来研究这些话题。这包括研究关系的基本几何和组合属性，并设计使用这些属性来回答特定情况下的问题的算法。例如，我将研究的一个特定问题是如何对多边形域D进行预处理，以便人们可以有效地回答以下形式的问题：给定一个吸引信标b和D中的一个点p，如果我们激活信标b，点p会移动到哪里？在这里，我们也得到了一个有意义的问题，如果我们用排斥致动器取代吸引信标。预期的研究是基础研究(研究这些关系的几何和组合性质)和应用研究(设计回答相关问题的算法)的混合体。这项研究至少有三个可能的应用领域。第一个是传感器网络中的消息路由；贪婪地理路由的思想是吸引力的离散化。第二个应用将在机器人学中，以了解机器人向(吸引)或远离(排斥)归位信标移动的行为。第三个应用可能是模拟人群行为，其中可能有吸引(每个人都想去的地方)和排斥(每个人都想离开的地方，比如火灾)的刺激。