CoBots: Robust Symbiotic Autonomous Mobile Service Robots

1 Introduction

We research, develop, and deploy multiple autonomous mobile robots capable of performing tasks requested by users in our multi-floor office building. To successfuly perform service tasks, our robots have several core capabilities, namely:

• To autonomously localize and navigate in the diverse types of indoor space, including corridors, elevators, and open areas with movable furniture and people.
• To schedule conflict-free plans for multiple robots to satisfy constrained tasks specified and requested by users.
• To overcome the robots' own limitations, in particular in actuation, by proactively ask for help from humans.

Our current four Collaborative Robots, CoBot-1 through CoBot-4 (see Figure 1) can be viewed as mobile, computing, and sensing platforms, that behave as service robots. 1

Mobile robots, by definition, need to be able to move, in our case, in indoor environments. Such capability has been extensively investigated. The fact that our research goal includes the persistent deployment of the CoBots led to the introduction of novel mapping, sensing, and localization approaches [Biswas, 2014]. The robots classify sensed obstacles as map-known long-term features (walls) or mapmissing short-term (furniture) and dynamic (people) features. This explicit distinction enables the overall effective episodic non-Markovian localization approach [Biswas et al., 2011; Biswas and Veloso, 2012; 2013].

1 Thanks to Mike Licitra for designing and building the CoBots, and to Joydeep Biswas for keeping them functional.

Service robots need to be able to perform service tasks. The CoBot robots can perform multiple classes of tasks, as requested by users through a website [Ventura et al., 2013], in person through speech [Kollar et al., 2013] or on the robot's touch screen. All tasks can be represented as pick up and delivery tasks of objects or people. The task scheduler takes into account time and location constraints, as well as the multiple available robots, and issues plans that can include transfers [Coltin, 2014].

As can be seen in Figure 1, a CoBot has no hands but has a basket, so it can carry, but not manipulate items. To overcome this actuation limitation, and inevitably other types of limitations, the robots proactively ask for help from humans [Rosenthal et al., 2010; 2011], and from the web [Samadi et al., 2012]. They can gather and use models of human help and preferences in a human-centered planning approach [Rosenthal, 2012].

2 Episodic non-Markov Localization

A variety of early robots, such as Shakey [Nilsson, 1984]), Xavier [Simmons et al., 1997], and museum tour guide robots [Burgard et al., 1999; Fong et al., 2003], and more recent ones [Chen et al., 2012; Randelli et al., 2013; Christensen et al., 2010; Hawes et al., 2007; Dias and Ventura, 2013; Zhang and Stone, 2015; Visser and Burkhard, 2007]. All of these efforts include variations of localization algorithms [Dellaert et al., 1999]. Our CoBot robots, as deployed in a multi-floor university building setting, now for more than 1,000km, have faced new challenges.

Over the course of their regular deployments, the CoBots are exposed to a variety of types of environments. Some environments like corridors remain largely invariant over time, with little or no changes. Other environments like cafe areas and open atria, exhibit significant changes over time, with objects like tables and chairs being moved around frequently, and numerous dynamic obstacles like humans. Such environments pose a challenge to localization algorithms that assume that the world can be represented by a static map.

To localize in the presence of frequently observed movable and moving objects, we introduce Episodic non-Markov Localization [Biswas and Veloso, 2014] that explicitly reasons about observations of non-mapped objects without saving locally static maps. Episodic non-Markov localization maintains a belief of the history of pose estimates of the robot over "episodes" of observations of unmapped objects. For every time-step, it classifies observations into those arising from the map ("Long Term Features", LTFs), from unmapped static objects ("Short Term Features", STFs), or from moving objects ("Dynamic Features", DFs). The correlations between poses of the robot due to the presence of STFs and DFs are represented by a "Varying Graphical Network" (VGN), which we introduce next.

2.1 The Varying Graphical Network

