Spelling suggestions: "subject:"realtime search"" "subject:"mealtime search""
1 |
Speeding Up the Convergence of Online Heuristic Search and Scaling Up Offline Heuristic SearchFurcy, David Andre 25 November 2004 (has links)
The most popular methods for solving the shortest-path problem in
Artificial Intelligence are heuristic search algorithms. The main
contributions of this research are new heuristic search algorithms
that are either faster or scale up to larger problems than existing
algorithms. Our contributions apply to both online and offline tasks.
For online tasks, existing real-time heuristic search algorithms learn
better informed heuristic values and in some cases eventually converge
to a shortest path by repeatedly executing the action leading to a
successor state with a minimum cost-to-goal estimate. In contrast, we
claim that real-time heuristic search converges faster to a shortest
path when it always selects an action leading to a state with a
minimum f-value, where the f-value of a state is an estimate of the
cost of a shortest path from start to goal via the state, just like in
the offline A* search algorithm. We support this claim by implementing
this new non-trivial action-selection rule in FALCONS and by showing
empirically that FALCONS significantly reduces the number of actions
to convergence of a state-of-the-art real-time search algorithm.
For offline tasks, we improve on two existing ways of scaling up
best-first search to larger problems. First, it is known that the WA*
algorithm (a greedy variant of A*) solves larger problems when it is
either diversified (i.e., when it performs expansions in parallel) or
committed (i.e., when it chooses the state to expand next among a
fixed-size subset of the set of generated but unexpanded states). We
claim that WA* solves even larger problems when it is enhanced with
both diversity and commitment. We support this claim with our MSC-KWA*
algorithm. Second, it is known that breadth-first search solves
larger problems when it prunes unpromising states, resulting in the
beam search algorithm. We claim that beam search quickly solves even
larger problems when it is enhanced with backtracking based on limited
discrepancy search. We support this claim with our BULB algorithm. We
show that both MSC-KWA* and BULB scale up to larger problems than
several state-of-the-art offline search algorithms in three standard
benchmark domains. Finally, we present an anytime variant of BULB and
apply it to the multiple sequence alignment problem in biology.
|
2 |
Single And Multi Agent Real-time Path Search In Dynamic And Partially Observable EnvironmentsUndeger, Cagatay 01 January 2007 (has links) (PDF)
In this thesis, we address the problem of real-time path search in partially observable grid worlds, and propose two single agent and one multi-agent search algorithm.
The first algorithm, Real-Time Edge Follow (RTEF), is capable of detecting the closed directions around the agent by analyzing the nearby obstacles, thus avoiding dead-ends in order to reach a static target more effectively. We compared RTEF with a well-known algorithm, Real-Time A* (RTA*) proposed by Korf, and observed significant improvement.
The second algorithm, Real-Time Moving Target Evaluation Search (MTES), is also able to detect the closed directions similar to RTEF, but in addition, determines the estimated best direction that leads to a static or moving target from a shorter
path. Employing this new algorithm, we obtain an impressive improvement over RTEF with respect to path length, but at the cost of extra computation. We compared our algorithms with Moving Target Search (MTS) developed by Ishida and the off-line path planning algorithm A*, and observed that MTES performs significanlty better than MTS, and offers solutions very close to optimal ones produced by A*.
Finally, we present Multi-Agent Real-Time Pursuit (MAPS) for multiple predators to capture a moving prey cooperatively. MAPS introduces two new coordination strategies namely Blocking Escape Directions (BES) and Using Alternative Proposals (UAL), which help the predators waylay the possible escape directions of the prey in coordination. We compared our coordination strategies with the uncoordinated one,
and observed an impressive reduction in the number of moves to catch the prey.
|
3 |
Multiagent Moving Target Search In Fully Visible Grid Environments With No Speed DifferenceErogul, Can 01 December 2006 (has links) (PDF)
In this thesis, a new real-time multi-agent moving target pursuit algorithm and a moving target algorithm are developed and implemented. The environment is a grid world, in which a coordinated team of agents cooperatively blocks the possible escape routes of an intelligent target in real-time.
Most of the moving target search algorithms presume that the agents are faster than the targets, so the pursuit is sure to end in favor of the agents. In this work, we relax this assumption and assume that all the moving objects have the same speed. This means that the agents must find a new approach for success in the pursuit, other than just chasing the targets. When the search agents and the moving targets are moving with the same speed, we need more than one search agent which can coordinate with the other agents to capture the target.
Agents are allowed to communicate with each other.
We propose a multi-agent search algorithm for this problem. To our best knowledge, there is no alternative algorithm designed based on these assumptions. The proposed algorithm is compared to the modified versions of its counterparts (A*, MTS and its derivatives) experimentally.
|
Page generated in 0.0526 seconds