赵才荣 同济大学，电子与信息工程学院，智信馆410室

Presentation on theme: "赵才荣 同济大学，电子与信息工程学院，智信馆410室"— Presentation transcript:

1 赵才荣 E-mail：zhaocairong@tongji.edu.cn 同济大学，电子与信息工程学院，智信馆410室
《人工智能原理》课程 第三章 通过搜索进行问题求解 有信息搜索 赵才荣 同济大学，电子与信息工程学院，智信馆410室 理性的Agent是人工智能方法的核心 通过对Agent从感知外部环境，到实施行动，并最后对外部环境施加影响的全过程，把AI中相互分离的主要领域，如问题求解，知识与推理，合乎逻辑 的行动，不确定知识与推理，学习以及通信、感知与行动等统一在智能Agent这一框架下，形成了一个相互联系的整体。

2 Review: Uninformed search strategies
Problem formulation Breadth-first Uniform-cost Depth-first Depth-limited Iterative deepening Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

3 Outline Best-first search Greedy best-first search A* search
Heuristics Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

4 Best-first search Idea: use an evaluation function f(n) for each node
estimate of "desirability" Expand most desirable unexpanded node Implementation: Order the nodes in fringe in decreasing order of desirability Special cases: greedy best-first search A* search Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

5 Best-first search 基本思想 启发式函数（heuristic function ）
创建一个评价函数 f(n) 度量下一步所有可能的步骤 选择一个最好的步骤进行扩展 启发式函数（heuristic function ） h(n) = 从节点n到目标节点的估计耗散值 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

6 Example 上海市精品课程 人工智能原理 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。
智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

7 Greedy best-first search
Evaluation function f(n) = h(n) (heuristic) e.g., hSLD(n) = straight-line distance from n to Bucharest Greedy best-first search expands the node that appears to be closest to goal Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

8 Greedy best-first search example
Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

9 Greedy best-first search example
Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

10 Greedy best-first search example
Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

11 Greedy best-first search example
Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

12 Greedy best-first search example
Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

13 Properties of greedy best-first search
Complete? No – can get stuck in loops, e.g., Iasi  Neamt  Iasi  Neamt  Time? O(bm), but a good heuristic can give dramatic improvement Space? O(bm) -- keeps all nodes in memory Optimal? No Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

14 A* search Idea: avoid expanding paths that are expensive
Evaluation function f(n) = g(n) + h(n) g(n) = cost so far to reach n h(n) = estimated cost from n to goal f(n) = estimated total cost of path through n to goal Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

15 A* search example 上海市精品课程 人工智能原理 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。
智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

16 A* search example 上海市精品课程 人工智能原理 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。
智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

17 A* search example 上海市精品课程 人工智能原理 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。
智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

18 A* search example 上海市精品课程 人工智能原理 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。
智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

19 A* search example 上海市精品课程 人工智能原理 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。
智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

20 A* search example 上海市精品课程 人工智能原理 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。
智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

21 Admissible heuristics
A heuristic h(n) is admissible if for every node n, h(n) ≤ h*(n), where h*(n) is the true cost to reach the goal state from n. An admissible heuristic never overestimates the cost to reach the goal, i.e., it is optimistic Example: hSLD(n) (never overestimates the actual road distance) Theorem: If h(n) is admissible, A* using TREE-SEARCH is optimal Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

22 Optimality of A* (proof1)
Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G. f(G2) = g(G2) since h(G2) = 0 f(G) = g(G) since h(G) = 0 g(G2) > g(G) since G2 is suboptimal f(G2) > f(G) from above Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

23 Optimality of A* (proof2)
Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G. f(G2) > f(G) from above h(n) ≤ h^*(n) since h is admissible g(n) + h(n) ≤ g(n) + h*(n) f(n) ≤ f(G) Hence f(G2) > f(n), and A* will never select G2 for expansion Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

24 Consistent Heuristics
A heuristic is consistent if for every node n, every successor n' of n generated by any action a, then h(n) ≤ c(n,a,n') + h(n') If h is consistent, we have f(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') ≥ g(n) + h(n) i.e., f(n) is non-decreasing along any path. Theorem: If h(n) is consistent, A* using GRAPH-SEARCH is optimal Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

25 Optimality of A* A* expands nodes in order of increasing f value
Gradually adds "f-contours" of nodes Contour i has all nodes with f=fi, where fi < fi+1 A*扩展所有 f(n) < C*的节点 A*扩展部分f(n)=C*的节点 A*不扩展f(n)>C*的节点 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

26 Properties of A* Complete? Yes (unless there are infinitely many nodes with f ≤ f(G) ) Time? Exponential Space? Keeps all nodes in memory Optimal? Yes Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

