We give an outline of recent results and propose several open problems in linear search by searchers, modelled as autonomous mobile agents. The trajectories of the searchers are continuous and the search domain is the infinite real line or generalizations thereof (e.g., star graph). The design and analysis of the search algorithms proposed takes into account the impact of the knowledge the searchers have about in order to obtain an optimal competitive ratio. For group-search involving multiple searchers the approach emphasizes agent co-operation and distributed algorithm design principles. The overall approach considered is based on understanding the impact of the knowledge the searchers have about the system settings on the competitive ratio (which is the supremum of the ratio between the time the searcher travels and the time he would have taken if he had known the location of the target) of the linear group-search algorithms.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Invited Paper: A Survey of the Impact of Knowledge on the Competitive Ratio in Linear Search

  • Evangelos Kranakis

摘要

We give an outline of recent results and propose several open problems in linear search by searchers, modelled as autonomous mobile agents. The trajectories of the searchers are continuous and the search domain is the infinite real line or generalizations thereof (e.g., star graph). The design and analysis of the search algorithms proposed takes into account the impact of the knowledge the searchers have about in order to obtain an optimal competitive ratio. For group-search involving multiple searchers the approach emphasizes agent co-operation and distributed algorithm design principles. The overall approach considered is based on understanding the impact of the knowledge the searchers have about the system settings on the competitive ratio (which is the supremum of the ratio between the time the searcher travels and the time he would have taken if he had known the location of the target) of the linear group-search algorithms.