Conflict Resolution and Optimization

冲突解决和优化

• 批准号: 230782768
• 负责人: Professor Dr. Sándor Fekete
• 金额: --
• 依托单位: Institut für Betriebssysteme und Rechnerverbund
• 依托单位国家: 德国
• 项目类别: Research Units
• 财政年份: 2013
• 资助国家: 德国
• 起止时间: 2012-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/230782768?language=en
• 关键词: Conflict; Resolution; Optimization

The main objectives of Phase 1 aim at developing fundamental algorithmic methods for reconfiguration and reallocation, as well as ensuring that they are useful and suitable for the overall objectives of CCC, by engaging in practical collaboration with the other, more applied projects. This is achieved by considering methods that work at different information and optimization scales (e.g., exact global computation by mathematical programming, heuristic approaches by local methods for gradual improvement), different time scales (e.g., more time-consuming methods applied in an offline setting, faster methods for online scenarios, but also a subdivision into preprocessing/query), as well as different computation scales (e.g., centralized computation vs. game-theoretic mechanism design). These scales are often linked (for example, decentralized computation may correlate with limited information), without being methodologically equivalent (e.g., optimization under limited information arises even in centralized scenarios, giving rise to the area of online algorithms). A general approach in the field of algorithmics is to develop separate methods for scenarios at different scales, i.e., to consider one combination of the described scales, and develop powerful methods that work well under these specific conditions.The main overall objective for Phase 2 is to overcome this limitation and study of multi-scale, integrated and interleaving methods for complex scenarios, in which these different scales (information and optimization, time, computation) are not treated separately, but are employed in an interchanging and parallel fashion. This requires blending and unifying the separate algorithmic methods into multi-scale methods, to be carried out within B1, a close interaction with the conceptual approaches and techniques of distributed contract and algorithm design and employment for complex, structured scenarios in collaboration with other projects, and an integration of the overall methods with the other projects in the context of case studies with the partners from the applied projects. Most notably, these involve studying robot platforms and autonomous vehicles, both of which pose relevant scientific challenges, when organizing resource allocation within one robot or vehicle and when coordinating several platforms. Beyond our algorithmic expertise, we have considerable experience in both application areas, making these very promising targets.

第一阶段的主要目标是开发用于重新配置和重新分配的基本算法方法，并通过与其他更多应用项目的实际合作，确保这些方法对CCC的总体目标有用和合适。这是通过考虑在不同信息和优化尺度下工作的方法来实现的（例如，通过数学规划的精确全局计算，通过用于逐渐改进的局部方法的启发式方法），不同的时间尺度（例如，在离线环境中应用更耗时的方法，在线场景中应用更快的方法，而且还细分为预处理/查询），以及不同的计算规模（例如，集中式计算与博弈论机制设计）。这些尺度通常是相互联系的（例如，分散计算可能与有限的信息相关），而不是方法上的等价（例如，在有限信息下的优化甚至出现在集中式场景中，从而产生在线算法的领域）。算法领域的一种通用方法是为不同尺度的场景开发单独的方法，即，第二阶段的主要总体目标是克服这一限制，研究用于复杂场景的多尺度、集成和交错方法，其中这些不同的尺度（信息和优化、时间、计算）不是单独处理的，而是以互换和并行的方式使用。这需要将单独的算法方法混合和统一为多尺度方法，在B1中进行，与分布式合同和算法设计的概念方法和技术密切互动，并与其他项目合作，用于复杂的结构化场景，以及在与应用项目的合作伙伴进行案例研究的背景下，将整体方法与其他项目相结合。最值得注意的是，这些涉及研究机器人平台和自动驾驶汽车，这两者都构成了相关的科学挑战，当组织一个机器人或车辆内的资源分配时，以及当协调多个平台时。除了我们的算法专业知识，我们在这两个应用领域都有相当丰富的经验，使这些非常有前途的目标。

项目成果

Cost-Oblivious Reallocation for Scheduling and Planning

用于调度和规划的成本无关的重新分配

• DOI: 10.1145/2755573.2755589
• 发表时间: 2015
• 期刊: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures
• 作者: M.E. Bender;M. Farach-Colton;S.P. Fekete;J. Fineman;S. Gilbert
• 通讯作者: S. Gilbert

A competitive strategy for distance-aware online shape allocation

距离感知在线形状分配的竞争策略

• DOI: 10.1016/j.tcs.2014.02.050
• 发表时间: 2014
• 期刊: Theor. Comput. Sci.
• 作者: S.P. Fekete;J.-M. Reinhardt;N. Schweer
• 通讯作者: N. Schweer

Conflict-Free Coloring of Graphs

图形的无冲突着色

• DOI: 10.1137/17m1146579
• 发表时间: 2018
• 期刊: SIAM J. Discret. Math.
• 作者: Z. Abel;V. Alvarez;E.D. Demaine;S. Fekete;A. Gour;A. Hesterberg;P. Keldenich;C. Scheffer
• 通讯作者: C. Scheffer

Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch

• DOI: 10.4230/lipics.socg.2018.29
• 发表时间: 2018-01
• 作者: E. Demaine;S. Fekete;Phillip Keldenich;H. Meijer;Christian Scheffer

Resource-efficient dynamic partial reconfiguration on FPGAs for space instruments

• DOI: 10.1109/ahs.2017.8046355
• 发表时间: 2017-07
• 期刊: 2017 NASA/ESA Conference on Adaptive Hardware and Systems (AHS)
• 作者: A. Dörflinger;B. Fiethe;H. Michalik;S. Fekete;Phillip Keldenich;Christian Scheffer