Understanding the Role of Exploration in Search and Planning

了解探索在搜索和规划中的作用

• 批准号: RGPIN-2015-04466
• 负责人: Müller, Martin
• 金额: $ 3.64万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=690214
• 关键词: Understanding; Role; Exploration; Search; Planning

1. Background********As a researcher in Computing Science, my goal is to make progress towards solving ever more complex real-world problems. Intelligent automated decision-making requires modelling an application domain, and processing a potentially huge space of possible future alternatives, sometimes offline but more and more often in a real-time setting. With my research group I study efficient search algorithms for solving hard problems. Powerful solution techniques include abstraction, divide and conquer strategies, and many types of systematic and heuristic search. While my research agenda involves work on many aspects of these approaches, the current proposal focuses on the topic of exploration in heuristic search, which has emerged as the common theme that drives much of my recent work.******For a computer program, exploration is a way of getting experience about its (simulated or real) environment. Such exploration can be used to correct errors, gaps and uncertainty in a model of the world. Examples include board games, where exploration of possible future move sequences can find winning strategies, and automated planning, where exploration can be used to discover promising action sequences.******2. Objectives of the Proposed Research Program********My main objective is to better understand the issues of using exploration in heuristic search. Exploration techniques are vital ingredients of a large and growing number of search algorithms. Monte Carlo sampling methods have been extremely successful in applications including game-playing and probabilistic planning. Yet despite all these successes, many important questions remain about when, how, and why exploration methods work.******3. Summary of Scientific Approach*******To study exploration methods in heuristic search, I plan to continue working on concrete applications which pose significant research challenges, such as the game of Go, domain-independent planning and motion planning. With my students and colleagues, I want to continue building complete high performance systems, and test them on standard benchmarks as well as in competitions.*******This work will require many angles of attack, from in-depth analysis of successful deployed systems to synthesizing the experience from different exploration-based algorithms, and leading towards generic frameworks and adaptive models for controlling exploration. A deeper understanding of exploration-based methods will likely lead to algorithmic improvements or even brand-new algorithms. It should also lead to significantly improved computer programs, which can find better solutions to difficult heuristic search problems, can scale to larger problems, and are fast enough for real-time use.**

1.背景 ** 作为一名计算机科学研究人员，我的目标是朝着解决越来越复杂的现实问题取得进展。智能自动化决策需要对应用程序域进行建模，并处理潜在的巨大空间，有时离线，但越来越多地在实时设置中。我和我的研究小组一起研究解决难题的高效搜索算法。强大的解决方案技术包括抽象，分而治之的策略，以及许多类型的系统和启发式搜索。虽然我的研究议程涉及这些方法的许多方面，但目前的建议侧重于探索启发式搜索的主题，这已经成为推动我最近大部分工作的共同主题。对于一个计算机程序来说，探索是一种获得（模拟的或真实的）环境经验的方式。这种探索可以用来纠正世界模型中的错误、差距和不确定性。例子包括棋盘游戏，其中探索可能的未来移动序列可以找到获胜策略，以及自动规划，其中探索可以用来发现有希望的动作序列。2.建议研究计划的目标 ** 我的主要目标是更好地理解在启发式搜索中使用探索的问题。探索技术是大量且不断增长的搜索算法的重要组成部分。蒙特卡罗抽样方法在游戏和概率规划等应用中非常成功。然而，尽管取得了所有这些成功，许多重要的问题仍然是关于何时，如何以及为什么勘探方法有效。3.科学方法摘要 * 为了研究启发式搜索中的探索方法，我计划继续致力于提出重大研究挑战的具体应用，例如围棋游戏、独立于域的规划和运动规划。我希望与我的学生和同事一起继续构建完整的高性能系统，并在标准基准测试和竞赛中对其进行测试。这项工作将需要从多个角度出发，从深入分析成功部署的系统，到综合不同探索算法的经验，并导致控制探索的通用框架和自适应模型。对基于探索的方法的更深入理解将可能导致算法的改进甚至全新的算法。它还应该导致显着改进的计算机程序，可以找到更好的解决困难的启发式搜索问题，可以扩展到更大的问题，并且速度足够快，可以实时使用。