As in a Dynamic Bayesian Network, a VGN includes certain periodically repeating nodes and edges that do not change with the belief. We term these the non-varying nodes and edges. A VGN includes two additional structural elements: varying nodes and varying edges. The presence and structure of the varying nodes and varying edges are not known apriori, and are estimated jointly with the belief. Since the estimates of the structure may change with the belief, the structure is likely to change as new observations become available.

VGNs provide an accurate representation for non-Markov localization. The presence of LTFs and their relations to the map, and the correlations between successive poses of the robot due to odometry observations are encoded by the nonvarying edges and nodes. The presence of STFs and DFs is encoded by the presence of associated varying nodes. The correlations between STFs observed at different time-steps is encoded by the varying edges. The Belief of the robot's localization, Bel(x1:n) is maintained over a history of n poses x1:n. For each timestep i, odometry ui corresponds to the robot's relative motion between poses xi-1 and xi, and observation si, made at pose xi, includes observations of LTFs that match the map, as well as unexpected observations of STFs and DFs.

Since the VGN for non-Markov localization has no predefined structure, it might seem that the computation of the belief would require storing the complete history of all states and observations since the robot was turned on. However, in practice this is not necessary, as we rely on the existence of "episodes" in non-Markov localization. Suppose there exists a time step ti such that all observations and state estimates made after ti, given xi, are independent of all prior observations and state estimates:

This conditional independence implies that there are no STF observations after ti that correspond to STF observations before ti. In such a case, the history of states and observations prior to ti, called the "episode" t0:i-1, can be discarded when estimating Bel(xi:n) over the episode ti:n. We assume such episode-boundary time-steps like ti exist, allowing real-time non-Markov localization with limited computational resources. Figure 2 shows an example VGN near an episode boundary, highlighting the absence of any varying edges crossing the episode boundary.

The exact structure of the VGN depends on the specific LTFs and STFs that are observed by the robot, and we next present how the observations are classified.

2.2 Classification of Long-Term and Short-Term Features

For every time-step, the structure of the VGN, based on the classification of the observations into LTFs, STFs and DFs, is re-evaluated prior to updating the MLE of the belief. In this work the sensor we use is a laser rangefinder, so each observation si is a set of ni 2D points si = {pij }j=1:ni observed by the robot. We represent the pose xi of the robot on the map at time-step i as an affine transform Ti that consists of a 2D rotation followed by a 2D translation.

We use a vector map [Biswas et al., 2011] representation Mvector = {li}1=1:s for the permanent map, consisting of a set of s line segments li. To evaluate which of the observed points pik are LTFs, an analytic ray cast [Biswas and Veloso, 2012] is performed from the latest MLE of xi. The result of the analytic ray cast is a mapping from pij → lj ∈ Mvector, indicating that the line segment lj from map Mvector is the most likely line in the map to be observed by the point pij . Let dist(p, l) denote the perpendicular distance of point p from the line segment l where both p and l are in the reference frame of the map. The observation likelihood P(pij |Ti,Mvector) of the point pij is then given by

where Σs is the scalar variance of observations, which depends on the accuracy of the sensor used. Thus, observations are classified as LTFs if the observation likelihood of the point given the map is greater than a threshold, P (pij |xi, Mvector) > ϵLTF.

Observed points that are classified as non-LTFs could potentially be STFs. To check if an observed point pij ∈ LTFi is an STF, it is compared to all non-LTF points observed prior to time-step i to check if they correspond to observations of the same point. Given a point pij ∈ LTFi observed at time-step i and another point plk ∈ LTFl observed at a previous timestep l, the probability that both the observations correspond to the same point is given by the STF observation likelihood function,

Therefore, a non-LTF point pij ∈ LTFi is classified as an STF if there exists a point plk ∈ LTFl from a time-step l, l < i such that P (pij , plk |xi, xl) > ϵSTF.

Given the classifications, and the form of the observation likelihoods of the LTFs and STFs, episodic non-Markov localization solves for the maximum likelihood estimate of the belief by representing the Belief as a cost function and optimizing over it, instead of keeping multiple estimates represented as a particle filter [Biswas, 2014].

