We study the setting in which a mobile agent must locate a hidden target in a bounded or unbounded environment, with no information about the hider's position. In particular, we consider online search, in which the performance of the search strategy is evaluated by its worst case competitive ratio. We introduce a multi-criteria search problem in which the searcher has a budget on its allotted search time, and the objective is to design strategies that are competitively efficient, respect the budget, and maximize the total searched ground. We give analytically optimal strategies for the line and the star environments, and efficient heuristics for general networks.
翻译：我们研究移动剂必须在封闭或未封闭的环境中定位隐藏目标的环境,而没有隐藏者位置的信息。我们特别考虑在线搜索,在网上搜索中,搜索战略的绩效以最差的个案竞争比率来评估。我们引入了多标准搜索问题,搜索者在其分配的搜索时间上有预算,目的是设计具有竞争力、尊重预算和最大限度地扩大搜索地面的战略。我们为线路和恒星环境提供了分析上的最佳策略,为一般网络提供了高效的套用。
相关内容
微信扫码咨询专知VIP会员