Heuristic search research often deals with finding algorithms for offline planning which aim to minimize the number of expanded nodes or planning time. In online planning, algorithms for real-time search or deadline-aware search have been considered before. However, in this paper, we are interested in the problem of {\em situated temporal planning} in which an agent's plan can depend on exogenous events in the external world, and thus it becomes important to take the passage of time into account during the planning process.  
 Previous work on situated temporal planning has proposed simple pruning strategies, as well as complex schemes for a simplified version of the associated metareasoning problem. 
 In this paper, we propose a simple metareasoning technique,  called the crude greedy scheme, which can be applied in a situated temporal planner. Our empirical evaluation shows that the crude greedy scheme outperforms standard heuristic search based on cost-to-go estimates. For many years, research in heuristic search has focused on the objective of minimizing the number of nodes expanded during search (e.g BID7 ). While this is the right objective under various scenarios, there are various scenarios where it is not. For example, if we still want an optimal plan but want to minimize search time, selective max BID10 or Rational Lazy A˚ ) can be used. Other work has dealt with finding a boundedly suboptimal plan as quickly as possible BID20 , or with finding any solution as quickly as possible BID21 . Departing from this paradigm even more, in motion planning the setting is that edge-cost evaluations are the most expensive operation, requiring different search algorithms BID14 BID11 .While the settings and objectives mentioned above are quite different from each other, they are all forms of offline planning. Addressing online planning raises a new set of objectives and scenarios. For example , in real-time search, an agent must interleave planning and execution, requiring still different search algorithms BID13 BID18 BID6 BID5 . Deadline-aware search BID9 must find a plan within some deadline. The BUGSY planner BID1 attempts to optimize the utility of a plan, which depends on both plan quality and search time.In this paper we are concerned with a recent setting, called situated temporal planning BID2 . Situated temporal planning addresses a problem where planning happens online, in the presence of external temporal constraints such as deadlines. In situated temporal planning, a plan must be found quickly enough that it is possible to execute that plan after planning completes. Situated temporal planning is inspired by the planning problem a robot faces when it has to replan BID3 , but the problem statement is independent of this motivation.The first planner to address situated temporal planning BID2 ) used temporal reasoning BID8 prune search nodes for which it is provably too late to start execution. It also used estimates of remaining search time BID9 together with information from the temporal relaxed planning graph BID4 ) to estimate whether a given search node is likely to be timely, meaning that it is likely to lead to a solution which will be executable when planning finishes. It also used dual open lists : one only for timely nodes, and another one for all nodes (including nodes for which it is likely too late to start execution). However, the planner still used standard heuristic search algorithms (GBFS or Weighted A˚) with these open lists, while noting that this is the wrong thing to do, and leaving for future work finding the right search control rules.Inspired by this problem, a recent paper BID19 proposed a rational metareasoning BID17 approach for a simplified version of the problem faced by the situated planner. The problem was simplified in several ways: first, the paper addressed a one-shot version of the metareasoning problem, and second, the paper assumed distributions on the remaining search time and on the deadline for each node are known. The paper then formulated the metareasoning problem as an MDP, with the objective of maximizing the probability of finding a timely plan, and showed that it is intractable. It also gave a greedy decision rule, which worked well in an empirical evaluation with various types of distributions.In this paper, we explore using such a metareasoning approach as an integrated part of a situated temporal planner.This involves addressing the two simplifications described above. The naive way of addressing the first simplification -the one-shot nature of the greedy rule -is to apply it at every expansion decision the underlying heuristic search algorithm makes, in order to choose which node from the open list to expand. The problem with this approach is that the number of nodes on the open list grows very quickly (typically exponentially), and so even a linear time metareasoning algorithm would incur too much overhead. Thus, we introduce an even simpler decision rule, which we call the crude greedy scheme, which does not require access to the distributions, but only to their estimated means. Additionally, the crude greedy scheme allows us to compute one number for each node,Q, and expand nodes with a highQvalue first. This allows us to use a regular open list, although one that is not sorted according to cost-to-go estimates, as in standard heuristic search. In fact, as we will see, cost-to-go estimates play no role in the ordering criterion at all.An empirical evaluation on a set of problems from the Robocup Logistics League (RCLL) domain BID16 BID15 shows that using the crude greedy scheme in the situated temporal planner BID2 leads to a timely solution of significantly more problems than using standard heuristic search, even with pruning late nodes and dual open lists. Next, we briefly survey the main results of the metareasoning paper BID19 , and then describe how we derive the crude greedy decision rule, and conclude with an empirical evaluation that demonstrates its efficacy. In this paper, we have provided the first practical metareasoning approach for situated temporal planning. We showed empirically that this approach outperforms standard heuristic search based on cost-to-go estimates. Nevertheless, the temporal relaxed planning graph BID4 ) serves an important purpose here, allowing us to estimate both remaining planning time and the deadline for a node. Thus, we believe our results suggest that cost-to-go estimates are not as important for situated temporal planning as they are for minimizing the number of expanded nodes or planning time as in classical heuristic search.The metareasoning scheme we provided is a crude version of the greedy scheme of BID19 . We introduced approximations in order to make the metareasoning sufficiently fast and in order to utilize only readily available information generated during the search. We also proposed a more refined and better theoretically justified version of the algorithm ('improved greedy'), but making the improved version applicable in the planner is a non-trivial challenge that forms part of our future research.Ongoing Work: Crude version of the improved greedy schemeThe improved greedy scheme is better justified, but has an additional term where we need the complete distribution (f 1 pt, t d q is needed, rather than just the expectation ErD i s).We would like to replace this distribution with a small number of parameters than can be easier to obtain. Basically the same considerations apply here as well, except that the the term involving f 1 i requires access to the full distributions m i , D i . Given specific distribution types, it may be possible to compute this term as a function of ErD i s and e i . However, this part of the work is still in progress and at present we are not sure what parameters we can obtain during the search that would support the improved scheme.
Metareasoning in a Situated Temporal Planner This paper addresses the problem of situated temporal planning, proposing a further simplification on  greedy strategies previously proposed by Shperberg.