Anytime versus Real-Time Heuristic Search for On-Line Planning

Running head: Heuristic Search
Anytime versus Real-Time Heuristic Search for On-Line Planning
Name of Student
Name of the University
Author notes

1HEURISTIC SEARCH
Table of Contents
Introduction................................................................................................................................2
Discussion and findings.............................................................................................................2
Conclusion..................................................................................................................................5
Reference....................................................................................................................................7

2HEURISTIC SEARCH
Cserna, B., Bogochow, M., Chambers, S., Tremblay, M., Katt, S. and Ruml,
W., 2016, June. Anytime versus real-time heuristic search for on-line
planning. In Ninth annual symposium on combinatorial search.
Introduction
In order to get idea about the most suitable measure for designing and collecting
effective feedback in the early stage of the design process, heuristic search is the best possible
way. The concept of Heuristic search can be explained by one efficient searching strategy
that tries to optimize the issue or problem by improving the particular solution iteratively
depending on the given cost measure or a heuristic function [1]. However, the main concept of
Heuristic Search falls into two categories: anytime and real time. The Real-time heuristic
search approach allow to have fine-grained control regarding how much planning is
necessary between the plan executions. Meanwhile, the anytime heuristic search allows to
have a flexible trade-off between the solution quality and the search time[2]. This report is
going to critically review the above mention article and explain the additional facts related to
both the Heuristic Search approaches.
Discussion and findings
As mentioned in the article several AI systems, for example robots, need to be plan
under the time constraints. Moreover, the anytime search method is the most popular search
approach in this case as the algorithm prepared here helps to find the suboptimal plan
quickly, and as the time passes, the algorithm, till the most appropriate plan is captured [3].
The author has discussed about the real time search approach as well. Providing a brief idea,
the author explained that, the real-time search methods handovers hard real-time bounds on

3HEURISTIC SEARCH
the action selection times, however these have not been demonstrated for the robotic systems.
Heuristics search approach is an essential approach for solving the problem in case of the
artificial intelligence frameworks. It again provides a cost efficient solution path by
representing the solution in a graph [4]. However, in case of large and complex problem,
finding an efficient as well as optimal solution path can sometime take longer time than
expected. In such cases, finding the suboptimal solution can be comparatively useful; in such
cases the anytime Heuristics search algorithm is efficient. In order to provide an example and
compare the approach with the real time search, the discussed article has explained the
anytime A* algorithm. In order to compare and get idea about the efficient heuristic search
approach, the author of this article has compared the anytime A* algorithm with the real time
LSS-LRTA* algorithm.
The A* algorithm usually considers two lists; these are identified as the Open and
Closed list. Both of the lists are essential for creating and maintaining a systematic search in a
minimum-cost path, starting from initial to the final in a graphical manner [5]. In the first
stage, the start node is mentioned in the open list and the closed list is vacant. As the
algorithm proceeds, in every cycle, the most prominent open node is set to be expanded, and
moved towards the defined closed list. However, the successor nodes are to be inserted inside
the Open list. Therefore, the closed list is left with those nodes, which have already been
expanded, by generating the associated successor nodes [6]. Whereas, the nodes that have
already been generated but not expanded are listed in the open list. The search come to an end
when a suitable goal node is generated for performing expansion. A solution path also can be
generated by tracking the node pointers in a backwards direction from the collected goal node
to the initial node [7]. On the other hand, the Local Search Space-Learning Real-Time A*
(LSS-LRTA*) can be identified as the “state-of-the-art real-time search algorithm” and it is
most suitable for those cases where there is one explicit real-time constraint present per

4HEURISTIC SEARCH
action. Similar to the anytime A* algorithm, the real time algorithm selected here also follow
two steps. Firstly, the LSS-LRTA* algorithm undertake the same procedure as the A*
algorithm follows that is searching from the current state of the agent toward a goal node
until and unless some suitable expansion limit has reached [8]. In the next step, the LSS
LRTA* algorithm selects the most suitable state present in the search frontier. After that, the
best path are queued so that efficient execution process can initiated. In order to complete a
particular path towards the goal, the LSS LRTA* follows the same procedure as the A*
algorithm. In addition, it also proceeds with a backup process similar to the Dijkstra process
in which the heuristic value of every stage is present in the look ahead search space [9].
Therefore, the intensive learning stage also beneficial for the algorithm in escaping the local
minima in a quick manner. In this case, the chosen actions are to be executed, and the search
computes the additional actions to be taken. An iteratively trajectory is constructed by the
agent in this manner [10].
The article upholds a discussion and experimental analysis section, where all the
related concepts of the discussed algorithms has discussed broadly. The discussion section
has provided a clear idea of several process undertaken by both the selected algorithms along
with a clear comparison of the potential ability and challenges of the two approaches.
Whereas, the section named “experimental result” has provided a brief knowledge about the
performance and implication approach of the anytime as well as the real time heuristic search
algorithm. Both the search algorithm’s performance has implemented in the Kotlin by using
an IBM J9 Virtual Machine in different simulated domains, such as, grid path finding with an
inertia, a four way grid path finding and in a under actuated double pendulum. Finally, the
experiment resulted that, even though the anytime algorithm is simple; yet, the real time
planning algorithm is more efficient in case of the complicated domains. Additionally, the

