.png){kind=icon}
返回
Physical search problems with probabilistic knowledge
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2012.12.003.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper considers the problem of an agent or a team of agents searching for a resource or tangible good in a physical environment, where the resource or good may possibly be obtained at one of several locations. The cost of acquiring the resource or good at a given location is uncertain (a priori), and the agents can observe the true cost only when physically arriving at this location. Sample applications include agents in exploration and patrol missions (e.g., an agent seeking to find the best location to deploy sensing equipment along its path). The uniqueness of these settings is in that the cost of observing a new location is determined by distance from the current one, impacting the consideration for the optimal search order. Although this model captures many real world scenarios, it has not been investigated so far. We analyze three variants of the problem, differing in their objective: minimizing the total expected cost, maximizing the success probability given an initial budget, and minimizing the budget necessary to obtain a given success probability. For each variant, we first introduce and analyze the problem with a single agent, either providing a polynomial solution to the problem or proving it is NP-complete. We also introduce a fully polynomial time approximation scheme algorithm for the minimum budget variant. In the multi-agent case, we analyze two models for managing resources, shared and private budget models. We present polynomial algorithms that work for any fixed number of agents, in the shared or private budget model. For non-communicating agents in the private budget model, we present a polynomial algorithm that is suitable for any number of agents. We also analyze the difference between homogeneous and heterogeneous agents, both with respect to their allotted resources and with respect to their capabilities. Finally, we define our problem in an environment with self-interested agents. We show how to find a Nash equilibrium in polynomial time, and prove that the bound on the performance of our algorithms, with respect to the social welfare, is tight. (C) 2013 Elsevier B.V. All rights reserved.
Keyword:
Graph search
Economic search
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
13.9
论文数:
6.1K
被引数:
1.9W
机构
引用论文
.png){kind=icon}
Biomedical knowledge graph-optimized prompt generation for large language models生物医学知识图谱优化的大语言模型提示生成
OAAI
OAAI分享收藏
查看更多内容