Understanding the Role of Exploration in Search and Planning

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

• 批准号: RGPIN-2015-04466
• 负责人: Müller, Martin
• 金额: $ 3.64万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=660408
• 关键词: 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。建议研究计划的目标********我的主要目标是更好地理解在启发式搜索中使用探索的问题。探索技术是越来越多的搜索算法的重要组成部分。蒙特卡罗采样方法在包括博弈和概率规划在内的应用中非常成功。然而，尽管取得了这些成功，关于勘探方法何时、如何以及为什么有效的许多重要问题仍然存在。******科学方法总结*******为了研究启发式搜索中的探索方法，我计划继续研究具有重大研究挑战的具体应用，如围棋，领域独立规划和运动规划。与我的学生和同事一起，我想继续构建完整的高性能系统，并在标准基准和比赛中对它们进行测试。*******这项工作将需要从多个角度进行攻击，从对成功部署的系统的深入分析到综合不同基于探索的算法的经验，并导致控制探索的通用框架和自适应模型。对基于探索的方法的更深入理解可能会导致算法的改进甚至是全新的算法。它也会导致计算机程序的显著改进，它可以为困难的启发式搜索问题找到更好的解决方案，可以扩展到更大的问题，并且足够快，可以实时使用