We convert the belief from a probability distribution representation to a cost function representation C such that

The cost function C consists of a sum of m sub-cost functions cSTF j corresponding to the STF terms P(sSTFj 1:n |x1:n), n sub-cost functions cLTF i corresponding to the LTF terms P (sLTF i |xi,M), and n sub-cost functions codom i corresponding to the odometry terms P(xi|xi-1, ui).

The Maximum Likelihood Estimate x∗1:n is therefore computed by minimizing the cost function as:

Thus, Episodic non-Markov Localization updates the maximum likelihood location estimates of the robot via functional non-linear least squares optimization of Equation 5.

2.3 Results

Episodic non-Markov Localization has been deployed on all the CoBots over part of a 1,000km Challenge [Biswas, 2014], and has been used to localize the robots in many different environments spanning multiple floors across multiple buildings. In particular, it has been instrumental in increasing the robustness of localization on floors with challenging open areas, like a large atrium on the floor GHC4. Figure 3 illustrates different placements of the STFs, namely movable furniture.

To highlight the contribution of the robustness of Episodic non-Markov localization to the deployments of the CoBots, we tabulate the mean distance traversed autonomously by the CoBots between operator interventions in Table 1.

The CoBots traversed a mean distance of 4.42km between interventions while using EnML for localization as opposed to 0.62km when using Corrective Gradient Refinement (CGR) [Biswas et al., 2011], a variant of Markov Localization. Overall, EnML allowed the CoBots to traverse a mean of 8.13km as opposed to 4.79km when using CGR. The increased robusteness is attributed to the ability of EnML to reason better about observations of unmapped objects, and hence its robustness to changes in the environment.

3 Scheduling for Transfers with CoBots

Tasks requested by users are processed by a scheduler that computes an ordered assignment of tasks to the multiple robots. The scheduler needs to satisfy various constraints stated by the users, including location, time windows, transportation capacities of the robots, and maximum delivery times. The goal of scheduler is to find a valid schedule which minimize the total distance traveled by the robots and, or the completion times of the tasks. The scheduler outputs task execution times for each robot, and sends lists of tasks to the robots. During execution, the robots update the scheduler of their progress.

We realized that the robots can perform their tasks more efficiently by transferring items between one another [Coltin, 2014]. For example, the scheduler, without considering transfers, could assign CoBot-1 and CoBot-2 both to pick up items on the seventh floor that they need to deliver to the ninth floor. Instead of both taking an elevator ride, CoBot-1 could transfer its item to CoBot-2, which could deliver both items.

Initially, we introduce a scheduler that generates an optimal schedule for the CoBots using mixed integer programming (MIP) [Coltin, 2014]. Finding the optimal schedule is NPhard, so the MIP solver scales poorly, although for our typical usage of less than fifteen tasks at once solving the problem optimally is feasible.

To scale to larger problems, we developed an approximation algorithm for a variant of the scheduling problem in which all the items share the same destination and there are no time constraints. This is a common scenario for the CoBots, when they pick up mail for delivery to the central office, or hand out candy to building occupants for Halloween. The approximation algorithm is based on an approximation for the traveling salesman problem, and returns a solution that is guaranteed to be within a factor of two of optimal in terms of total distance traveled [Coltin and Veloso, 2014a].

Expanding to the more general problem in which items have distinct destinations, we introduced three heuristics to from schedules, still without considering time: a greedy approach, an algorithm based on auctions, and an algorithm where an item's entire trajectory is inserted into a graph of transfers. The heuristics reduce the search space by inserting transfers into existing schedules, and hence may not find the optimal solution. Transfers were shown to reduce the solution cost compared to similar heuristics without transfers [Coltin and Veloso, 2014b].

We extended the auction heuristic to work with time windows, by determining execution times through the use of simple temporal networks. The auction algorithm is applied online as new tasks come in from users, so that the CoBots replan online. If a CoBot is delayed or disabled, the other CoBots replan so that the tasks are still completed as quickly as possible (see Figure 4).

