Plan Explanations that Exploit a Cognitive Spatial Model (2021)

Abstract: Ideally, people who navigate together in a complex indoor space share a mental model that facilitates explanation. This paper reports on a robot control system whose cognitive world model is based on spatial affordances that generalize over its perceptual data. Given a target, the control system formulates multiple plans, each with a model-relevant metric, and selects among them. As a result, it can provide readily understandable natural language about the robot’s intentions and confidence, and generate diverse, contrastive explanations that reference the acquired spatial model. Empirical results in large, complex environments demonstrate the robot’s ability to provide human-friendly explanations in natural language.

## introduction inspired by recent recommendations for spoken language interaction with robots @xcite , this paper introduces why, an approach to communicate a robot's planning rationales, intentions, and confidence in human-friendly spatial language. our thesis is that a plan based on spatial representations acquired from travel experience can ground its objectives and support explainable path planning. the principal results of this paper are empirical demonstrations of why's ability to explain and contrast plans in readily-understandable natural language. given sensor data and a metric map (e.g., a floor plan), the task of our autonomous robot navigator is to travel to target locations in a large, complex, human-centric, indoor space (henceforward, world). the robot's control system integrates acquired spatial knowledge into a cognitively-based architecture that combines planning with reactivity, heuristics, and situational reasoning. given a target, the control system creates a plan, a sequence of intermediate locations (waypoints) to reach it. this plan is expected to balance multiple objectives, combine continuous and discrete spatial representations, and encourage a human's trust. traditional navigation planners use a cost graph (also known as a costmap) where each node is a point in unobstructed space and each edge connects a pair of nodes with a weight for the cost to move between them. a popular cost graph is based on an occupancy grid, uniform square cells superimposed on a two-dimensional metric map. each edge in the graph represents two adjacent unobstructed cells, labeled with the euclidean distance between their centers. in a fine-grained grid, however, optimal planners (e.g., a* @xcite )) hug obstacles so tightly that their plans require tight maneuvers to reach some waypoints and may fail as actuator and sensor errors accumulate near them. to bias plans toward its particular objective (a spatial representation or commonsense rationale), a planner modifies the weights in its own copy of the occupancy-grid graph. the fixed underlying graph structure allows our approach to evaluate a plan within any such modified graph. voting then selects the plan that best satisfies all the objectives. this approach facilitates contrastive natural-language explanations of the chosen plan with respect to each objective. the control system reports on its beliefs, intentions, and confidence with spatial language. for example, "although there may be another way that is somewhat shorter, i think my way is a lot better at going through open areas." the next sections provide related work and describe the acquired spatial model. subsequent sections cover the modified graphs, vote-based planning, and how why explains plans. the last sections describe empirical results and future work. ## related work a spatial representation of its world is essential to a robot control system that navigates efficiently and explains its behavior clearly. grounded communication between a robot and a person, however, requires a shared spatial representation. this section first describes work on human cognitive maps that inspired our control system's spatial model. it then details approaches that describe and explain the robot's behavior. a cognitive map is a compact, mental spatial representation of a world, built by a person as she moves through that world @xcite . to reduce her cognitive load, a person reasons from a cognitive map that incorporates landmarks, route knowledge, and survey knowledge @xcite . landmarks represent locations in the map, routes represent lines that connect them, and survey knowledge captures spatial relations. although it has been suggested that cognitive maps use metric distances and angles @xcite , more recent work indicates that cognitive maps have a nonmetric, qualitative topological structure @xcite . other recent work suggests that people use a cognitive graph with labeled metric information that captures connectivity and patterns @xcite . an affordance is a characteristic of the world that enables the execution of some action @xcite . affordance-based theories of spatial cognition posit a tight relationship between the specific dynamics of a world and the decisions made by an individual there @xcite . here, a spatial affordance is an abstract representation of the world that facilitates navigation. this paper introduces path planning in cost graphs based on acquired spatial affordances. people generalize structured representations across domains on similar tasks @xcite much the way the spatial model described here generalizes affordances for use in different worlds. a control system can learn and use a cognitive map of its world for robot navigation. for example, the spatial semantic hierarchy (ssh) modeled a cognitive map with hierarchical metric and topological representations @xcite . although ssh's cognitive map bears some similarity to the one used here, it did not explain plans. other approaches used semantics to create a meaningfullylabeled metric map @xcite . while these maps provide a qualitative context in which to ground a controller's language, they do not necessarily align with human cognitive maps. moreover, control systems often use semantic maps for communication but another representation for reasoning and decision-making. instead, this paper shows how a single, affordance-based representation supports all of those processes. indoors, an autonomous robot may interact with people as it navigates to its target. a human collaborator is more likely to accept, trust, and understand a robot that can explain its behavior @xcite . rather than describe an event or summarize its causes, an explanation compares counterfactual cases, includes causes selectively, and recognizes people as social beings with beliefs and intentions @xcite . a contrastive explanation compares the reason for a decision to another plausible rationale @xcite . human subjects generally prefer such explanations that focus on the difference between the robot's planned route and their own (e.g., "my route is shorter, but overlaps more and produces less reward") @xcite . detailed technical logs of a robot's experience were originally available only to trained researchers @xcite . recent work, however, has generated natural language descriptions of a robot's travelled path from them. these focus on abstraction, specificity, and locality @xcite or on sentence correctness, completeness, and conciseness @xcite . all, however, required a labeled dataset or a semantic map. other recent work partitions a plan into actions and uses language templates to generate descriptions of each action in the context of a collaborating robot team @xcite . why focuses on explanations for the reasons behind the robot's decisions rather than descriptions of the robot's behavior. to produce explanations, others have selected potentially suboptimal plans @xcite or readily understandable behaviors @xcite , or relied on classical planning @xcite @xcite or on logic @xcite . none of that work, however, explains in natural language. the approach closest to the one presented here provides contrastive explanations for multi-objective path planning in natural language as a markov decision process @xcite , but considers fewer objectives, requires a hand-labeled map, and has been evaluated only in much smaller worlds. ## spatial affordances the context of this work is semaforr, a cognitively-based control system for autonomous indoor navigation @xcite regions with doors and exits korpan, 2019). at decision point @xmath0, y, θ, v , semaforr records the robot's location (x, y), its orientation θ, and its view v , the data from its onboard range finder. after each target, semaforr identifies spatial affordances for its acquired model of freespace, the unobstructed areas in a world. the model can be used alone or with a metric map. at decision point d, semaforr learns a region, a circle in freespace with center at (x, y) and radius equal to the minimum distance reported by v . accumulated contradictory or overlapping regions are resolved after each target. an exit represents access to freespace, a point where the robot's path once crossed the region's perimeter. a door is an arc on a region's perimeter, a continuous generalization of finitely many, relatively close exits between its endpoints. figure 1(a) shows acquired regions with exits and doors (drawn for clarity as secants to their respective arcs). although regions approximate what appear to be rooms in the figure, they record only freespace, not walls. a trail is a refined version of the robot's path toward its target. the algorithm that creates trails heuristically smooths the robot's paths and eliminates digressions. the remaining (usually far fewer) decision points are trail markers. as in figure 1 (b), the sequence of line segments defined by consecutive trail markers is typically more direct than the original path, but rarely optimal. a conveyor is a freespace cell in a 2 × 2m grid supera hallway represents well-travelled routes in some angular direction (vertical, horizontal, major diagonal, or minor diagonal). a hallway generalizes line segments between consecutive decision points to find relatively straight, narrow, continuous freespace with both length and width. figure 1(d ) shows some acquired minor-diagonal hallways. ## modified cost graphs planning for navigation requires a graphical representation of the world's freespace. to produces an optimal plan, a* searches a cost graph g based on an occupancy grid with edge weights for euclidean distance. semaforr constructs a set of graphs; each begins with g but modifies its edge weights to align with a particular objective. this biases search toward that objective but still considers plan length. in practice, an occupancy grid should be sufficiently fine to represent obstacles accurately. four planners exploit a particular kind of spatial affordance with changes to edge weights. (values based on preliminary testing bias plans to pursue but not overemphasize affordances.) regionp's cost graph modifies each edge's weight w based on the location of its endpoints. if both lie in the same region, w goes unchanged; if neither lies in a region w becomes 10w. otherwise, for the one endpoint v not in a region, w becomes 1.5w if v is within 0.5m of a door and an exit, 1.75w if v is within 0.5m of a door or an exit, and otherwise 2w. this biases plans to pass through regions because it increases edge costs outside them. hallwayp and trailp modify their weights similarly, with respective conditions "lie in one hallway" and "lie within 0.5m of a trail marker." if both endpoints of an edge meet the condition, w goes unchanged; if neither does, w becomes 10w. otherwise, when just one endpoint meets the condition, w becomes 1.5w. to bias plans toward high-count conveyors, conveyp considers the counters c 1 and c 2 for the cells where the endpoints of an edge with weight w lies. if both are non-zero, w becomes w + 2/(c 1 + c 2 ); otherwise, w becomes 10w. because semaforr's spatial model focuses on freespace, these modified cost graphs allow a robot control system to encourage travel there but also incorporate the metric cost graph where the model lacks knowledge. the region-based cost graph, for example, imposes relatively lower costs only for doors and exits that the robot has successfully exploited earlier, and thus prioritizes them. because weights only increase, euclidean distance remains an admissible heuristic for a*, that is, it never overestimates the actual cost to the target's location. ## voting among planners to choose paths, people use many different objectives that reflect their motivation @xcite . a cognitively-based robot navigator should also incorporate and balance a variety of path-selection heuristics. semaforr's planners can be used together because they originate from the same cost graph. this section explains algorithm 1, pseudocode for how voting balances the planners' objectives to select a plan. semaforr constructs multiple plans that optimize a single objective and then uses voting to select the plan that maximally satisfies the most objectives. first, each planner j constructs an op-algorithm 1: voting-based planning input: planners j, spatial model m , basic cost graph g for each planner @xmath1, find optimal plan p j in g j for each planner @xmath2 for each plan p i do score i ← j @xmath3. this guarantees that each submitted plan is optimal for at least one objective. next, each planner's objective is used to evaluate every plan. all the cost graphs have the same nodes and edges, so to evaluate planner i's plan p i from the perspective of planner j, semaforr simply sums the edge weights in g j for the sequence of edges specified by p i . the resultant scores c ij are then normalized in [0, 10] for each j. semaforr seeks to minimize its objectives. thus a c ij value near 0 indicates that plan p i closely conforms to objective j, while a score near 10 indicates that plan p i conflicts with objective j. voting selects the plan with the lowest total score across all objectives and breaks ties at random. ## contrastive explanations semaforr uses why to explain its long-range perspective in natural language. why exploits differences among planners' objectives to produce clear, concise, contrastive explanations for a plan quickly. why assumes that the robot's human companion seeks a shortest-length plan, and compares that to semaforr's plan. although we assume here that a goal-directed human navigator would seek to minimize travel distance, another objective, including those in throughout this section, n represents a function that translates its argument (a planner or a metric value) into natural language. given a real-valued metric m for some aspect (e.g., confidence or enthusiasm) of the decision process, m(m) bins m's value into an ordered partition of m's range and n (m(m)) translates that bin to a natural language phrase. for example, m could measure the desire to select one plan over the others, and the value partition could distinguish a strong preference for that plan from a weak one. thus, if @xmath4, +∞) were partitioned as {(0, 5), [5, +∞)}, n (@xmath5." this allows why to hedge in its responses, much the way people explain their reasoning when they are uncertain @xcite . ## empirical evaluation semaforr with why is evaluated on three challenging real worlds: m5, h10, and g5. m5 is the fifth floor of new york's museum of modern art. it is 54 × 62m and has 1585m 2 freespace. h10 is the 89 × 58m tenth floor of an academic building with 2627m 2 of freespace and 75 rooms. g5 is the 110 × 70m fifth floor of a renovated manhattan building. g5 has about 4021m 2 of freespace, 180 rooms, and many intersecting hallways. it is known for its ability to perplex human navigators, despite color-coded walls and art introduced as landmarks. all testing was in simulation with ros, the stateof-the-art robot operating system @xcite . mengeros manages the simulation and deliberately introduces error into both the sensor data and action execution @xcite . to evaluate why we randomly sampled 5 sequences of 40 targets in each world's freespace. ## discussion to capture useful spatial affordances for its world model, semaforr generalizes over its percepts, the 660 distances to the nearest obstacle that its range finder reports 15 times per second. each of semaforr's planners generates paths in a graph biased by edge weights that represent that planner's objective but share an underlying structure that facilitates plan comparison. voting guarantees that any selected plan will be optimal with respect to at least one objective, and makes it likely that the plan will also perform well with respect to the others. this also facilitates contrastive explanations in natural spatial language for the robot's planning objectives, alternative paths, and confidence. how a robot control system represents knowledge is integral to natural communication between robots and people, especially in a spatial context. misunderstandings between a robot and a human often arise from a discrepancy between their spatial mental models. this prompts questions about the robot's underlying decision-making and reasoning mechanisms. why's explanations rely on semaforr's cognitive underpinnings. language about the spatial model is readily understood because semaforr interprets its percepts much the way people do. semaforr's freespace affordances were inspired by sketches after human subjects had actively explored complex virtual worlds @xcite . the planners' objectives are also analogous to processes empirically identified in people @xcite . the results here demonstrate that natural language communication with robots benefits substantially when a robot's control system and a human have similar cognitively-based spatial representations. why's templates flexibly and quickly produce many different explanations in natural language. the templates focus language generation on se-maforr's computational rationale rather than on linguistic structure and grammar. they also facilitate the introduction of new planners without the need to retrain a language generator for a new planning objective. for example, an objective that relied on landmarks could modify the cost graph to reduce costs near them, so that why might explain "i think my way is a lot better at following landmarks." although why assumes the human's objective is the shortest path, it can easily substitute any objective representable in a cost graph with an admissible heuristic. semaforr could also incorporate a planning objective learned from external demonstration (e.g., inverse reinforcement learning) if that objective were representable as increments to the cost graph's weights. whenever semaforr selects fastp's plan here, it assumes that it shares the human's objective. any questions about the robot's plan necessarily challenge that assumption. presumably, the person asks because they do not recognize their objective there. why responds by agreement that the person's plan is the correct way to go (e.g., "actually, i agree that we should take the shortest route."), even though the question should not have arisen. another way to address this would be to offer an alternative plan when fastp is selected. our current work examines how well human subjects understand and feel comfortable with why. although semaforr's parameters for intervals (e.g., in future work could extend why for dialogue (e.g., to clarify confusion or guide navigation @xcite ). this could incorporate natural language generation with deep learning and facilitate queries to the person. why presumes that questions arise from a difference between the human's and the robot's objectives, but they could also stem from a violation of the shared target assumption. a broader system for human-robot collaboration would seek the cause of such a mismatch, use plan explanations to resolve it, and then allow the robot to adjust its responses based on feedback from its human partner. for example, given a plan p from a person or an unspecified heuristic planner, why could use the individual objectives in its repertoire to tease apart and then characterize how p weighted its objectives (e.g., "so distance is more important than travel time?"). meanwhile, semaforr's cognitively-based spatial model supports important path planning objectives and human-friendly explanations of its behavior, intentions, and confidence. empirical results in three large, complex, realistic worlds show that our approach produces diverse, understandable contrastive explanations in natural language.