# AI研究生题目

1. (25 pts.) Consider state-space search using A∗ and an ε-admissible heuristic function h(n). That is, ∀n, h(n) ≤ h∗(n) + ε where h∗ is the perfect heuristic function and ε is a fixed positive constant.
(a) (20pts.) Prove that in such a case, A∗ is ε-admissible. That is, A∗ is guaranteed to return a path to a goal node m such that g(m) ≤ h∗(s) + ε.
(b) (5 pts.) Comment on the potential advantages of an ε-admissible search algorithm in problem domains in which near-optimal solutions are abundant.
2. (25 points) Consider a swarm of autonomous robotic vehicles which have to find their way to a goal location in an environment for which no roadmap is available. Each robot is capable of reading road signs etc. and learn the distance to closest reachable cities from the city where it is located. The robots, in general, do not have a way of obtaining the distance to the goal location from their current locations although in some instances they may be able to do so (e.g., through intelligence information provided by local informants). Each robot, if it is the first one to visit a particular city, leaves behind a sign which can be read by other robots that arrive there. Suppose this sign contains the h value (the estimated distance to the goal city). Each robot is able to update the sign based on information that it has gathered. Formulate a strategy that each robot can use independently (without any direct communication) to maximize the chances of the swarm of robots in achieving their objective. Some desirable characteristics of the solution include the following:
• In a finite graph with positive arc costs, in which there exists a path from every node to a goal node, if the h values are initialized with nonnegative admissible estimates, the strategy is complete: i.e., eventually, some member(s) of the swarm will reach a goal.
• Over repeated trials mounted by swarm(s) of robots, the heuristic estimates con- verge to their true values (unless no new arcs are introduced into the graph).