Attraction, Repulsion, and Facility Location

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

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

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