The CoBots also take advantage of the fact that there are multiple robots to replan better schedules. If a robot is blocked in a hallway, it will inform the other robots it is blocked. The other robots will then replan to avoid the blocked hallway, if possible, as shown in Figure 5. Additionally, robots detect if doors are open or closed when they drive past. If one robot happens to drive by a closed door that another robot is planning to pick up or deliver an item from, it will tell the other robot, and the scheduler will attempt to delay the task at that room until a later time when the occupant has hopefully returned to their office [Coltin and Veloso, 2013]. In general, each robot can be aware of and check the rationale of the plans of other robots.

Finally, we introduce an algorithm based on simulated annealing which finds high quality non-optimal schedules with transfers. While more computationally expensive than the previous heuristics, this algorithm outperforms the best previous solutions to benchmark scheduling problems by incorporating transfers. In addition to the CoBots, the idea of transfers are also applied to transportation and ridesharing problems to reduce fuel costs [Coltin and Veloso, 2014c].

Multiple CoBots continue to autonomously perform tasks in the Gates-Hillman building. The scheduling algorithms, with transfers, allow the CoBots to complete more tasks, more quickly, while prolonging battery life.

4 Human-Centered Planning for Symbiotic Autonomy

Rather than limiting robots' tasks to those that only include actions that robots can perform autonomously, CoBot instead reasons about, plans for, and overcomes its limitations by proactively asking humans in the environment for help [Rosenthal et al., 2010].

We introduced a human-centered planning algorithm that asks for help when CoBot is uncertain of its location or when it is uncertain of which action to take [Rosenthal et al., 2010]. Robots and humans are in a symbiotic relationship, as robots perform service tasks for humans, and humans may need to help the robots. The underlying assumption for the symbiotic robot autonomy is that the requests for help from the robot, e.g., pressing an elevator button, are simple for humans.

The symbiotic autonomy approach leads to adding ask-forhelp action primitives to the robots' plans. The robots autonomously perform such actions. Figure 6 shows a highlevel partial conditional plan for the robot to navigate to a room, where it asks for help from a human to push the elevator buttons.

The conditional plan in Figure 7 is partial in the sense that it does not include what happens if any of the actions fails. We have developed several approaches to handle the additional contingencies of symbiotic autonomy, namely (i) no human helps, e.g., the robot keeps waiting by the elevator; (ii) a human provides the wrong help, e.g., it tells the robot is on an incorrect floor. In the latter situation, as soon as the robot recognizes that it is not at its desired location, it continues its execution by replanning or recognizing that it cannot perform its task for any reason. In both situations, the robot is unable to proceed its task. We have developed two approaches: timeout-based one and a proactive-seek for help one. In the timeout-based approach, the robot waits for help for a predefined amount of time, after which it sends email to its developers using a template that it fills in describing the location and situation where it finds stalled. This step represents an action to ask for help from remote humans.

In the proactive-seek for help approach, we studied who, whether, and where to proactively ask building occupants for help, concretely to use the elevator. We made five hypotheses based on our intuitions about what human state attributes matter in determining where and who to ask for help. The first two hypotheses represent the spatial considerations that CoBot robot should take into account.

• Cost of Help: Asking someone for help who is already at the elevator is preferred over finding someone in an office. A benefit of asking the elevator person is that they are already performing the action themselves and should have little cost to helping the robot
• Distance to Help Location: If someone in an office must be asked because it is unlikely that anyone will be at the help location, there should be a preference for asking someone close to the location to avoid making someone travel too far. Although CoBot is mobile and are capable of traveling to find help, an in-office helper would have to travel back to the help location.

The second three hypotheses represent the considerations the robot should make to increase the likelihood that people are willing to comply and help the robot, because the robot need help performing these actions over a long period of time.

• Interruption: The robot should avoid requesting help from people in offices that are likely to be busy.
• Recency of Last Question and Frequency of Questions: The robot should take into account how recently it asked different helpers to avoid asking too often.
• Availability: If a robot travels with a person to the help location and there is someone already at the location of help, the traveling person may feel that they were asked unnecessarily.

