Combinatorial Search-Type Problems for Mobile Agents
移动代理的组合搜索类型问题
基本信息
- 批准号:RGPIN-2022-03811
- 负责人:
- 金额:$ 2.55万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2022
- 资助国家:加拿大
- 起止时间:2022-01-01 至 2023-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Mobile agent computing pertains to a number of combinatorial and/or geometric algorithmic problems in which a number of mobile agents (searchers/robots) need to execute a task, e.g. explore an unknown terrain, locate hidden items or achieve a special formation such as gathering in one spot. In alignment with fundamental questions of Theoretical Computer Science, the goal in such problems is to identify algorithmic boundaries subject to computation resources. In this research program I will expand further in this direction by investigating a number of combinatorial questions for search-type problems aiming to develop new algorithmic tools as well as new techniques for proving negative (impossibility) results. Search-type problems were first considered in the early 60's by mathematicians as a means to identify optimal strategies in so-called hide-and-seek games. The topic was reinvented by the computer science community a few decades later, where the same problems were examined under the lens of online algorithms, that is, optimization problems where part of the input is not known (e.g. the hidden item that is sought by mobile agents). Even more recently, the area was rejuvenated due to the consideration of multiple mobile agents along with their underlying communication model. To this date, a long series of results exist that establish both positive and negative results for a number of variations. The novelty of the current research program is the emphasis on the combinatorial structure of geometric mobile agent problems. More specifically, the program will consider research questions pertaining to non-deterministic models of computation, efficiency/resources trade-offs, and combinatorial attributes for the mobile agents. These directions revisit the search-type problems as combinatorial problems, where among others their tractability is determined not only by the (partial) information of the input but also by the computational capabilities of the mobile agents as processors. The significance of the above research directions pertains to the fundamental question in computing regarding the tractability of combinatorial problems. Progress in the area will give rise to new algorithmic techniques for solving hard optimization problems in a distributed environment, as well as to new mathematical tools for proving efficiency limitations in the underlying model of computation. Apart from the theoretical value of the program, understanding combinatorial search-type problems can have applications in emergency response, in search and rescue operations, in surveillance and in the understanding of animal/insect behavior.
移动代理计算涉及许多组合和/或几何算法问题,其中许多移动代理(搜索者/机器人)需要执行任务,例如探索未知地形,定位隐藏物品或实现特殊编队,例如聚集在一个地点。与理论计算机科学的基本问题一致,这些问题的目标是确定受计算资源约束的算法边界。在这个研究项目中,我将在这个方向上进一步扩展,通过研究一些搜索型问题的组合问题,旨在开发新的算法工具以及证明负(不可能)结果的新技术。在60年代早期,数学家们首先将搜索型问题视为在所谓的捉迷藏游戏中确定最佳策略的一种手段。几十年后,计算机科学界重新发明了这个话题,在在线算法的镜头下检查了同样的问题,即部分输入未知的优化问题(例如,移动代理寻找的隐藏项目)。甚至在最近,由于考虑了多个移动代理及其底层通信模型,该领域重新焕发了活力。到目前为止,已经有一长串的结果为一些变化确定了积极和消极的结果。当前研究方案的新颖之处在于强调几何移动智能体问题的组合结构。更具体地说,该计划将考虑有关非确定性计算模型的研究问题,效率/资源权衡,以及移动代理的组合属性。这些方向将搜索类型问题作为组合问题重新审视,其中它们的可追踪性不仅由输入的(部分)信息决定,还由作为处理器的移动代理的计算能力决定。上述研究方向的意义涉及到计算中关于组合问题可溯性的基本问题。该领域的进展将产生新的算法技术来解决分布式环境中的困难优化问题,以及新的数学工具来证明底层计算模型中的效率限制。除了该课程的理论价值外,理解组合搜索型问题还可以应用于应急响应、搜索和救援行动、监视以及对动物/昆虫行为的理解。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Georgiou, Konstantinos其他文献
Priority evacuation from a disk: The case of n = 1,2,3
优先从磁盘疏散:n≤=≤1,2,3 的情况
- DOI:
10.1016/j.tcs.2019.09.026 - 发表时间:
2020 - 期刊:
- 影响因子:1.1
- 作者:
Czyzowicz, Jurek;Georgiou, Konstantinos;Killick, Ryan;Kranakis, Evangelos;Krizanc, Danny;Narayanan, Lata;Opatrny, Jaroslav;Shende, Sunil - 通讯作者:
Shende, Sunil
Validity of a virtual reality endoscopic retrograde cholangiopancreatography simulator: can it distinguish experts from novices?
- DOI:
10.3389/fsurg.2023.1289197 - 发表时间:
2023 - 期刊:
- 影响因子:1.8
- 作者:
Georgiou, Konstantinos;Boyanov, Nikola;Antonakis, Pantelis;Thanasas, Dimitrios;Sandblom, Gabriel;Enochsson, Lars - 通讯作者:
Enochsson, Lars
Search on a Line by Byzantine Robots
拜占庭机器人在线搜索
- DOI:
10.1142/s0129054121500209 - 发表时间:
2021 - 期刊:
- 影响因子:0.8
- 作者:
Czyzowicz, Jurek;Georgiou, Konstantinos;Kranakis, Evangelos;Krizanc, Danny;Narayanan, Lata;Opatrny, Jaroslav;Shende, Sunil - 通讯作者:
Shende, Sunil
Gut microbiome: Linking together obesity, bariatric surgery and associated clinical outcomes under a single focus.
- DOI:
10.4291/wjgp.v13.i3.59 - 发表时间:
2022-05-22 - 期刊:
- 影响因子:0
- 作者:
Georgiou, Konstantinos;Belev, Nikolay A;Koutouratsas, Tilemachos;Katifelis, Hector;Gazouli, Maria - 通讯作者:
Gazouli, Maria
Exome sequencing reveals novel mutation targets in diffuse large B-cell lymphomas derived from Chinese patients
- DOI:
10.1182/blood-2013-12-546309 - 发表时间:
2014-10-16 - 期刊:
- 影响因子:20.3
- 作者:
de Miranda, Noel F. C. C.;Georgiou, Konstantinos;Pan-Hammarstrom, Qiang - 通讯作者:
Pan-Hammarstrom, Qiang
Georgiou, Konstantinos的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Georgiou, Konstantinos', 18)}}的其他基金
Efficiency Tradeoffs for Combinatorial Optimization Problems
组合优化问题的效率权衡
- 批准号:
RGPIN-2016-04312 - 财政年份:2021
- 资助金额:
$ 2.55万 - 项目类别:
Discovery Grants Program - Individual
Mathematics and geometry behind Additive Manufacturing for the multi-axis tool path
多轴刀具路径增材制造背后的数学和几何
- 批准号:
560726-2020 - 财政年份:2020
- 资助金额:
$ 2.55万 - 项目类别:
Alliance Grants
Efficiency Tradeoffs for Combinatorial Optimization Problems
组合优化问题的效率权衡
- 批准号:
RGPIN-2016-04312 - 财政年份:2020
- 资助金额:
$ 2.55万 - 项目类别:
Discovery Grants Program - Individual
Efficiency Tradeoffs for Combinatorial Optimization Problems
组合优化问题的效率权衡
- 批准号:
RGPIN-2016-04312 - 财政年份:2019
- 资助金额:
$ 2.55万 - 项目类别:
Discovery Grants Program - Individual
Efficiency Tradeoffs for Combinatorial Optimization Problems
组合优化问题的效率权衡
- 批准号:
RGPIN-2016-04312 - 财政年份:2018
- 资助金额:
$ 2.55万 - 项目类别:
Discovery Grants Program - Individual
Efficiency Tradeoffs for Combinatorial Optimization Problems
组合优化问题的效率权衡
- 批准号:
RGPIN-2016-04312 - 财政年份:2017
- 资助金额:
$ 2.55万 - 项目类别:
Discovery Grants Program - Individual
Efficiency Tradeoffs for Combinatorial Optimization Problems
组合优化问题的效率权衡
- 批准号:
RGPIN-2016-04312 - 财政年份:2016
- 资助金额:
$ 2.55万 - 项目类别:
Discovery Grants Program - Individual
相似海外基金
Synthesis and search for superconductivity of ternary hydrogen compounds with fluorite-type structure
萤石型结构三元氢化合物的合成及超导性研究
- 批准号:
23K03301 - 财政年份:2023
- 资助金额:
$ 2.55万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Elucidation of molecular genetic features and search for novel diagnostic markers in hyaline vascular type Castleman disease
阐明透明血管型 Castleman 病的分子遗传学特征并寻找新的诊断标志物
- 批准号:
22K15405 - 财政年份:2022
- 资助金额:
$ 2.55万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
Development of monolithic type pixel detector to search for axion like particle
开发单片式像素探测器来寻找轴子类粒子
- 批准号:
20K04004 - 财政年份:2020
- 资助金额:
$ 2.55万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Composition- and structure-controls and search for magnetic properties of eutectoid-decomposition-type metal/oxide nanocomposites
共析分解型金属/氧化物纳米复合材料的成分和结构控制以及磁性能研究
- 批准号:
20K05079 - 财政年份:2020
- 资助金额:
$ 2.55万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Search for "green gap free" semiconductor based on spinel-type chalcogenides
寻找基于尖晶石型硫属化物的“绿色无间隙”半导体
- 批准号:
20K15363 - 财政年份:2020
- 资助金额:
$ 2.55万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
A search for novel efficient p-type nitride materials
寻找新型高效p型氮化物材料
- 批准号:
1905186 - 财政年份:2019
- 资助金额:
$ 2.55万 - 项目类别:
Standard Grant
The search study of the molecular mechanisms about the autonomous myofiber type determination by myogenic stem cells.
肌源干细胞自主决定肌纤维类型的分子机制探索研究。
- 批准号:
19K15959 - 财政年份:2019
- 资助金额:
$ 2.55万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
Collaborative Research: A search for novel efficient p-type nitride materials
合作研究:寻找新型高效p型氮化物材料
- 批准号:
1904861 - 财政年份:2019
- 资助金额:
$ 2.55万 - 项目类别:
Standard Grant
Elucidation of the role of denitrosylation enzyme in type 2 diabetes pancreatic beta cell dysfunction and search for new therapeutic agents
阐明脱亚硝基化酶在2型糖尿病胰腺β细胞功能障碍中的作用并寻找新的治疗药物
- 批准号:
18K06970 - 财政年份:2018
- 资助金额:
$ 2.55万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Search for new therapeutic target against cancer stem cells using intestinal-/gastric type gastric cancer organoid
利用肠/胃型胃癌类器官寻找癌症干细胞的新治疗靶点
- 批准号:
18K07017 - 财政年份:2018
- 资助金额:
$ 2.55万 - 项目类别:
Grant-in-Aid for Scientific Research (C)