{'fraction_non_alphanumeric': 0.03323489323034984, 'fraction_numerical': 0.008291685597455701, 'mean_word_length': 4.403338652264638, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Planning and Execution using Inaccurate Models with Provable Guarantees

Models used in modern planning problems to simulate outcomes of real world action executions are becoming increasingly complex, ranging from simulators that do physics-based reasoning to precomputed analytical motion primitives. However, robots operating in the real world often face situations not modeled by these models before execution. This imperfect modeling can lead to highly suboptimal or even incomplete behavior during execution. In this paper, we propose an approach for interleaving planning and execution that adapts online using real world execution and accounts for any discrepancies in dynamics during planning, without requiring updates to the dynamics of the model. This is achieved by biasing the planner away from transitions whose dynamics are discovered to be inaccurately modeled, thereby leading to robot behavior that tries to complete the task despite having an inaccurate model. We provide provable guarantees on the completeness and efficiency of the proposed planning and execution framework under specific assumptions on the model, for both small and large state spaces. Our approach is shown to be efficient empirically in simulated robotic tasks including 4D planar pushing, and in real robotic experiments using PR2 involving a 3D pick-and-place task where the mass of the object is incorrectly modeled, and a 7D arm planning task where one of the joints is not operational leading to discrepancy in dynamics. Video can be found at https://youtu.be/eQmAeWIhjO8


I. INTRODUCTION
Modern robotic planning approaches involve use of models that tend to be sophisticated and complex. These models are used to simulate the dynamics of the real world and foresee the outcomes of actions executed. From using fast analytical solvers to generate motion primitives on-the-fly [10] to simulators that do reasoning based on physics, and optimization to resolve contacts [29], these models are getting better at modeling the dynamics of the real world. However, real world robotic tasks are rife with situations that cannot be predicted and therefore, modeled before execution. Thus, we need a planning approach that can use potentially inaccurate models and still complete the task.
For example, consider the task depicted in Figure 1 (left) where a robotic arm needs to pick an object and place it at a goal location. Without knowledge of the mass of the object, the model can be inaccurate in simulating the dynamics. If the object is modeled as light, the planned path would pick it to a certain height before placing it at the goal location. However, if the object is heavy in the real world, like in Figure 1 (left), this plan cannot be executed as the joint torque limits are reached and the arm cannot move higher. Thus, by using the inaccurate model for planning, the arm is stuck and cannot reach the goal. Figure 1 (right) presents another simple scenario where a mobile robot is navigating a gridworld containing icy states, where the robot slips, i.e. if the robot tries to go right or left in an icy state, it will move two cells rather than one cell in that direction. However, the model used for planning does not model the icy states and hence, cannot simulate the real world dynamics correctly. This can lead to highly suboptimal paths or sometimes even inability to reach the goal, when using such a model for planning.
A typical solution to this problem is to update the dynamics of the model and replan [28]. However, this is seldom possible in real world planning problems where we use models that are complex and in some cases obtained from expensive computation that is done offline before execution [13]. The dynamics of these models cannot be changed online arbitrarily without deteriorating their simulation capabilities in other scenarios and sacrificing real-time execution. In addition, this solution might require us to have the knowledge of what part of the model dynamics are inaccurate and how to correct it. Going back to the pick-and-place example in Figure 1, to update the model we need to first identify that the modeled mass is incorrect and then estimate the true mass to correct the dynamics of the model. Both of these steps require specialized non-trivial implementations. Finally, in the case of models that can be updated online efficiently, it might still not be possible to model the true dynamics without an unreasonably large number of online executions because the true dynamics are extremely complex, e.g. modeling cooperative navigation dynamics in human crowds [30]. The above aspects make the solution of updating model dynamics online undesirable in real world robotic tasks, where we are interested in completing the task and not in modeling the dynamics accurately.
In this work, we present an alternative approach for interleaving planning and execution that does not require updating the dynamics of the model. Instead during execution, whenever we discover an action where the dynamics differ between the real world and the model, we update the cost function to penalize executing such state-action pairs in the future. This biases the planner to replan paths that do not consist of such state-action pairs, and thereby avoid regions of state-action space where the dynamics are known to differ. Based on this idea, we present algorithms for both small state spaces, where we can do exact planning, and large state spaces, where we resort to function approximation to update the cost function and to maintain cost-to-go estimates. Our framework CMAX comes with provable guarantees on reaching the goal, without any resets, under specific assumptions on the model. The proposed algorithms are tested on a range of tasks including simulated 4D planar pushing as well as physical robot 3D pick-and-place task where the mass of the object is incorrectly modeled, and 7D arm planning tasks when one of the joint is not operational, leading to discrepancy in dynamics.

II. PRELIMINARIES
We are interested in the deterministic shortest path problem represented by the tuple M = (S, A, G, f, c) where S denotes the state space, A denotes the action space, G ⊆ S is the non-empty set of goal states we are interested in reaching, f : S × A → S denotes the deterministic dynamics governing the transition to next state given current state and action, and c : S × A → [0, 1] is the cost function. For the purposes of this work, we will focus on small discrete action spaces, bounded costs lying between 0 and 1 1 , and a cost-free termination goal state i.e. for all g ∈ G, we have c(g, a) = 0 and f (g, a) = g for all actions a ∈ A. The objective of the shortest path problem is to find the least-cost path from any given start state s 0 ∈ S to any goal state g ∈ G in M . We assume that there exists at least one path from each state s ∈ S to one of the goal states g ∈ G in M , and that the cost of any transition starting from a non-goal state is positive i.e. c(s, a) > 0 for all s ∈ S \ G, a ∈ A. These assumptions are typical for analysis in deterministic shortest path problems [6]. We use V (s) to denote the cost-to-go estimate of any state s ∈ S and V * (s) to denote the optimal cost-to-go. From dynamic programming literature [6], we know that the optimal cost-to-go satisfies the Bellman optimality condition V * (s) = min a∈A [c(s, a) + V * (f (s, a))]. A cost-to-go estimate V is called admissible if it underestimates the optimal cost-to-go V (s) ≤ V * (s) for all s ∈ S, and is called consistent if it satisfies the condition that for any state-action pair (s, a), s / ∈ G, V (s) ≤ c(s, a) + V (f (s, a)), and V (g) = 0 for all g ∈ G.
In this work, we assume that the exact dynamics are initially unknown to the robot, and can only be discovered through 1 Any bounded cost function can be scaled to fit this assumption executions. Thus, instead of offline planning methods, we need online methods that interleave planning with action execution. Specifically, we focus on the online real-time planning setting where the robot does not have access to resets, and the robot has to interleave planning and execution to ensure real-time operation. This is similar to the classical real-time search setting considered by works like LRTA* [22], RTAA* [20], RTDP [4] and several others. An important aspect of these approaches is that the robot can only perform a fixed amount of computation for planning, independent of the size of state space, before it has to execute an action.

III. PROBLEM SETUP
Consider the problem of a robot acting to find a least-cost path to a goal in an environment represented by the tuple M = (S, A, G, f, c) with unknown deterministic dynamics f and known cost function c. The robot gathers knowledge of the dynamics over a single trajectory in the environment, and does not have access to any resets, ruling out any episodic approach. This is an extremely challenging setting as the robot has to reason about whether to exploit its current knowledge of the dynamics to act near-optimally or to explore to gain more knowledge of the dynamics, possibly at the expense of suboptimality.
We assume that the agent has access to an approximate model,M = (S, A, G,f , c), that it can use to simulate the outcome of its actions and use for planning. In our motivating gridworld example (Figure 1 right), this model represents a grid with no icy states, so the dynamicsf moves the robot to the next cell based on the executed action without any slip. However, the real environment contains icy states resulting in dynamics f that differ on state-action pairs where the state is icy. For the remainder of this paper, we will refer to such state-action pairs where f andf differ as "incorrect" stateaction pairs, and use the notation X * ⊆ S × A to denote the set of all "incorrect" state-action pairs, i.e. f (s, a) =f (s, a) for all (s, a) ∈ X * . The objective is for the robot to reach a goal state from a given start state, despite using an inaccurate model for planning, while minimizing the cost incurred and ensuring real-time execution.

IV. APPROACH
Existing planning and learning approaches try to learn a very good approximation of M from scratch through online executions [18,7,16,11], or update the dynamics of modelM so that it approximates M well [1,15,26]. In this work, we take a different approach. Our main motivation is that modern planning approaches use forward models that are complex and in some cases, obtained from expensive computation that is done offline. For example, motion planning usually involves using analytical motion primitives [9] that are precomputed offline and are difficult to update during online execution without sacrificing real-time capabilities. The dynamics of these forward models cannot be changed online in any arbitrary way without deteriorating their performance in other scenarios and sacrificing real-time capabilities. In addition, to update the model dynamics we might require knowledge about the environment that we are uncertain about, like the mass of the object in our pick-and-place example in Figure 1 (left), which is hard to obtain. In domains where we do have models that can be updated efficiently online it might not be possible to model the true dynamics as it can be extremely complex and could potentially take a large number of real world executions to learn a reasonable approximation. In this work, we propose an approach CMAX that uses the inaccurate model online without updating its dynamics, and is provably guaranteed to complete the task.
In a nutshell, instead of learning a new dynamics model from scratch or updating the dynamics of existing model, CMAX maintains a running estimate of the set X t consisting of all state-action pairs that have been executed and have been discovered to be incorrect until timestep t. Using the set X t , we update the cost function to bias the planner to plan future paths that avoid state-action pairs that are known to be incorrect. It is important to note that the challenge of dealing with exploration-exploitation dilemma online still exists, as we do not know the set of state-action pairs where the dynamics differ X * ahead of online execution. A similar approach was proposed in Jiang [15] for the episodic setting where the robot had access to resets, and for small state spaces where we could perform full state space planning. CMAX extends it to the significantly more challenging online real-time setting and we present a practical algorithm for large state spaces.

A. Penalized Model
We formalize our approach as follows: Given a modelM and a set X ⊆ S × A consisting of state-action pairs that have been discovered to be incorrect so far, define the penalized modelM X as: Definition 4.1 (Penalized Model): The penalized model M X = (S, A, G,f ,c X ) has the same state space, action space, set of goals, and dynamics asM . The cost functioñ c X is defined asc X (s, a) = |S| if (s, a) ∈ X , elsẽ c X (s, a) = c(s, a).
Intuitively, the penalized modelM X has a very high cost for any transition where the dynamics differ, i.e. (s, a) ∈ X , and the same cost as the modelM otherwise. More specifically, the cost is inflated to the size of the statespace, which is the maximum cost of a path that visits all states 2 (remember, that our cost is normalized to lie within 0 and 1.) This biases the planner to "explore" all other state-action pairs that are not yet known to be incorrect before it plans a path through an incorrect state-action pair. In the next section, we will describe how we use the penalized modelM X for real-time planning.

B. Limited-Expansion Search for Planning
During online execution, the robot has to constantly plan the next action to execute from its current state in real-time. This forces the robot to use a fixed amount of computation for planning before it has to execute the best action found so far. 2 Hence, the name CMAX for our approach If s i ∈ G, then s best ← s i and move to Line 19 8: Expanding state s i 9: Get successor s =f (s i , a) 10: If s ∈ C, continue to next action 11: if s ∈ O and g(s ) > g(s i ) +c X (s i , a) then 12:  for s ∈ C do 20: Backtrack from s best to s, and set a best as the first action on path from s to s best return a best In this work, we use a real-time search method that is adapted from RTAA* proposed by Koenig and Likhachev [20]. The planner is summarized in Algorithm 1. At any timestep t, given the current penalized modelM Xt and the current state s t , the planner constructs a lookahead search tree using K state expansions. We obtain the successors of any expanded state and the cost of any state-action pair using the penalized modelM Xt . After expanding K states, it finds the best state s best among the leaves of the search tree that has the least sum of cost-to-come from s t and cost-to-go to a goal state. The best action to execute in the current state s t is chosen to be the first action on the path from s t to s best in the search tree and the cost-to-go estimates of all expanded states are updated as: where g(s) is the cost-to-come from s t for any state s in the search tree. The amount of computation used to compute the best action for the current state is bounded as a factor of the number of expansions K in the search tree. Thus, we can bound the planning time and ensure real-time operation for our robot.

C. Small State Spaces
In this section, we will present an algorithm that is applicable for small discrete state spaces where it is feasible to maintain cost-to-go estimates for all states s ∈ S using a tabular representation, and we can maintain a running set X t containing all the discovered incorrect state-action pairs so far, without resorting to function approximation. The algorithm is shown in Algorithm 2. Intuitively, Algorithm 2 maintains Algorithm 2 CMAX -Small State Spaces Update the penalized model :M t+1 ←M Xt+1 8: a running set of incorrect state-action pairs X t , updates the set whenever it encounters an incorrect state-action pair, and recomputes the penalized modelM Xt . Crucially, the algorithm never updates the dynamics of the modelM , and only updates the cost function according to Definition 4.1. In order to prove completeness, we assume the following: Assumption 4.1: Given a penalized modelM Xt and the current state s t at any timestep t, there always exists at least one path from s t to a goal state that does not contain any state-action pairs (s, a) that are known to be incorrect, i.e. (s, a) ∈ X t . 3 Under this assumption, we can show the following guarantee for Algorithm 2: Theorem 4.1: Assume Assumption 4.1 holds then, if X * denotes the set consisting of all incorrect state-action pairs, and the initial cost-to-go estimates used are admissible and consistent, then using Algorithm 2 the robot is guaranteed to reach a goal state in at most |S| 2 timesteps. Furthermore, if we allow for K = |S| expansions, then we can guarantee that the robot will reach a goal state in at most |S|(|X * |+1) timesteps.
Proof of the above theorem is given in Appendix A. The above theorem establishes that using Algorithm 2, the robot is guaranteed to reach a goal state under Assumption 4.1. In practice, we observe that the number of timesteps to reach a goal has a smaller dependence on the size of state space than the worst-case bound, especially if Algorithm 2 starts with cost-to-go estimates that are reasonably accurate for the initial modelM .

D. Large State Spaces
In large state spaces, it is infeasible to maintain cost-to-go estimates for all states s ∈ S using a tabular representation and maintain a running estimate of the set X t , as both could be very large in size. Thus, we will need to resort to function approximations for both cost-to-go estimates and the set X t .
We will assume existence of a fixed distance metric d : S×S → R + ∪{0}, and that S is bounded under this metric. We relax the definition of X using the distance metric d as follows: Define any state-action pair (s, a) ∈ X ξ to be ξ-incorrect if d(f (s, a),f (s, a)) > ξ where ξ ≥ 0. This definition helps us to not count any discrepancy smaller than ξ as an incorrect pair. We assume that there is an underlying path controller that is used to execute our plan and can deal with small discrepancies less than ξ.
Our algorithm for large state spaces is presented in Algorithm 3. The main idea of the algorithm is to "cover" the set X ξ using hyperspheres in S × A. Since the action space A is a discrete set, we maintain separate sets of hyperspheres for each action a ∈ A. Whenever the agent encounters an incorrect state-action pair (s, a) ∈ X ξ , it places a hypersphere at s corresponding to action a whose radius (as measured by the metric d) is given by δ > 0, a domain-dependent constant. We inflate the cost of a state-action pair (s, a), according to Definition 4.1, if s lies inside any hypersphere corresponding to action a. In practice, this is implemented by constructing separate KD-Trees in state space S for each action a ∈ A to enable efficient lookup.
After executing the action and placing a hypersphere if a discrepancy in dynamics was observed, the function approximation for cost-to-go is updated iteratively as follows (Line 15 to Line 17): Sample a batch of states from the buffer of previously visited states with replacement, construct a lookahead tree for each state in the batch (through parallel jobs) to obtain all states on the closed list and their corresponding cost-to-go updates using Algorithm 1, and finally update the parameters of the cost-to-go function approximator to minimize the mean squared loss L(V θ , X) = 1 2|X| (s,V (s))∈X (V (s) − V θ (s)) 2 for all the expanded states through a gradient descent step (Line 17).
Observe that, similar to Algorithm 2, we do not update the dynamicsf of the model, and only update the cost function according to Definition 4.1. However, unlike Algorithm 2, we do not explicitly maintain a set of incorrect state-action pairs but maintain it implictly through hyperspheres. By using hyperspheres, we obtain local generalization and increase the cost of all the state-action pairs inside a hypersphere. In addition, unlike Algorithm 2, we update cost-to-go estimates of not only the expanded states in the lookahead tree obtained from current state s t , but also from previously visited states. This ensures that the function approximation used for maintaining cost-to-go estimates does not deteriorate for states that were previously visited, and potentially help in generalization.
We can provide a guarantee on the completeness of Algorithm 3 by assuming the following: Assumption 4.2: Given a penalized modelM X ξ t and the current state s t at any timestep t during execution, there always exists at least one path from s t to a goal state that is at least δ distance away from any state-action pair (s, a) that is known to be ξ-incorrect, i.e. (s, a) ∈ X ξ t . The above assumption has two components: the first one relaxes Assumption 4.1 to accommodate the notion of ξincorrectness, and the second one states that, unlike Assumption 4.1, there exists a path that not only does not contain any Execute a t in environment M to get s t+1 ← f (s t , a t )

5:
if d(s t+1 ,f (s t , a t )) > ξ then 6: UpdateM t+1 ←M X ξ t+1 10: Add s t to buffer D 11: 12: t ← t + 1 13: function UPDATE(s,M , V θ , D) 14: for n = 1, · · · , N do 15: Sample batch of B states S n from buffer D with replacement 16: Call SEARCH(s i ,M , V θ , K) for each s i ∈ S n to get all states on closed list s i and their corresponding cost-to-go updates V (s i ) and construct the training set state-action pairs that are known to be ξ-incorrect, but also that any state-action pair on the path is at least δ distance, as measured by the metric d, away from any state-action pair that is known to be ξ-incorrect. The second component makes this assumption stronger. However, it can lead to substantial speedups in the time taken to reach a goal as we can place hyperspheres of radius δ to quickly "cover" the ξ-incorrect set.
Algorithm 3 employs approximate planning by using a function approximator for cost-to-go estimates and performing batch updates to fit the approximator. This is necessary as the state space is large, and maintaining tabular cost-to-go estimates for each state is expensive in memory and would take a large number of timesteps to update them in practice. However, for ease of analysis, we will assume that we do exact updates and maintain tabular cost-to-go estimates like Algorithm 2. Then, we can show the following guarantee: Theorem 4.2: Assume Assumption 4.2 holds then, if X ξ denotes the set of all ξ-incorrect state-action pairs, the initial cost-to-go estimates are admissible and consistent, then using Algorithm 3 with exact updates and tabular representation for cost-to-go estimates, the robot is guaranteed to reach a goal state in at most |S| 2 timesteps. Furthermore, if we allow for K = |S| expansions, then we can guarantee that the robot will reach a goal state in at most |S|(C(δ) + 1) timesteps, where C(δ) is the covering number of the set X ξ .
Proof of the above theorem is given in Appendix B. The above theorem states that, using Algorithm 3, the robot is guaranteed to reach a goal state, if the initial cost-to-go estimates are admissible and consistent. The theorem also provides a stronger guarantee that the number of timesteps to the goal has a dependence on the covering number, if we do |S| number of expansions at each timestep. Covering number C(δ) of a set A is formally defined as the size of the set B of state-action pairs (s, a) such that A ⊆ (s,a)∈B sphere(s, a, δ). Note that the covering number C(δ) is typically much smaller than the size of the set X ξ . Although performing |S| expansions at each timestep is infeasible in large state spaces with real-time constraints, it is useful to note that we achieve speedup from adding hyperspheres of radius δ. Importantly, the efficiency of the Algorithm 3 degrades gracefully with decreasing δ and reduces to the bound presented in Theorem 4.1, if only Assumption 4.1 holds. Similar to the worst-case bounds presented in Theorem 4.1, the number of timesteps it takes for the robot to reach a goal state, in practice as shown in our experiments, has a much smaller dependence on size of state space if we start with cost-to-go estimates that are reasonably accurate for the initial modelM , and use cost-to-go function approximation as we do in Algorithm 3.

V. EXPERIMENTS
We test the applicability and efficiency of our approach CMAX on a range of robotic tasks across simulation and real-world experiments. In all experiments, we record the mean and standard error for the number of timesteps taken by the robot to reach the goal emphasizing the performance of CMAX. The video of our physical robot experiments can be found at https://youtu.be/eQmAeWIhjO8 and code to reproduce simulated experiments can be found at https: //github.com/vvanirudh/CMAX.

A. Simulated 4D Planar Pushing in the Presence of Obstacles
In this experiment, the task is for a robotic gripper to push a cube from a start location to a goal location in the presence of static obstacles without any resets, as shown in Figure 2 (right). This can be represented as a planning problem in 4D continuous state space S with any state represented as the tuple s = (g x , g y , o x , o y ) where (g x , g y ) are the xy-coordinates of the gripper and (o x , o y ) are the xy-coordinates of the object. The modelM used for planning does not have the static obstacles and the robot can only discover the state-action pairs that are affected due to the obstacles through real world executions. The action space A is a discrete set of 4 actions that move the gripper end-effector in the 4 cardinal directions by a fixed offset using an IK-based controller. The cost of each transition is 1 when the object is not at the goal location, and 0 otherwise.
We compare CMAX with the following baselines: a modelfree Q-learning approach [24] that learns from online executions in environment and does not use the modelM , and a model learning approach that uses limited-expansion search for planning but updates a learned residual that compensates for the discrepancy in dynamics between the model and  Steps subcolumn is obtained using 20 random start and goal locations, and we present mean and standard error of number of timesteps it takes the robot to reach the goal among successful trials. The % success subcolumn indicates percentage of successful trials where the robot reached the goal in less than 1000 timesteps. The last row corresponds to using the planner with an accurate model (the same as the environment.) environment. The model learning approach is very similar to previous works that learn residual dynamics models and have been shown to work well in episodic settings [26,12,27]. The predicted residual is added to the next state, according to the model, to obtain the learned next state. We chose two function approximators for the learned residual dynamics to account for model learning approaches that use global function approximators such as neural networks (NN) [14], and local function approximators such as K-nearest neighbor regression (KNN) [25,16]. Finally, we compare against a limitedexpansion search planner that uses an accurate model with the full knowledge about obstacles to understand the difficulty of the task. To ensure a fair comparison across all baselines, we use the same neural network function approximator for cost-to-go, and start with the same initial cost-to-go estimates. Specific details on the architecture and baseline parameters can be found in Appendix C. For our implementation, we follow Algorithm 3 with euclidean distance metric, ξ = 0.01, and δ = 0.02. These values are chosen to capture the discrepancies observed in the object and gripper position when pushed into an obstacle, and the size of the obstacles. We use the same values for the model learning KNN baseline to ensure a fair comparison. For all the approaches, we use a limited expansion search planner with K = 5 expansions, N = 5 planning updates, batch size B = 64, and an Adam optimizer [19] with learning rate η = 0.001. The results of our experiments are presented in Table I. We notice that all the approaches have almost the same performance when both model and environment have no obstacles (first column). This validates that all the baselines do well when the model is accurate. However, when the model is inaccurate (second column), the performance varies across baselines. Q-learning performs decently well since it relies on the model only for the initialized Q-values and not during online executions, but as the task is now more difficult, it solves much fewer trials and is highly suboptimal. It is interesting to see that model learning baselines do not do as well as one would expect. This can be attributed to the number of online executions required to learn the correct residual, which can be prohibitively large. Among the two model learning baselines, KNN works better since it requires fewer samples to learn the residual, while NN requires large  amounts of data. In contrast, CMAX does not seek to learn the true dynamics and instead is more focused on reaching the goal quickly. When compared with a planner that uses the accurate model with obstacles and solves 17 trials (last row in Table I), our approach solves 16 trials and achieves the lowest mean number of timesteps to reach the goal among all baselines. We would like to note that the planner with accurate model takes a larger number of timesteps because we used the same initial cost-to-go estimates as other approaches. The initial cost-to-go estimates are more accurate for the model with no obstacles than for the model with obstacles. Hence, it spends a larger number of timesteps updating cost-to-go estimates. This experiment shows that by focusing on reaching the goal and not trying to correct the model dynamics, CMAX performs the best and solves the most number of trials among baselines.

B. 3D Pick-and-Place with a Heavy Object
The task of this physical robot experiment (Figure 3) is to pick and place a heavy object using a PR2 arm from a start pick location to a goal place location while avoiding an obstacle. This can be represented as a planning problem in 3D discrete state space S where each state corresponds to the 3D location of the end-effector. In our experiment, we discretize each dimension into 20 bins and plan in the resulting discrete state space of size 20 3 . Since it is a relatively small state space, we use exact planning updates without any function approximation following Algorithm 2 with K = 3 expansions. The action space is a discrete set of 6 actions corresponding to a fixed offset movement in positive or negative direction along each dimension. We use a RRT-based motion planner [23] to plan the path of the arm between states, while avoiding collision with the obstacle. The modelM used by planning does not model the object as heavy and hence, does not capture the dynamics of the arm correctly when it holds the heavy object. The cost of each transition is 1 if object is not at the goal place location, otherwise it is 0.
We observe that if the object was not heavy, then the arm takes the object from the start pick location to the goal place location on the optimal path which goes above the obstacle (first 3 images of Figure 3). However, when executed with a heavy object, the arm cannot lift the object beyond a certain height as its joint torque limits are reached. At this point, the Fig. 3: Physical robot 3D pick-and-place experiment. The task is to pick the object (light -wooden block, heavy -black dumbbell) and place it at the goal location (green) while avoiding the obstacle (box). For the light object (first 3 images), the model dynamics are accurate and the robot takes it on the optimal path that goes above the obstacle. For the heavy object (next 3 images), the model dynamics are inaccurate but using CMAX the robot discovers that there is a discrepancy in dynamics when the object is lifted beyond a certain height (due to joint torque limits), adds hyperspheres at that height to account for these transitions (red spheres in the last image), and quickly finds an alternate path going behind the obstacle. Fig. 4: Physical robot 7D arm planning experiment. The task is to start from a fixed configuration (shown in the first image) and move the arm so that the end-effector reaches the object place location (green). When the shoulder lift joint is operational, the robot uses the joint to quickly find a path to the goal (middle image). However, when the joint is non-operational, it encounters discrepancies in its model and compensates by finding a path that uses other joints to reach the goal (last image.) robot notes the discrepancy in dynamics between the model M and the real world, and inflates the cost of any executed transition that tried to move the object higher. Subsequently, the robot figures out an alternate path that does not require it to lift the object higher by taking the object behind the obstacle to the goal place location (last 4 images of Figure 3). The robot takes 36 timesteps (25.8 seconds) to reach the goal with the heavy object, in comparison to 26 timesteps (22.8 seconds) for the light object (see attached video). Thus, the robot using CMAX successfully completes the task despite having a model with inaccurate dynamics.

C. 7D Arm Planning with a Non-Operational Joint
The task of this physical robot experiment ( Figure 4) is to move the PR2 arm with a non-operational joint from a start configuration so that the end-effector reaches a goal location, specified as a 3D region. We represent this as a planning problem in 7D discrete statespace S where each dimension corresponds to a joint of the arm bounded by its joint limits. Each dimension is discretized into 10 bins resulting in a large state space of size 10 7 . The action space A is a discrete set of size 14 corresponding to moving each joint by a fixed offset in the positive or negative direction. We use an IK-based controller to navigate between discrete states. The modelM used for planning does not know that a joint is non-operational and assumes that the arm can attain any configuration within the joint limits. In the real world, if the robot tries to move the non-operational joint, the arm does not move. Thus, the robot realizes unreachable states only through real world executions.
For the purpose of this experiment, we follow Algorithm 3 with δ = 1, ξ = 1, and make the shoulder lift joint (marked by red cross and arrows in last image of Figure 4) of PR2  (right) Performance of our approach for 4D planar pushing as the radius of the hypersphere δ varies. The plot is generated for each value of radius δ by generating 10 random start and goal locations, and running CMAX for a maximum of 400 timesteps.
non-operational. We use a kernel regressor with RBF kernel of length scale γ = 10 for the cost-to-go function approximation. Figure 4 shows CMAX operating in the real world to place an object at a desired location with a goal tolerance of 10 cm. When the shoulder lift joint is operational, the robot finds a path quickly to the place location by using the joint (middle image of Figure 4). However, when the shoulder lift joint is non-operational, the robot notes discrepancy in dynamics whenever it tries to move the joint, places hyperspheres in 7D to inflate the cost, and comes up with an alternate path (last image of Figure 4) to reach the place location. The robot takes 13 timesteps (32.4 seconds) to reach the goal location with the non-operational joint, in comparison to 10 timesteps (25.8 seconds) for the case where the joint is working (see attached video). Thus, the robot successfully finds a path to the place location despite using a model with inaccurate dynamics.
To emphasize the need for cost-to-go function approximation and local generalization from hyperspheres in large state spaces, we compared CMAX against Adaptive RTAA*, an exact planning method that uses a tabular representation for cost-to-go estimates and updates model dynamics online. Results are presented in Figure 2 (left) and show that RTAA* fails to solve 7 of the 10 trials whereas CMAX solves all of them, and in less mean number of timesteps.

D. Effect of Function Approximation and Size of Hyperspheres
While previous experiments have tested CMAX against other baselines and on a physical robot, this experiment is designed  to evaluate the effect of cost-to-go function approximation and the size of hyperspheres on the performance of CMAX in large state spaces (Algorithm 3.) For the first set of experiments, we use the setup of Section V-C and focus on varying the smoothness of the kernel regressor cost-to-go function approximation by varying the length scale γ of the RBF kernel. Intuitively, small length scales result in approximation with high variance, and for large scales we obtain highly smooth approximation. The results are presented in Figure 5 (left.) We notice that for small γ, the performance is poor and as γ increases, the performance of CMAX becomes better as it can generalize the cost-to-go estimates in the state space. However, for large γ the performance deteriorates as it fails to capture the difference in cost-to-go values among nearby states due to excessive smoothing. This showcases the need for generalization in cost-to-go estimates for efficient updates in large state spaces. For the second set of experiments, we vary the radius of the hyperspheres δ introduced whenever an incorrect stateaction pair is discovered in Algorithm 3. We use the setup of Section V-A, vary δ and observe the number of timesteps it takes the robot to push the object to the goal. The results are presented in Figure 5 (right.) We observe that when δ is large, the performance is poor as we potentially penalize state-action pairs that are not incorrect and could result in a very suboptimal path. However, a very small δ can also lead to a poor performance, as we need more online executions to discover the set of incorrect state-action pairs. Hence, the radius δ needs to be chosen carefully to quickly "cover" the incorrect set, while not penalizing any correct state-action pairs.

E. Simulated 2D Gridworld Navigation with Icy States
In our final experiment, we want to understand the performance of CMAX compared to other baselines in small domains where model dynamics can be represented using a table, and can be updated efficiently. We consider the 2D gridworld such as the one shown in Figure 1(right) with icy states where the robot slips (moving left or right on ice moves the robot by two cells.) The model used for planning does not contain ice, and is an empty gridworld. Random gridworlds with ice of size 100 × 100 are generated, with random start and goal locations for the robot, and we compare CMAX (Algorithm 2) with the following baselines: Adaptive RTAA*, and Q-learning, a model-free baseline that learns solely from online executions. The results are presented in Table II. We can observe that model-free approaches like Q-learning perform well compared to model-based approaches in cases where the model available is highly inaccurate (see Table II last column.) However, when the model is reasonably accurate Adaptive RTAA* performs the best. But the results show that even in domains where model dynamics are simple and can be updated efficiently, CMAX competes closely with Adaptive RTAA*. Thus, our approach is still applicable in such domains and is relatively easier to implement.

VI. RELATED WORK
The proposed approach has components concerning realtime heuristic search, local function approximation methods, and dealing with inaccuracy in models. There is a wide array of existing work at the intersection of planning and learning that deal with these topics, and have served as an inspiration for our work. Notably, we leverage prior work on real-time heuristic search [22,20] for the limited-expansion search-based planner presented in Algorithm 1. Using local function approximation methods in robotics has been heavily explored in seminal works [31,2] due to their smaller sample complexity requirements and local generalization properties that do not cause interference [3,8]. More recently, [16], [25] and [5] have also proposed approaches that learn local models from online executions. However unlike CMAX, they use these models to approximate the dynamics of the real world. Our work is also closely related to the field of real-time reinforcement learning that tackles the problem of acting near-optimally in unknown environments, without any resets [28,4,21]. The analysis presented in Theorem 4.1 and 4.2 borrows several useful results from Koenig and Simmons [21]. Prior works in model-based reinforcement learning with provable guarantees, such as [18,5,7,17], are also related. However, these works learn the true dynamics by updating the model and give sample complexity results in the finitehorizon setting or discounted infinite-horizon setting, unlike our shortest path setting. Among these works, Kakade et al. [17], which proposes a method for exploration in metric state spaces, serves as an inspiration for the covering number bounds given in Theorem 4.2. The work that is most closely related to ours is Jiang [15] which proposed an approach that uses a similar idea of updating the cost function, in cases where updating the model dynamics is infeasible. However, the approach is suitable only for episodic settings and small state spaces. We extend it to the challenging online real-time setting and provide an algorithm for large state spaces.

VII. DISCUSSION AND CONCLUSION
In this concluding section, we would like to highlight the main advantages and shortcomings of CMAX. The biggest advantage of CMAX is that it does not rely on any knowledge of how the model is inaccurate, whether it can be updated in real-time, and ways to correct its dynamics. Hence, it is broadly applicable in real world robotic tasks with complex inaccurate models. In our experiments, we have tested on several high-dimensional robotic tasks ranging from 4D planar pushing to 3D pick-and-place to 7D arm planning, which shows the versatility of CMAX. In comparison, approaches that update the model dynamics online rely on the flexibility of the model to be updated, knowledge of what is lacking in the model, and a large number of online executions to correct it. For example, to learn accurate dynamics for a transition in N -D statespace we need at least N samples in the worst case, whereas our approach needs only 1 sample to observe a discrepancy and inflate the cost. CMAX has a few shortcomings as well. The most important shortcomings are Assumptions 4.1 and 4.2, which are hard to verify, and are not satisfied in several real world robotic tasks. For example, consider the task of opening a spring-loaded door which is not modeled as loaded. All transitions would have discrepancy in dynamics, and CMAX as is would fail at completing the task in a reasonable amount of time.
To summarize our work, we present an approach CMAX for interleaving planning and execution using inaccurate models that does not require updating the dynamics of the model, and still provably completes the task. We propose practical algorithms for both small and large state spaces, and deploy them successfully in real world robot tasks showing its broad applicability. In simulation, we analyze CMAX and show that it outperforms baselines that update dynamics online. Future directions include establishing similar guarantees like Theorem 4.2 in the approximate planning setting, and relaxing Assumptions 4.1, 4.2 so that CMAX is applicable to a wider range of robotic tasks.