5HEURISTIC SEARCH
real time approach always proved to be best from the anytime approach in every instance by
delivering minimal goal achievement time.
The article has also explained the advantages as well as the limitations of both the
approaches. Real-time search suffers from two important limitations. Discussing about the
challenges of real-time search, it is found that the particular approach incomplete in many
domain where there exist dead end states, and due to this reaching to the goal node is not
possible. Secondly, the errors or the local minima present in the heuristic function might also
resulted in visiting the real time search algorithm to a particular node many times, the
algorithm do this for updating the appropriate heuristic values in the minimum. However, this
is required in those case where the size of minimum is greater than the look ahead. On flip,
three major limitation of the anytime search algorithm has also discussed in the article.
Firstly, searching in a backward direction from the goal node to the starting node needs a
predecessor function that might be non-trivial. Secondly, until and unless the first completed
plan is not generated, the agent cannot moved, which is again a time consuming process.
Lastly, as the exact time taken for finding the new plan is unknown, the goal state for the
backward search is not obvious.
Though the article have discussed important concepts related to the heuristic search
method for performing online planning successfully, yet the formulas are not clearly
mentioned. Additionally, less diagrammatic representation of the selected search and
planning algorithm makes the article less representable. However, the all the necessary
concepts are explained clearly, thus creating a wider understanding of the selected research
area. In addition, the recent sources and evidences used here clearly explained that the author
has conducted a deep research about the areas.

6HEURISTIC SEARCH
Conclusion
In conclusion, it can be said that the selected article has clearly explained all the
concepts related to both kind of heuristic search approaches. In a final outcome, the author
has described that both the algorithms are efficient enough for performing online planning
activities. However, due to completing the search activity in a less time and delivering the
goal node in a comparatively minimal time than the anytime algorithm, the real time
algorithm has proved to be more efficient. Therefore, in future, further researches can also be
carried for explaining this approach in a broader aspect. Providing a critical discussion of
both the algorithms, the article has discussed the benefits and drawbacks of all the aspects.
Despite of providing a less diagrammatic representation, the article is still a useful one. The
author has used the resent research resources and provided a discussion about the future
research area.

7HEURISTIC SEARCH
Reference
[1] S. Kiesel, E. Burns, and W. Ruml, Achieving goals quickly using real-time search:
Experimental results in video games, Journal of Artificial Intelligence Research
54:123–158, 2015.
[2] N. Sturtevant and V. Bulitko, Reaching the goal in real-time heuristic search:
Scrubbing behavior is unavoidable, In SoCS, 166–174, 2014.
[3] B. Cserna, M. Bogochow, S. Chambers, M. Tremblay, S. Katt, and W. Ruml,
Anytime versus real-time heuristic search for on-line planning, In Ninth annual
symposium on combinatorial search, 2016, June.
[4] E. Burns, W. Ruml, and M.B. Do, Heuristic search when time matters, Journal of
Artificial Intelligence Research, 47, pp.697-740, 2013.
[5] B. Cserna, W. Ruml, and J. Frank, Planning time to think: Metareasoning for on-line
planning with durative actions, In Twenty-Seventh International Conference on
Automated Planning and Scheduling, 2017, June.
[6] M. Otte, W. Silva, and E. Frew, Any-time path-planning: Time-varying wind field+
moving obstacles, In 2016 IEEE international conference on robotics and automation
(ICRA) (pp. 2575-2582). IEEE, 2016, May.
[7] B., Cserna, W.J. Doyle, J.S. Ramsdell, and W. Ruml, Avoiding dead ends in real-time
heuristic search, In Thirty-Second AAAI Conference on Artificial Intelligence, 2018,
April.
[8] D. O'Ceallaigh, and W. Ruml, Metareasoning in real-time heuristic search, In Eighth
Annual Symposium on Combinatorial Search, 2015, May.
[9] G.Sharon, A. Felner, and N. Sturtevant, Exponential deepening A* for real-time
agent-centered search, In Twenty-Eighth AAAI Conference on Artificial Intelligence,
2014, June.

8HEURISTIC SEARCH
[10] S. Kiesel, E. Burns, and W. Ruml, Achieving goals quickly using real-time
search: Experimental results in video games, Journal of Artificial Intelligence
Research, 54, pp.123-158, 2015.