27 Heuristic Function Admissible heuristics
E.g., for the 8-puzzle: h1(n) = number of misplaced tiles h2(n) = total Manhattan distance (i.e., no. of squares from desired location of each tile) h1(S) = ? h2(S) = ? Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

28 Admissible heuristics
E.g., for the 8-puzzle: h1(n) = number of misplaced tiles h2(n) = total Manhattan distance (i.e., no. of squares from desired location of each tile) h1(S) = ? 8 h2(S) = ? = 18 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

29 A*算法应用举例 例八数码难题。 S0 f=6 g*=1h*=3 f=6 f=6 g*=2 h*=2 f=6 f=4
S0 h*=4 f=4 1 4 f= g*=1h*= f= f=6 f=4 2 3 g*=2 h*= f=6 f=4 例八数码难题。 f(n)=d(n)+P(n) d(n) 深度 P(n)与目标距离 显然满足 P(n)≤ h*(n) 即f*=g*+h* 8 4 g*=3 h*=1 f=4 6 5 g*=4 h*=0 f=4 f=6 Sg 八数码难题h(n)=P(n)的搜索树 上海市精品课程 人工智能原理 29

30 A*算法应用举例 例八数码难题。 S0 f=4 g*=1h*=3 f=5 f=5 f=5 f=6 g*=2 h*=2 f=6 f=4
S0 h*=3 f=3 1 4 f= g*=1h*= f= f=5 f=4 8 3 6 5 f= f=6 2 3 g*=2 h*= f=6 f=4 例八数码难题。 f(n)=d(n)+P(n) d(n) 深度 P(n)不在位棋子数 显然满足 P(n)≤ h*(n) 即f*=g*+h* 8 4 g*=3 h*=1 f=4 6 5 g*=4 h*=0 f=4 f=6 Sg 八数码难题h(n)=P(n)的搜索树 上海市精品课程 人工智能原理 30

31 Dominance If h2(n) ≥ h1(n) for all n (both admissible)
then h2 dominates h1 ===》 h2 is better for search Typical search costs (average number of nodes expanded): d=12 IDS = 3,644,035 nodes (ITERATIVE-DEEPENING-SEARCH) A*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

32 上海市精品课程 人工智能原理 Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。
智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

33 Heuristics from Relaxed Problems
A problem with fewer restrictions on the actions is called a relaxed problem The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h1(n) gives the shortest solution If the rules are relaxed so that a tile can move to any adjacent square, then h2(n) gives the shortest solution Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

34 Heuristics from subproblems
Let h3(n) be the cost of getting a subset of tiles (say, 1,2,3,4) into their correct positions Can precompute and save the exact solution cost for every possible subproblem instance – pattern database Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

35 Review : search strategies
Uninformed: Use only information available in the problem formulation Breadth-first Uniform-cost Depth-first Depth-limited Iterative deepening Informed: Use heuristics to guide the search Best first: Greedy search – queue first nodes that maximize heuristic “desirability” based on estimated path cost from current node to goal; A* search – queue first nodes that maximize sum of path cost so far and estimated path cost to goal. Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

36 Exercise: Search Algorithms
The following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h. Which node (use the node’s letter) will be expanded next by each of the following search algorithms? (a) Depth-first search (b) Breadth-first search (c) Uniform-cost search (d) Greedy search (e) A* search 5 D A C 4 19 6 3 h=15 B F G E h=8 h=12 h=10 h=18 H Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

37 Depth-first search Node queue: initialization # state depth path cost parent # 1 A Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

38 Depth-first search Node queue: add successors to queue front; empty queue from top # state depth path cost parent # 2 B 3 C 4 D 1 A Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

39 Depth-first search Node queue: add successors to queue front; empty queue from top # state depth path cost parent # 5 E F G H B C D A Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

40 Depth-first search Node queue: add successors to queue front; empty queue from top # state depth path cost parent # 5 E 6 F 7 G 8 H 2 B 3 C 4 D 1 A Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

41 Exercise: Search Algorithms
The following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h. Which node (use the node’s letter) will be expanded next by each of the following search algorithms? (a) Depth-first search (b) Breadth-first search (c) Uniform-cost search (d) Greedy search (e) A* search 5 D A C 4 19 6 3 h=15 B F G E h=8 h=12 h=10 h=18 H Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

42 Breadth-first search Node queue: initialization
# state depth path cost parent # 1 A 上海市精品课程 人工智能原理

43 Breadth-first search Node queue: add successors to queue end; empty queue from top # state depth path cost parent # 1 A 2 B 3 C 4 D 上海市精品课程 人工智能原理

44 Breadth-first search Node queue: add successors to queue end; empty queue from top # state depth path cost parent # 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 上海市精品课程 人工智能原理