Through user studies, we confirmed all five hypotheses [Rosenthal and Veloso, 2012]. Robots should consider the cost of help, distance to help location, availability, interruptibility, and frequency and recency of questions. However, some participants were willing to help irrespective of the distance to the help location. We use these human state attributes in our human-centered planning algorithm to determine who to ask for help and where to navigate.

When CoBot needs help to use the elevator, it first asks at the elevator hall if anyone is available to help. The people at the elevator hall location have the lowest cost of helping the robot because they are at the elevator anyway. However, if no one helps CoBot, it plans where to seek for help by computing the decision-theoretic expected cost of asking a person in their office based on our user study findings to come to help the robot to get to the desired floor.

The goal of our human-centered proactive replanning algorithm is to simultaneously reduce the time to complete the task while also limiting the in-office help [Rosenthal and Veloso, 2012]. We were able to show that CoBot could complete tasks 4mn faster on average with the proactive replanning algorithm compared to waiting at the elevator only.

The CoBot robots have been deployed for more than 1,000km, in our multi-floor buildings successfully navigating, using their symbiotic autonomy, in particular to move between floors. We present a sample of the results to illustrate the impact of the symbiotic autonomy in the timing of the tasks. The results correspond to a deployment of one robot on the upper four floors of our office building for a two week period. CoBot was deployed for two hours every weekday and made available to the building occupants.

The response to CoBot's deployment was positive: over 100 building occupants registered to use CoBot. Users found creative ways to exploit the robot's capabilities, including, but not limited to sending messages to friends, reminding occupants of meetings, escorting visitors between offices, delivering printouts, inter-office mail, USB sticks, snacks, owed money, and beverages to other building occupants.

We found that occupants scheduled the robot to transport objects between multiple floors of the building more often than they used the multi-floor functionality for other tasks (see Table 2). In particular, the transport task saved the task solicitors time because they did not have to travel between floors themselves. However, even the other scheduled tasks utilized the elevator 40% of the time.

Figure 7 shows how much time CoBot took to execute each task, and how that time was apportioned. A total of

140 tasks were completed during the two-week deployment, which took 9 hours and 13 minutes. Based on these times, we find that task solicitors quickly responded to the robot's request for help at the start and end of tasks. Building occupants (even those that had never scheduled a task) were willing and able to help the robot in and out of the elevator. This finding supports our model of symbiotic autonomy, namely that humans are willing to help a robot complete its tasks so that the robot is available and capable of performing tasks for them as well at another time.

5 Conclusion

The CoBot robots have been successfully deployed in multifloor buildings for over three years. We summarized some of the core contributions. The episodic non-Markovian localization to effectively handle environments whose depth appearance varies over time. Long-term features, e.g., walls, match existing floor-plan maps, while short-term features, e.g., furniture, match previous observations in an episodic non-Markovian manner. The multi-robot task scheduler considers transfers among robots to optimize the travel time performance, and replans to handle online requests and changing conditions. Symbiotic autonomy enables the robot to ask for help from humans at the place needed or proactively search for help from near-by humans. Human-centered planning uses models of humans to generate robots' plans.

Current and future work include learning to improve service performance, including human-preference and environment learning and exploration. We also continue to research on detection of anomalies for safety of use. We are also focused on task instruction and correction through natural language [Mericli et al., 2014], to enable any user to requests new tasks from the robot.

Acknowledgements

We thank Aijun Bai, Steven Klee, Thomas Kollar, Max Korein, Juan Pablo Mendoza, Cetin Mericli, Daniele Nardi, Vittorio Perera, Mehdi Samadi, Yichao Sun, and Rodrigo Ventura for their contributions to the CoBot robots.

This research is partly sponsored by the NSF under awards NSF IIS-1012733 and IIS-1218932, and the ONR under grant number N00014-09-1-1031. The views and conclusions contained herein are those of the authors only.