Effective use of Knowledge in Search

在搜索中有效利用知识

• 批准号: RGPIN-2019-05529
• 负责人: Sturtevant, Nathan
• 金额: $ 3.5万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=715593
• 关键词: Effective; use; Knowledge; Search

One expected aspect of any Artificial Intelligent (AI) agent is the ability to solve problems. AI techniques are used to solve a wide variety of problems such as path planning in road networks, for virtual agents, for package delivery in a city, or for individuals or teams of robots moving through a shared space. The problem solving agents used to solve these problems in heuristic search combine exhaustive search techniques with knowledge to solve problems. The better the knowledge, the less search is needed; with less knowledge more search is needed. Thus, knowledge plays an important part in search. The knowledge used for these agents is typically pre-computed in the form of heuristics or constraints. Heuristics guide the search towards the goal by estimating the distance to the goal from a given state, while constraints guide the search away from states that cannot reach the goal. Heuristics and constraints are typically built through an exact computational procedure, so that precise theoretical properties can be guaranteed. For instance, heuristics are usually required to be admissible, meaning they do not overestimate the cost to reach the goal. Although machine learning techniques have had a broad impact on other fields, they have had less of an impact on single-agent heuristic search. One reason for this is that machine learning cannot guarantee the same properties on heuristics (or constraints) that are guaranteed through exact computational procedures. Machine learning approaches may, for instance, produce inadmissible heuristics. However, machine learning has been able to learn very strong heuristics in games such as Go, although nobody currently knows how accurate these heuristics actually are. Given the recent advances in machine learning and success in related domains, along with the lack of use in single-agent search, it is the right time to research the application of machine learning to heuristic search. This research will grow out of the current research by the PI which has produced large data sets that are applicable for learning. It will involve numerous approaches for building heuristics and constraints, as well as building new algorithms that are designed to work with the approximate nature of data from machine learning. This work will allow heuristic techniques to be scaled to larger problems, while maintaining desired theoretical properties on solution quality, such as bounded suboptimality. More broadly, the work will have large impact on single-agent search, bringing new techniques to the field that have the potential to significantly change the approaches currently used.

任何人工智能（AI）代理的一个预期方面是解决问题的能力。人工智能技术被用于解决各种各样的问题，例如道路网络中的路径规划，虚拟代理，城市中的包裹递送，或通过共享空间移动的个人或机器人团队。用于在启发式搜索中解决这些问题的问题解决代理联合收割机将穷举搜索技术与知识相结合来解决问题。知识越好，需要的搜索就越少;知识越少，需要的搜索就越多。因此，知识在搜索中起着重要的作用。用于这些代理的知识通常是以逻辑或约束的形式预先计算的。启发式通过估计从给定状态到目标的距离来引导搜索朝向目标，而约束则引导搜索远离无法到达目标的状态。启发式和约束通常通过精确的计算过程来建立，从而可以保证精确的理论性质。例如，假设通常被要求是可接受的，这意味着它们不会高估达到目标的成本。 虽然机器学习技术对其他领域产生了广泛的影响，但它们对单智能体启发式搜索的影响较小。其中一个原因是，机器学习无法保证通过精确计算过程保证的相同的属性。例如，机器学习方法可能会产生不可接受的错误。然而，机器学习已经能够在像围棋这样的游戏中学习非常强大的算法，尽管目前没有人知道这些算法的准确性。 鉴于机器学习的最新进展和相关领域的成功，沿着在单智能体搜索中的缺乏使用，现在是研究机器学习在启发式搜索中的应用的合适时机。这项研究将从PI目前的研究中发展出来，PI已经产生了适用于学习的大型数据集。它将涉及许多方法来构建算法和约束，以及构建新的算法，这些算法旨在处理机器学习数据的近似性质。这项工作将允许启发式技术扩展到更大的问题，同时保持所需的理论性能的解决方案的质量，如有界次优。更广泛地说，这项工作将对单智能体搜索产生重大影响，为该领域带来新技术，有可能显著改变目前使用的方法。