45 Breadth-first search Node queue: add successors to queue end; empty queue from top # state depth path cost parent # 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 上海市精品课程 人工智能原理

46 Exercise: Search Algorithms
The following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h. Which node (use the node’s letter) will be expanded next by each of the following search algorithms? (a) Depth-first search (b) Breadth-first search (c) Uniform-cost search (d) Greedy search (e) A* search 5 D A C 4 19 6 3 h=15 B F G E h=8 h=12 h=10 h=18 H Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

47 Uniform-cost search Node queue: initialization
# state depth path cost parent # 1 A 上海市精品课程 人工智能原理

48 Uniform-cost search Node queue: add successors to queue so that entire queue is sorted by path cost so far; empty queue from top # state depth path cost parent # 1 A 2 B 3 D 4 C 上海市精品课程 人工智能原理

49 Uniform-cost search Node queue: add successors to queue so that entire queue is sorted by path cost so far; empty queue from top # state depth path cost parent # 1 A 2 B 3 D 5 E 6 F 7 G 8 H 4 C 上海市精品课程 人工智能原理

50 Uniform-cost search Node queue: add successors to queue so that entire queue is sorted by path cost so far; empty queue from top # state depth path cost parent # 1 A 2 B 3 D 5 E 6 F 7 G 8 H 4 C 上海市精品课程 人工智能原理

51 Exercise: Search Algorithms
The following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h. Which node (use the node’s letter) will be expanded next by each of the following search algorithms? (a) Depth-first search (b) Breadth-first search (c) Uniform-cost search (d) Greedy search (e) A* search 5 D A C 4 19 6 3 h=15 B F G E h=8 h=12 h=10 h=18 H Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

52 Greedy search Node queue: initialization
# state depth path cost total parent # cost to goal cost 1 A 上海市精品课程 人工智能原理

53 Greedy search Node queue: Add successors to queue, sorted by cost to goal. # state depth path cost total parent # cost to goal cost 1 A 2 B 3 D 4 C Sort key 上海市精品课程 人工智能原理

54 Greedy search Node queue: Add successors to queue, sorted by cost to goal. # state depth path cost total parent # cost to goal cost 1 A 2 B 5 G 7 E 6 H 8 F 3 D 4 C 上海市精品课程 人工智能原理

55 Greedy search Node queue: Add successors to queue, sorted by cost to goal. # state depth path cost total parent # cost to goal cost 1 A 2 B 5 G 7 E 6 H 8 F 3 D 4 C 上海市精品课程 人工智能原理

56 Exercise: Search Algorithms
The following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h. Which node (use the node’s letter) will be expanded next by each of the following search algorithms? (a) Depth-first search (b) Breadth-first search (c) Uniform-cost search (d) Greedy search (e) A* search 5 D A C 4 19 6 3 h=15 B F G E h=8 h=12 h=10 h=18 H Agent 通过传感器感知环境并通过执行器对所处环境产生影响的实体。 智能体，顾名思义：就是具有智能的实体，英文名是Agent。 智能体是 人工智能 领域中一个很重要的概念。任何独立的能够思想并可以同环境交互的实体都可以抽象为智能体。 例子： 人类智能体（简单分析一下智能体的工作机理）；机器人智能体。 一般地，一个Agent在指定时间是否为理性取决于以下四条： 1）定义了成功程度的性能度量； 2）Agent迄今所感知到的全体， 即感知序列（percept sequence）； 3）Agent对环境的了解； 4）Agent所能实施的行动。 上海市精品课程 人工智能原理

57 A* search Node queue: initialization
# state depth path cost total parent # cost to goal cost 1 A 上海市精品课程 人工智能原理

58 A* search Node queue: Add successors to queue, sorted by total cost.
# state depth path cost total parent # cost to goal cost 1 A 2 B 3 D 4 C Sort key 上海市精品课程 人工智能原理

59 A* search Node queue: Add successors to queue front, sorted by total cost. # state depth path cost total parent # cost to goal cost 1 A 2 B 5 G 6 E 7 H 3 D 8 F 4 C 上海市精品课程 人工智能原理

60 A* search Node queue: Add successors to queue front, sorted by total cost. # state depth path cost total parent # cost to goal cost 1 A 2 B 5 G 6 E 7 H 3 D 8 F 4 C 上海市精品课程 人工智能原理

61 实验一 求解Hanoi塔问题（不能用迭代方法求解），A星搜索求解八数码问题 要求：1，动态演示求解过程 2，PPT展示设计思想
和实验效果（10分钟） 3，提交一份实验报告 上海市精品课程 人工智能原理

62 Thank you