Séverin Lemaignan
email: severin.lemaignan@brl.ac.uk

Yoan Sallami

Christopher Wallbridge

Aurélie Clodic

Tony Belpaeme

Rachid Alami

UNDERWORLDS: Cascading Situation Assessment for Robots

We introduce UNDERWORLDS, a novel lightweight framework for cascading spatio-temporal situation assessment in robotics. UNDERWORLDS allows programmers to represent the robot's environment as real-time distributed data structures, containing both scene graphs (for representation of 3D geometries) and timelines (for representation of temporal events). UNDERWORLDS supports cascading representations: the environment is viewed as a set of worlds that can each have different spatial and temporal granularities, and may inherit from each other. UNDERWORLDS also provides a set of highlevel client libraries and tools to introspect and manipulate the environment models.

This article presents the design and architecture of this open-source tool, and explores some applications, along with examples of use.

I. INTRODUCTION

UNDERWORLDS is a distributed and lightweight opensource framework 1 that enables robot programmers to build and refine spatial and temporal models of the environment surrounding a robot in real-time. UNDERWORLDS makes it possible to share these world models amongst the software components running on the robot. Additionally, UNDER-WORLDS enables users to represent and manipulate multiple alternatives to the current, perceived world model in a distributed manner. For instance, the world with some objects filtered out; the world 'viewed' from the perspective of another agent; a hypothetical world resulting from the simulated application of a plan, etc.

A. Distributed Situation Assessment

Anchoring perceptions in a symbolic model suitable for decision-making requires perception abilities and their symbolic interpretation. We call physical situation assessment the cognitive skill that a robot exhibits when it represents and assesses the nature and content of its surroundings and monitors its evolution.

Numerous approaches exist, like amodal (in the sense of modality-independent) proxies [START_REF] Jacobsson | Crossmodal content binding in information-processing architectures[END_REF], grounded amodal representations [START_REF] Mavridis | Grounded situation models for robots: Where words and percepts meet[END_REF], semantic maps [START_REF] Nüchter | Towards semantic maps for mobile robots[END_REF], [START_REF] Galindo | Robot task planning using semantic maps[END_REF], [START_REF] Blodow | Autonomous semantic mapping for robots performing everyday manipulation tasks in kitchen environments[END_REF] or affordancebased planning and object classification [START_REF] Lörken | Grounding planning operators by affordances[END_REF], [START_REF] Varadarajan | Ontological knowledge management framework for grasping and manipulation[END_REF].

UNDERWORLDS is specifically inspired by geometric and temporal reasoners like SPARK (SPAtial Reasoning & Knowledge) [START_REF] Sisbot | Situation assessment for humanrobot interactive object manipulation[END_REF] or TOASTER (Tracking Of Agents and Spatio-TEmporal Reasoning) [START_REF] Milliez | A framework for endowing an interactive robot with reasoning capabilities about perspective-taking and belief management[END_REF]. SPARK acts as a situation assessment reasoner that generates symbolic knowledge from the geometry of the environment with respect to relations between objects, robots and humans. It also takes into account the different perspective that each agent has on the environment. SPARK embeds a modality-independent geometric model of the environment that serves both as basis for the fusion of the perception modalities and as bridge with the symbolic layer [START_REF] Lemaignan | Artificial cognition for social human-robot interaction: An implementation[END_REF]. This geometric model is built from 3D CAD models of the objects, furniture and robots, and full body, rigged models of humans. It is updated at run-time by the robot's sensors. Likewise, UNDERWORLDS embeds a grounded amodal model of the environment, updated online from the robot's sensors (sensor fusion).

However, SPARK is a monolithic module that does not support sharing its internal 3D model with other external components. In contrast, UNDERWORLDS focuses on offering a shared and distributed representation of the environment within the robot's software architecture. This also distinguishes UNDERWORLDS from complex cognitive toolkits like KnowRob (as found in OpenEASE [START_REF] Beetz | Open-EASE -a knowledge processing service for robots and robotics/ai researchers[END_REF]). While these tools maintain a spatio-temporal model of the world, this model is internal and not meant to be made widely accessible to other external processes. UNDERWORLDS focuses instead on reusability and sharing of distributed spatio-temporal models. As such, UNDERWORLDS can be seen as a middleware for spatio-temporal world models and, contrary to KnowRob, it does not provide any intrinsic high-level processing or reasoning capability. Such reasoning skills are implemented in loosely-coupled clients (see Section III hereafter).

Work on distributed scene graphs [START_REF] Naef | The blue-c distributed scene graph[END_REF] has been previously applied to robotics to provide a shared 3D representation of the robot's environment (for instance, the Robot Scene Graph [START_REF] Blumenthal | A scene graph based shared 3d world model for robotic applications[END_REF] or the Deep State Representation proposed in [START_REF] Bustos | A unified internal representation of the outer world for social robotics[END_REF]). UNDERWORLDS offers a similar distribution mechanism for 3D scene graphs and extends it to temporal representations. Besides, UNDERWORLDS further extends this line of work by providing the ability to create, manipulate and share multiple alternative worlds. As an example, these could correspond to filtered or hypothetical views on the initial, perceived model of the environment.

B. Representing Alternative States of the World

The components which make use of spatial and temporal models of the environment are usually found in the intermediate layers of robotic architectures, between the lowlevel perceptual layers, and the high-level decisional layers. They include modules like geometric reasoners (that compute spatial and topological relations between objects), motion planners or action recognition modules.

These components exhibit different needs in terms of representation, like different nominal spatial and/or temporal resolutions. For instance, a 3D motion planner would typically use coarse 3D models of surrounding objects to lower the computational load while planning, while a module assessing the visibility of objects might need high-resolution models for accurate 3D visibility testing. This requirement of multiple task-specific representations has been framed as the need for deep representations by Beetz [START_REF] Beetz | Towards performing everyday manipulation activities[END_REF].

Traditional robotic middlewares, like ROS, are not particularly well suited to deal with these different needs: full geometric data can be represented, but is not firstclass citizen: a basic task like displaying a 3D mesh at an arbitrary position is not particularly easy to perform with ROS, requiring the combination of static Collada meshes, a URDF kinematic description, TF broadcasters, and a 3D visualisation tool like RViz. Critically, simultaneously representing and reasoning on alternative states of the environment is not directly feasible.

Representing alternative states is however often highly desirable. For instance, software components manipulating environment models typically perform better if the models are physically consistent. However, low-level perception inaccuracies often introduce hard-to-avoid physical inconsistencies (like detected objects floating in the air, or wrongly inset into other objects). Therefore, a post-process stage (for instance, using a physics simulation engine) is needed to move the objects seen by the robot into physicallycorrect positions. Implemented with a classical approach (for instance, using ROS TF frames), we would represent an object book with two frames: the original frame (e.g.,book frame raw) and a second one computed by the physics engine (e.g.,book frame corrected). Such an approach leads to the robot's 3D model being cluttered with multiple frames and does not scale well.

Another example pertains to geometric task planning: a geometric task planner typically needs to reason over hypothetical future states of the environment ("What happens if I move this glass onto that pile of books?"). The planner generates many possible future states, which in turn might require further processing (for instance, running a physics simulation). Such a tool would benefit a flexible representation system, where models are derived from each other, with partial modifications and different timescales.

A third example relates to human-robot interaction scenarios where perspective taking is important (a prototypical example being the game 'I spy with my little eye', as implemented in [START_REF] Ros | Which one? grounding the referent based on efficient human-robot interaction[END_REF]). Perspective taking is a cognitive skill that relies on the ability for an agent to take someone else's point of view to estimate what they see from their perspectives. Perspective taking has previously been implemented in robotics by temporarily placing virtual cameras at eye locations for each of the humans tracked by the robot [START_REF] Ros | Solving ambiguities with perspective taking[END_REF]. While acceptable for simple cases, such an approach does not maintain truly independent spatio-temporal models of the environment for each agent, and in particular, it does not permit the representation of proper false-belief situations. On the contrary, separate, independent world models as implemented by UNDERWORLDS effectively support such a skill, which is an important precursor to research and implement human's mind modelling (i.e., a theory of mind) [START_REF] Lemaignan | Mutual modelling in robotics: Inspirations for the next steps[END_REF].

Lastly, geometric pre-supposition accommodation makes another interesting case for alternative worlds representation. Pre-supposition accommodation originally comes from linguistics, where it describes the mechanism by which context is adjusted [...] to accept [...] a sentence that imposes certain requirements on the context in which it is processed [START_REF] Fintel | What is presupposition accommodation, again?[END_REF]. In the context of spatio-temporal representations, we call presupposition accommodation the ability of an agent to adjust its model so that it matches some contextual constraint. For instance, if A tells B to "catch the red balloon behind you", B might create a representation of an imaginary red balloon, placed behind her, even without actually observing the balloon: B accommodates the pre-supposition of a red balloon being present behind herself. Endowing robots with this capability has been touched upon by Mavridis et al. within their multi-modal Grounded Situation Model [START_REF] Mavridis | Grounded situation models for robots: Where words and percepts meet[END_REF]. However, to the best of our knowledge, a general framework which would enable robots to accommodate spatial and temporal pre-suppositions by deriving imaginary worlds from existing ones has not been proposed so far.

UNDERWORLDS addresses this need and the main contribution of this work is a generic approach to represent and share multiple parallel representations of the world. UNDERWORLDS does so by allowing clients to clone existing worlds, modify them, and re-share them, without the cost of duplicating geometric data (as explained in section II). By organising clients in a network (Figure 1), worlds can be made dependent on each other, resulting in a loosely-coupled modular approach to spatio-temporal world representation that we call cascading situation assessment.

II. DESIGN AND ARCHITECTURE

A. Software architecture Figure 1 depicts a typical UNDERWORLDS topology: a graph (that happens to be an acyclic graph on Figure 1, but does not have to be in the general case) of worlds, with clients connecting the worlds to each others.

1) Clients: Software components implementing accessing UNDERWORLDS worlds are called clients. Clients can both read and write onto the worlds they are connected to, and automatically see updates broadcast by other clients connected to the same world. To ensure data consistency, worlds can have many simultaneous readers, but only one writer at a given time.

UNDERWORLDS provides several standard clients (like a 3D visualisation tool or a physics engine simulator). Clients are however typically written by the end users, depending on the needs of one's specific architecture.

2) Worlds: Worlds are effectively distributed data structures composed of a scene graph representing the 3D ge- ometry of the environment, and a timeline storing temporal events.

While each world is technically independent from all the others, dependencies (and therefore, coupling) arise between worlds from the clients' connections. For instance, filters effectively create a dependency between worlds. On Figure 1, the Physics-based position correction client creates a dependency between the world base (which represents here the result of raw sensor fusion) and the world corrected which would be a physically-consistent copy of base. As a result, an UNDERWORLDS network can also be seen as a dependency graph between worlds (where cyclic dependencies are permissible).

This architecture enables what we call cascading situation assessment: independent software components (the clients) build, refine and share successive models of the environment by a combination of filtering/transformations steps and model branching. A change performed by one client (for instance, a face tracker updates the pose of the human head) may thereby cascade to each of the downstream, dependent worlds.

3) Scenes: Worlds contain both a geometric model and a temporal model. The geometric model is represented as a scene graph. The scene graph has a unique root node, to which a tree of other nodes is parented.

Nodes in an UNDERWORLDS scene graph have three possible types: objects that represent concrete physical objects (typically with one or several associated 3D meshes); entities that represent abstract entities like reference frames or groups of objects; perspectives that represent viewpoints of the scene (like cameras or human gaze).

Every node has a unique ID, a parent, a 3D transformation relative to the parent and an optional name. Object nodes optionally store as well pointers to their associated meshes. Importantly, mesh data (or other geometric datasets like point clouds) are not stored within the nodes themselves. UNDERWORLDS represents geometric data as immutable data, identified by their hash value (preventing de facto data duplication). Nodes only store the hash corresponding to the desired geometric data, and the actual data is pulled from the server by the clients whenever they actually need it (for rendering for instance).

4) Timelines: Complementing the spatial representation encapsulated in the scene graph, each world also stores the world's timeline. This data structure is shared and synchronised amongst the clients in the same way as the scene graph. Clients can record and query both events (durationless states) and situations in the timeline, i.e., states with a start time and a (possibly open-ended) end time.

B. Distributed spatio-temporal models

UNDERWORLDS is not a monolithic piece of software. Instead, it stands for both a network of interconnected clients which manipulate spatial and temporal models of the robot environment (for instance, a motion planner, a object detection module, a human skeleton tracker, etc.), and for a client library that makes it possible to interface existing software components with the network.

Critically, the network is essentially hidden to the client: from the user perspective, the environment model is manipulated as a local data structure (see Listing 1). Modifications to the model are asynchronously synchronised with a central server (the underworlded daemon) and broadcast to every other client connected to the same world.

As previously mentioned, worlds are composite data structures comprised of a scene graph and a timeline. These data structures are synchronised using Google's gRPC message passing framework2 , ensuring high throughput, reliability and cross-platform/cross-language support. The UN-DERWORLDS API is specifically discussed hereafter, in section III-A.

UNDERWORLDS is meant to broadcast complex environment representations (typically including large geometric datasets, like meshes) in real-time. UNDERWORLDS itself does not perform many CPU intensive tasks (CPU intensive processing tasks -sensor fusion, physics simulation, etc.are performed by the clients themselves) and as such, the performance bottleneck is essentially the network's data throughput. In that regard, one of the simple yet critical optimisations performed by UNDERWORLDS is automatic caching of mesh data. Mesh data are not transmitted when nodes are updated; only a hash value of the mesh data. The client can then request the full data whenever it is actually needed.

C. Time and space complexity analysis

UNDERWORLDS is fundamentally about distributing two datastructures: a scene graph (with nodes representing spatial entities) and a timeline (where events are stored as a flat list). Typical time and space complexities arise from these datastructures. In typical usage scenarios (where the number of nodes or events remain under a few hundred relatively small), the computational load to manipulate these datastructures is however dominated by the actual processings performed by the clients with the data. In the current implementation, scene graphs and timelines are stored in-memory. Were they required, serialization and persistent storage are not anticipated to be difficult to implement.

More interesting is the time complexity of distributing changes across an UNDERWORLDS network. With n the number of worlds and m the number of clients in an UNDERWORLDS network, the worst-case (when every world is a parameter of every client) time complexity of creating or updating a node and propagating the change across the network is O(n × m) (this effectively corresponds to the UNDERWORLDS server performing n × m requests to notify clients of the update). The space complexity is the same (as clients own a full copy of the worlds they monitor), except for mesh data whose space and time complexities are O(1) (only the server stores the mesh data).

In the common case of one client performing a full update of a single world (with p nodes) at each time step, the complexity of propagating these changes across the network would be O(p × m). Figure 2 shows measured propagation time for one change across up to 20 cascading worlds.

III. API & CLIENTS

A. API

As mentioned, UNDERWORLDS uses Google's gRPC as message passing protocol. The protocol is explicitly defined (using the protocol buffers 3 interface definition language), and bindings to various languages and platforms can be automatically generated from the protocol definition file (as of Jan 2018, gRPC can generate bindings for C, C++, C#, Node.js, PHP, Ruby, Python, Go and Java, on Windows, Mac, Linux and Android). The cross-platform/cross-language support of gRPC is especially welcome in the academic context, as it offers ease and flexibility to plug a variety of preexisting components into an UNDERWORLDS network. 3 https://developers.google.com/protocol-buffers/ However, the gRPC message passing layer is low-level with respect to the typical use of UNDERWORLDS (manipulation of asynchronous, distributed spatio-temporal models of the robot environment). In particular, the asynchronous fetching (and conversely, remote updating) of nodes and time-related objects is typically hidden from the user, and managed instead by the UNDERWORLDS client library.

UNDERWORLDS currently offers such a high-level client library for Python only (a C++ library is under development). Listing 1 gives a complete example of an UNDERWORLDS client performing simple filtering: the client continuously listens for changes in an input world, removes some objects (in this case, items whose volume is below a threshold), and forwards all other changes to an output world, effectively making the output world a copy of the input world with all smaller objects removed. Listing 1: Example of a simple yet complete UNDERWORLDS filter, written in Python: the client connects to the UNDER-WORLDS network, blocks until the world world1 changes, and only propagate nodes that match the condition to the world world2.

B. Standard Clients

The UNDERWORLDS package provides several standard clients to perform common tasks on UNDERWORLDS networks. Fig. 3. Screenshot of the uwds view 3D visualisation and manipulation client. In this particular example, the 3D meshes have been pre-loaded using uwds load. Their positions are then updated at run-time using the robot's sensors and proprioception (joint state).

1) 3D Visualisation and manipulation: Interestingly, while UNDERWORLDS deals with 3D geometries and scenes, it does represent 3D entities purely as data structures; no visual representation is involved (and as such, the UNDER-WORLDS server and core libraries do not depend on any graphics library like OpenGL). However, for all practical purposes, the ability to visualise the content of a scene is desirable. UNDERWORLDS provides a standard client, uwds view, that performs real-time 3D rendering of worlds, using OpenGL (Figure 3). This tool also supports basic object manipulations (translations, rotations), that are broadcast to the other UNDER-WORLDS clients connected to the same world.

Assets loading: Often, objects manipulated by the robot have known meshes with corresponding CAD models that can be conveniently pre-loaded. In these cases, UNDER-WORLDS provides a tool, uwds load, that loads a mesh into a UNDERWORLDS network (and optionally, creates a node) from a large range of 3D formats (including Collada, FBX, OBJ, Blender) 4 .

2) Physics simulation: When perception modules provide objects localisation, the physical consistency of the locations is not typically enforced. For instance, objects that are supposed to lay on a table might be slightly above (or inset into) the table; or when dropping an item into a box, the robot can not update the location of the item anymore as it becomes occluded.

These issues can be alleviated by relying on a physics simulation to stabilise the position of objects: natural physics (including gravity) are simulated for a short amount of time (up to one second) ahead of time, and the objects' positions are updated accordingly. To this end, UNDERWORLDS pro- CLients are connected to the worlds either as readers or providers of data. UNDERWORLDS introspection features make it possible to also visualise when clients were last active. vide a standard filter, the physics filter, based on the Bullet RT physics simulation and the pybullet5 library. It generates an output world that mirrors its input world after a specific duration of physics simulation, the physical properties of objects (including mass, friction, inertia) being provided from standard URDF descriptions.

3) Introspection and debugging: UNDERWORLDS provides a range of tools to inspect a running network. Graphical tools (uwds explorer and uwds timeline, see Figure 4) provide a user-friendly overview of the system's graph with the connections between the clients and the worlds, as well as their activity.

Specialised command-line tools are also available to list the worlds and their content (uwds ls) at run-time, or to display detailed information for a specific node (uwds show).

4) Interface with ROS: UNDERWORLDS is meant to integrate as easily as possible into existing robot architectures, and interfaces transparently with ROS' TF frame system through the uwds tf client.

The uwds tf client continuously monitors the ROS TF tree, and mirrors TF frames as nodes in the desired UN-DERWORLDS world. A node is first created if none matches a given TF frame, and its transformation is subsequently updated, mirroring the TF frame. A regular expression can be provided to only mirror a subset of the TF tree into UNDERWORLDS.

Currently, the process is unidirectional: the uwds tf client performs TF to UNDERWORLDS updates, but not the reverse.

C. Spatial Reasoning and Perspective Taking

Spatial reasoning [START_REF] O'keefe | The Spatial Prepositions[END_REF] is a field in its own right, and has been used for natural language processing for applications such as direction recognition [START_REF] Kollar | Toward understanding natural language directions[END_REF], [START_REF] Matuszek | Following directions using statistical machine translation[END_REF] or language grounding [START_REF] Tellex | Natural language and spatial reasoning[END_REF]. Other examples in human-robot interaction include Ros et al. [START_REF] Ros | Solving ambiguities with perspective taking[END_REF], [START_REF] Ros | Which one? grounding the referent based on efficient human-robot interaction[END_REF] which has recently been integrated into a full architecture for autonomous human-robot interaction [START_REF] Lemaignan | Artificial cognition for social human-robot interaction: An implementation[END_REF].

UNDERWORLDS provides an exemplary client (spatial relations) to compute both allo-centric (independent of the viewpoint like isIn or isOn) and ego-centric (i.e., viewer-dependent, like inFrontOf or leftOf) spatial relations between objects. Other libraries, like QSRLib [START_REF] Gatsoulis | Qsrlib: a software library for online acquisition of qualitative spatial relations from video[END_REF], that implement computational models of Qualitative Spatial Relations, could be trivially combined with UNDERWORLDS to provide more advanced geometric analysis. Future developments will also include the results of the more basic research on spatio-temporal reasoning for robotics, led by de Leng and Heintz [START_REF] De Leng | Qualitative spatio-temporal stream reasoning with unobservable intertemporal spatial relations using landmarks[END_REF].

UNDERWORLDS also implements an efficient algorithm to assess object visibility from a specific viewpoint (i.e., from a given perspective node). The algorithm (color picking) enables fast (single pass) computation of the visibility of every object in the scene, while providing control regarding how many pixels should be actually visible for the object to be considered globally visible. The commandline tool uwds visibility returns the list of visible objects from the point of view of each camera in a given world, and UNDERWORLDS also provides the helper class VisibilityMonitor to programmatically access visibility information.

When integrated into a filter node, visibility computation allows easy creation of new worlds representing the estimated perspectives of the different agents.

IV. APPLICATION EXAMPLE: PERSPECTIVE-AWARE JOINT ACTIONS

UNDERWORLDS is being used within the large European project MuMMER 6 for service robots to compute visibility and knowledge about objects, places and agents within a mall environment.

We present here a simplified scenario, yet representative of situations which are processed in real-time by MuMMER robots: two humans and a robot are looking at a table and have to coordinate joint actions (pick and place). One object on the table (the green box in Figure 5) is only visible to one human and the robot, but hidden to the second human. The robot needs to take into account this fact to generate appropriate and legible joint manipulation actions. Figure 5 illustrates the topology of the UNDERWORLDS network that we use to this end.

A first client, static env provider, provides the environment models and allows to build a first ENV world where static objects, furnitures and walls are present. Then, three worlds cascade through three (independent) clients: robots state monitor augments ENV with the robot state (using underneath the ROS robot state publisher node) and broadcast a new world ENV ROBOTS. objects monitor then recognises and adds the dynamic objects (using ar track alvar 7 ). humans monitor finally detects and 6 http://www.mummer-project.eu continuously updates the humans poses (using [START_REF] Khalidov | Real-time multiple head tracking using texture and colour cues[END_REF]). It broadcasts a world called BASE that contains as a result the static environment, the robots, the dynamic objects and the detected humans.

The world BASE goes through a physics filter client (as explained in section III-B.2) to obtain the STABLE world where all elements are present with physically-consistent locations. This physically-correct world is used by the computation of spatial relations client to compute spatial relations such as onTop, isIn or isAbove (see Section III-C).

The world STABLE is also used by a perspectives filter client to compute the different visual perspectives of each agent (in our case: human 1, human 2 and the robot itself).

In addition to a 3D rendering of the input world from the perspective of the agent, it aggregates the history of what was visible to the agent at a given point in time. As such, it does not only offer a snapshot of the agent visual perspective at the current time but also acts as the visual memory of each agent.

With this network, the robot can easily compute that an object on the table is only seen by the human 1 and not the human 2; additionally, if human 1 moves in a position where the object is not visible anymore to him, the perspective filter will maintain the knowledge that the human had seen it (and keep the last position where it has been seen).

UNDERWORLDS makes it possible to implement such a geometric reasoning pipeline in a fully decoupled way, and each intermediary world can be easily introspected at run-time. This example shows how UNDERWORLDS facilitates the implementation and debugging of complex spatiotemporal reasoning pipelines.

We are currently deploying a similar network in the framework of the European project MuMMER where a Pepper robot handles interactive situations in a large shopping centre in Finland. One of the situation is a guiding task where Pepper help people to find their route by pointing them landmarks and explaining them how to reach a destination. To be effective, this helping behaviour needs to be aware of the visual perspective of the human. UNDERWORLDS facilitates the implementation of such a spatio-temporal reasoning pipeline, where perception and high-level reasoning (including complex, human-aware reasoning) have to be tightly integrated. Because of the decoupling of each of the clients in the network, UNDERWORLDS also practically supports software development spread across multiple partners in different countries, with different expertise.

V. DISCUSSION AND CONCLUSION

A. Relation to existing robotic middleware Like traditional robotic middleware, UNDERWORLDS offers a form of distributed computation based on message passing. However, it distinguishes itself from existing middlewares (including ROS extensions like DyKnow [START_REF] De Leng | DyKnow: A Dynamically Reconfigurable Stream Reasoning Framework as an Extension to the Robot Operating System[END_REF]) in significant ways. Most importantly, UNDERWORLDS purposefully does not offer any general capability to distribute computation and data streams amongst independent components: it focusses specifically on distributing environment models, both spatial (geometric models) and temporal (events and situations). In that sense, UNDERWORLDS really is a distributed datastructure that addresses the specific needs of spatio-temporal modelling, including the modelling of hypothetical, alternative world models, something that traditional middlewares like ROS do not address adequately. Second, and as presented above, UNDERWORLDS offers specific mechanisms for the representation and manipulation of alternative world models that are not directly achievable with traditional tools.

While using standard middleware as underlying transport for UNDERWORLDS would be technically feasible and relatively easy to implement, it does not offer any clear ad-vantage over lighter and dedicated message passing libraries like ZeroMQ or gRPC (the later being the one used by UNDERWORLDS).

B. Future work

As illustrated in section IV, UNDERWORLDS is already deployed and used on the field. Several features are however still under development.

1) Representation capabilities: as presented in section II, the current version of UNDERWORLDS allows to represent objects, abstract entities like groups and perspectives. Fields are also part of the UNDERWORLDS design, but are not yet implemented. Fields are commonly used to represent continuously-valued spatial entities. Fields might or might not be spatially bounded. Examples include the working space of a robot arm (spatially bounded), the field of view of a camera (spatially bounded), proxemics (potentially unbounded). We plan to represent fields in UNDERWORLDS using the memory-efficient octomaps [START_REF] Hornung | Octomap: An efficient probabilistic 3d mapping framework based on octrees[END_REF] or NDT-OM maps [START_REF] Saarinen | 3d normal distributions transform occupancy maps: An efficient representation for mapping in dynamic environments[END_REF]. Similarly to geometric data,these datastructures will not be directly stored with the nodes (nodes will refer to them through handles), but unlike geometric data, they will not be treated as immutable datasets by the server, permitting real-time updates.

Representation of uncertainty: currently node positions are stored as 4 × 4 transformation matrices, relative to the node parent. This representation is efficient, and conveniently matches traditional representation systems (including ROS TF frames or OpenGL transformations). However, the explicit management of uncertainties is instrumental to many robotic applications, and we plan to add full support for position uncertainties to UNDERWORLDS. We plan to add this support by adding a pose covariance matrix to the nodes, and equipping the different UNDERWORLDS helper tools with corresponding support (like covariance ellipses visualisation in uwds view).

2) Implementation and Integration: we plan to continue to improve the integration of UNDERWORLDS into existing software architectures. A short-term goal is to provide excellent C++ support, with a high-level, user-friendly C++ client library. This is critical for a broader adoption of UNDERWORLDS within the robot community. Support for other languages might follow, depending on demands and open-source contributions.

C. Conclusion

We have introduced UNDERWORLDS, a novel framework for shared and composable spatio-temporal representations of a robot's world. The key contributions of our approach are: a composite data structure for environment representation within a robotic software architecture, made of a scene graph and a timeline; a mechanism to efficiently and transparently share this data structure amongst a set of clients (the software modules of the robot); a cascading architecture permitting the explicit of representation of alternative states of the world while maintaining a network of dependencies.

Fig. 1 .

 1 Fig.1. Schema of a possible UNDERWORLDS network: eight clients (userwritten & architecture specific; in blue) are sharing environment models through four independent worlds (made from joint spatial and temporal models). This architecture enables successive and modular refinement of the models (cascading situation assessment), effectively adapted to each client's needs.

Fig. 2 .

 2 Fig. 2. Propagation times of one change (node creation) across n worlds. The test is performed by running n-1 pass-through filters that monitor one world and replicate any changes into the next world. Durations measured over 20 runs, performed on a 8 core machine.

Fig. 4 .

 4 Fig. 4. Screenshot of the network topology introspection tool, with arbitrary examples of worlds (represented as boxes) and clients (ellipses).CLients are connected to the worlds either as readers or providers of data. UNDERWORLDS introspection features make it possible to also visualise when clients were last active.

Fig. 5 .

 5 Fig. 5. Schema of the UNDERWORLDS architecture used in the MuMMER project. Clients read and generate the worlds ENV → ENV ROBOT → . . . → HUMAN * PERSPECTIVE. The last two worlds HUMAN{1,2} PERSPECTIVE represent the immediate visual perspective of each of the humans, as well as their past visual perceptions. As such, they are the visual memories of the humans, that the robot can rely on when making decisions.

http://www.grpc.io/

The underlying import capability is provided by the ASSIMP library. http://assimp.sourceforge.net/

https://pybullet.org/

We have additionally presented a concrete instantiation of a system relying on UNDERWORLDS for its representation needs, and we have sketched future directions of development.

We believe this work can practically support existing robotic architectures with state-of-the-art spatio-temporal representation capabilities. We also hope that this line of research can lead to a better understanding of the representation needs of modern robotic systems, and participate to the emergence of a possible common representation platform for robots, building on previous formalisation efforts like the RSG-DSL domain specific language [30].

ACKNOWLEDGMENT

This work has been supported by the EU H2020 Marie Skłodowska-Curie Actions project DoRoThy (grant 657227), the EU H2020 MuMMER project (grant 688147) and the EU H2020 L2TOR project (grant 688014).


Mathieu Dehouck
email: mathieu.dehouck@inria.fr

Pascal Denis
email: pascal.denis@inria.fr

A Framework for Understanding the Role of Morphology in Universal Dependency Parsing

This paper presents a simple framework for characterizing morphological complexity and how it encodes syntactic information. In particular, we propose a new measure of morphosyntactic complexity in terms of governordependent preferential attachment that explains parsing performance. Through experiments on dependency parsing with data from Universal Dependencies (UD), we show that representations derived from morphological attributes deliver important parsing performance improvements over standard word form embeddings when trained on the same datasets. We also show that the new morphosyntactic complexity measure is predictive of the gains provided by using morphological attributes over plain forms on parsing scores, making it a tool to distinguish languages using morphology as a syntactic marker from others.

Introduction

While word embedding has proven a good solution to reduce data sparsity in parsing [START_REF] Koo | Simple semi-supervised dependency parsing[END_REF], treating word forms as atomic units is at odds with the fact that words have a potentially complex internal structure. Furthermore, it makes parameters estimation difficult for morphologically rich languages (MRL) in which the number of possible forms a word can take can be very large 1 .

Recently, researchers have started to work on morphologically informed word embeddings [START_REF] Cao | A joint model for word embedding and word morphology[END_REF][START_REF] Botha | Compositional morphology for word representations and language modelling[END_REF], aiming at better capturing both lexical, syntactic and morphological information. But encoding lexicon and morphology in the same space makes it difficult to distinguish the role of each in syntactic tasks such 1 A typical English noun has 2 forms while a Finnish one may have more than 30. This shows in data as English lemmas have 1.39 forms on average while Finnish ones have 2.19, as measured on UD data [START_REF] Nivre | Universal dependencies v1: A multilingual treebank collection[END_REF]. as dependency parsing. Furthermore, morphologically rich languages for which we hope to see a real impact from those morphologically aware representations, might not all rely to the same extent on morphology for syntax encoding. Some might benefit mostly from reducing data sparsity while others, for which paradigm richness correlate with freer word order [START_REF] Comrie | Language universals and linguistic typology : syntax and morphology / Bernard Comrie[END_REF], will also benefit from morphological information encoding.

This paper aims at characterizing the role of morphology as a syntax encoding device for various languages. Using simple word representations, we measure the impact of morphological information on dependency parsing and relate it to two measures of language morphological complexity: the basic form per lemma ratio and a new measure (HPE) defined in terms of head attachment preference encoded by its morphological attributes. We show that this new measure is predictive of parsing result differences observed when using different word representations and that it allows one to distinguish amongst morphologically rich languages, those that use morphology for syntactic purpose from those using morphology as a more semantic marker. To the best of our knowledge, this work is the first attempt at systematically measuring the syntactic content of morphology in a multi-lingual environment.

Section 2 presents the representation learning method and the dependency parsing model. It also defines two measures of morphological complexity. Section 3 describes the experimental setting and analyses parsing results in terms of the previously defined morphological complexity measures. Section 4 gives some conclusions and future work perspectives. This section details: (i) our method for learning lexical and morphological representations, (ii) how these can be used for graph-based dependency parsing, and (iii) how to measure morphological complexity. Our representation learning and parsing techniques are purposely very simple in order to let us separate lexical and morphological information and weight the role of morphology in dependency parsing of MRL.

Word Representation

We construct separate vectorial representations for lemmas, forms and morphological attributes, either learned via dimension reduction of their own cooccurrence count matrices or represented as raw one-hot vectors.

Let V be a vocabulary (it can be lemmas or forms or morphological attributes (incl. values for POS, number, case, tense, mood...)) for a given language. Correspondingly, let C be the set of contexts defined over elements of V. That is, lemmas appear in the context of other lemmas, forms in the context of forms, and attributes in the context of attributes. Then, given a corpus annotated with lemmas and morphological information, we can gather the cooccurrence counts in the matrix M ∈ N |V|×|C| , such that M ij is the frequency of lemma (form or morphological attributes) V i appearing in context C j in the corpus. Here, we consider plain sequential contexts (i.e. surrounding bag of "words") of length 1, although we could extend them to more structured contexts [START_REF] Bansal | Tailoring continuous word representations for dependency parsing[END_REF]. Those cooccurrence matrices are then reweighted by unshifted Positive Point-wise Mutual Information (PPMI) and reduced via Singular Value Decomposition (SVD). For more information on word embedding via matrix factorization, please refer to [START_REF] Levy | Improving distributional similarity with lessons learned from word embeddings[END_REF].

Despite its apparent simplicity, this model is as expressive as more popular state of the art embedding techniques. Indeed, Goldberg and [START_REF] Levy | Neural word embedding as implicit matrix factorization[END_REF] have shown that the SkipGram objective with negative sampling of Mikolov's Word2vec (2013) can be framed as the factorization of a shifted PMI weighted cooccurrence matrix.

This matrix reduction procedure gives us vectors for lemmas, forms and morphological attributes, noted R. Note that while a word has only one lemma and one form, it will often realize several morphological attributes. We tackle this issue by simply summing over all the attributes of a word (noted M orph(w)). If we note r w the vectorial representation of word w we have:

r w = a∈M orph(w) R a .
Simple additive models have been shown to be very efficient for compositionally derived embeddings [START_REF] Arora | A Simple but Tough-to-Beat Baseline for Sentence Embeddings[END_REF].

Dependency Parsing

We work with graph-based dependency parsing, which offers very competitive parsing models as recently re-emphasized by [START_REF] Dozat | Stanford's graph-based neural dependency parser at the conll 2017 shared task[END_REF] in the CONLL 2017 shared-task on dependency parsing [START_REF] Daniel Zeman | Conll 2017 shared task: Multilingual parsing from raw text to universal dependencies[END_REF].

Let x = (w 1 , w 2 , ..., w n ) be a sentence, T x be the set of all possible trees over it, ŷ the tree that we predict for x, and Score(•, •) a scoring function over sentence-tree pairs :

ŷ = argmax t∈Tx Score(x, t).
We use edge factorization to make the inference problem tractable. A tree score is thus the sum of its edges scores. We use a simple linear model:

Score(x, t) = e∈t θ • φ(x, e),
where φ(x, e) is a feature vector representing edge e in sentence x, and θ ∈ R m is a parameter vector to be learned.

The vector representation of an edge e ij whose governor is the i-th word w i and dependent is the j-th word w j , is defined by the outer product of their respective representations in context. Let ⊕ note vector concatenation, ⊗ the outer product and w k±1 be the word just before/after w k , then:

v i = w i-1 ⊕ w i ⊕ w i+1 , v j = w j-1 ⊕ w j ⊕ w j+1 and φ(x, e ij ) = vec(v i ⊗ v j ) ∈ R 9d 2 .
Recall that w i of length d

V is a vector from R. We use the averaged Passive-Aggressive online algorithm for structured prediction [START_REF] Crammer | Online passive-aggressive algorithms[END_REF] for learning the model θ. Given a score for each edge, we use Eisner algorithm [START_REF] Eisner | Three new probabilistic models for dependency parsing: An exploration[END_REF] to retrieve the best projective spanning tree. Even though some languages display a fair amount of non-projective edges, on average Eisner algorithm scores higher than Chu-Liu-Edmonds algorithm [START_REF] Chu | On the shortest arborescence of a directed graph[END_REF] in our setting.

Measuring Morpho-Syntactic Complexity

Some languages use morphological cues to encode syntactic information while other encode more semantic information with them. For example, the Case feature (especially core cases) is of prime syntactic importance, for it encodes the type of relation words have with each other. On the contrary, the Possessor feature (in Hungarian for example) is more semantic in nature and need not impact sentence structure. This remark would support different treatment for each language. However, those languages tend to be treated equally in works dealing with MRL.

Form to Lemma Ratio A basic measure of morphological complexity is the form per lemma ratio, we note it F/L. It captures the tendency of words to inflect in a given language. Because some word classes tend not to inflect and not all forms are equally productive, we note F/iL the ratio of form per inflected lemma. Given a language l with a lemma vocabulary V l and a form counting function c : V l → N that returns the number of forms a lemma can take, we have:

F /L(l) = 1 |V l | w∈V l c(w), F /iL(l) = 1 |V l i | w∈V l i c(w), V l i = {w ∈ V l |c(w) > 1}
F/L and F/iL do not measure the informative content of morphology, but simply its productivity. [START_REF] Bentz | A comparison between morphological complexity measures: typological data vs. language corpora[END_REF] compared five different measures of morphological complexity amongst which word entropy and the micro-averaged version of F/L (they call it TTR) and showed that they all have high positive correlation given enough data.

Head POS Entropy In order to compare the morpho-syntactic complexity of different languages, we introduce a new measure called Head Part-of-speech Entropy or HPE. The HPE of a token t represents the amount of information t has about the part-of-speech of its governor. More formally, let P OS(Gov(t)) be the set of partsof-speech that t can depend on, and let π t (p) be the probability of t actually depending on part-ofspeech p, then the HPE is defined as:

HP E(t) = p∈P OS(Gov(t)) -π t (p)log 2 (π t (p)).
This is a measure of a token preferencial attachment to its head. A token with a low HPE tends to attach often to the same part-of-speech, while a token with a high HPE will attach to many different parts-of-speech. Thus a language with a low HPE will tend to encode a lot of syntactic information in the morphology, rather than in word order say.

For example, a noun can attach to another noun like a genitive, or to a verb as a subject or object, or even to an adjective in the case of transitive adjective. French nouns do not inflect for case, thus attachment to another noun or verb can only be infered from words relative positions. On the contrary, Gothic nouns do inflect for case, thus making verb or noun attachment clear directly from the morphological analysis.

We compute the HPE of a language as the averaged HPE of its attributes sets over a given corpus. Likewise, we use the empirical counts as a surrogate for c in F/L and F/iL.

Experiments

In order to test the hypothesis that morphological representations contain syntactic information crucial for dependency parsing of morphologically rich languages, but that this information is not equally distributed across MRL, we run experiments on data from the Universal Dependencies [START_REF] Nivre | Universal dependencies v1: A multilingual treebank collection[END_REF] project.

Data Description

For conciseness, we focused on eleven languages that display varying degrees of morphological complexity and belong to four different language families. Basque (eu) is an isolate and it is an ergative language. English (en), Gothic (got), Danish (da) and Swedish (sv) are Germanic languages, and French (fr) and Romanian (ro) are Romance languages (Indo-European). Finnish (fi), Estonian (et) and Hungarian (hu) are Finno-Ugric languages. Hebrew (he) is a Semitic language. Basic statistics are provided in Table 1.

Experimental Settings

For the experiments we use the train/dev/test data provided by UD 2.0. Basic statistics about the data are reported in the appendix. Lemmas and forms are embedded in 150 dimensions, while Morphological attributes are embedded in 50 dimensions, because they are much less numerous (less than 100). All embeddings are induced on their language respective train set only using a context window of size For each type, we report results using one-hot representation (OH) and results using embeddings (Emb).

directly preceding and following words).

Parsers are trained for 10 iterations using either lemma, form or morphological representations, and we pick the best iteration on the basis of UAS on the development set.

While we used gold lemmas as provided in the corpora, we ran two experiments for morphological attributes, one with gold attributes and one with predicted attributes. Morphological attributes are predicted with a simple multinomial logistic regression per attribute (POS, Tense, Case, Gender...), where we add a special undef value (except for POS) to represent the lack of an attribute (e.g., nouns have no Tense in English). The models predict attribute values for the center word of trigrams represented by feature vectors encoding word prefixes and suffixes of length 1, 2 and 3, word length and capitalization. We used the logistic regression implemented in the Scikit-Learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] library with the default settings. It can output an argmaxed decision or a softmaxed decision, thus we tried both as input to the parser. The argmaxed decision gives a vector of zeros and ones, while the softmaxed decision gives a continuous vector with each each attributes summing to one (the probability assigned to each possible value for Gender like Masculine, Feminine, Neuter and Undef must sum to one). Then those vectors are used unchanged for the one-hot representation or passed through an embedding matrix for the embedding representation.

Results

For clarity, we focus on comparing results using form embeddings and gold morphological representations. They are given in Table 2. Because the analysis carries to the labeled case, we stick to unlabeled scores (UAS) for the analysis. A more complete table is provided in the appendix as well as a complete labeled accuracy score (LAS) table. Morphological complexity measures are also reported.

One-hot gold morphological attributes consistently outerperform form embeddings. This is expected since forms embedding were trained on much fewer data than usually considered necessary. However, improvements are not consistent across languages, ranging from 1.14 point for English to 15.20 points for Finnish. While those differences are not explained by morphological productivity alone (Figure 1a), a measure of preferential attachment gives a good account of them (Figure 1b). Those inconsistencies become even more striking, considering results using predicted attributes. We notice that despite a general drop of performance of 5-12 points, predicted attributes Figure 1: Accuracy differences (y-axis) between parsers using form embeddings and parsers using onehot attributes, with respect to morphological complexity (x-axis). Red dots represent the gold attributes scores and blue squares the predicted attributes scores.

still perform significantly better than form embeddings for those morphologically rich languages that have an HPE lower than 0.65 as depicted on Figure 1b.

Figures 1a and 1b plot the differences in parsing scores. For each language, the red dot corresponds to the score difference between using form embeddings and gold attributes one-hot representations, and the blue square corresponds to the score difference between using the same form embeddings and predicted attributes softmax representations (the complete scores are given in the appendix). Figure 1a plots those differences with regard to the form per inflected lemma ratio (F/iL) and Figure 1b plots those differences with regard to the head POS entropy (HPE).

Both Figures show trends. Score differences seem to increase with F/iL and decrease with HPE. But while the F/iL plot suffers outliers (Hungarian, Estonian and Romanian), the HPE plot shows a clear boundary between languages benefiting fully from morphological information (even predicted) and those benefiting primarily from reducing data sparsity. While Hebrew seems to be an outlier, it might be due to its annotation style, where attached prepositions, articles and possessive markers are treated as independent words rather than morphological inflection as other languages do, thus artificially increasing the parsing accuracy with a lot of trivial dependencies. This shows that indeed, HPE is a good measure of the syntactic informativeness of a language morphology, and that it can help deciding between encoding morphological information or just reducing data sparsity. Furthermore, it seems to be link to the distinction that [START_REF] Kibort | Features: perspective on a key notion in linguistics[END_REF] do between morphosyntax and morphosemantic.

Conclusion

We have contributed a new measure of morphosyntactic complexity (HPE) that helps distinguishing languages that use morphology for syntactic purpose from languages that use morphology to encode more semantic information. We showed that this measure correlates much more with differences in parsing results using morphological representations than the simple form per lemma ratio. It could thus be used to help designing language specific word representations.

It is worth mentioning that we focused here on dependent marked head selection. It would be interesting to have a similar measure for headmarking situations with dependencies marked on the governor. We leave it for future work.

Acknowledgement

This work was supported by ANR Grant GRASP No. ANR-16-CE33-0011-01 and Grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020. We also thank the reviewers for their valuable feedback.

Appendix A: Supplementary Tables

Table 3 reports results for the predicted attributes experiment. The POS and averaged attributes prediction accuracies are given. Are also reported, scores for the four representation regimes of predicted attributes. Predictions can be either probability distributions (Soft) or argmax (Hard) and either used as such (OH) or passed through an embedding (Emb). Table 4 reports all the labeled accuracy scores for parsers using either gold lemmas, forms or gold attributes, either as one-hot vectors or as dense embeddings. Table 5 reports results for the predicted attributes experiment. Are also reported, scores for the four representation regimes of predicted attributes as in table 4. Predictions can be either probability distributions (Soft) or argmax (Hard) and either used as such (OH) or passed through an embedding (Emb).

Table 1 :

 1 Basic datasets statistics. The first line gives the number of train sentences for each language. The second and third give the number of part-of-speech and of morphological attribute values for each language. The fourth and fifth lines reports forms per lemma ratios. Last line gives the HPE.

	1 (i.e. the

Table 2 :

 2

UAS scores for parsers using lemmas (Lem), word forms (Form) or morphological attributes (Morph) representations as features.

21 72.72

  .24 84.49 86.09 86.14 90.60 90.44 90.93 88.43 90.64 89.23 Attributes 98.02 97.74 96.20 97.56 97.09 97.60 96.00 97.84 92.76 97.76 96.88 Form Emb 70.64 75.13 57.36 65.64 60.38 76.05 68.72 72.68 55.06 73.

	da	en	et	eu	fi	fr	got	he	hu	ro	sv
	POS Hard OH Soft OH 87.37 87Morph 64.69 69.32 57.16 64.51 64.33 72.82 69.94 71.60 61.80 71.36 67.99 65.43 71.36 58.76 67.02 66.84 73.29 70.86 72.75 61.91 72.03 69.48 Hard Emb 64.19 69.51 55.53 64.10 62.58 72.28 69.29 71.51 59.62 70.86 67.82
	Soft Emb 65.33 70.75 57.24 66.18 65.04 73.18 70.46 71.85 60.64 71.34 68.60

Table 3 :

 3 UAS scores for parsers using predicted morphological attributes. The two first rows are POS and averaged attributes prediction accuracy. The third row reports UAS using form representations for comparison purpose. Rows 4 to 7 give UAS using morphological representations, either one-hot or embedding. Regressors output a probability distribution per morphological feature, we either use those soft decision as input for the parser (Soft) or apply argmax first (Hard).

		da	en	et	eu	fi	fr	got	he	hu	ro	sv
	Lem	OH 48.09 57.09 25.30 45.96 40.78 64.88 46.85 54.91 27.80 56.89 48.61 Emb 62.47 70.95 48.17 62.52 59.34 65.62 61.37 64.41 41.59 64.76 65.70
	Form	OH 45.12 54.97 21.29 40.53 34.59 61.95 45.19 55.82 25.60 53.83 45.00 Emb 65.09 71.20 45.79 57.42 52.67 70.81 59.35 66.92 44.30 65.13 64.93
	Morph	OH 69.

19 72.32 64.06 68.19 71.00 73.92 71.04 72.66 64.31 68.94 69.97

  Emb 68.71 72.22 62.81 67.30 68.70 73.96 70.41 71.77 63.45 68.76 69.69

Table 4 :

 4 LAS scores for parsers using lemmas (Lem), forms (Form) or morphosyntactic attributes (Morph) representations as features. Representations are either embeddings or one-hot.

	da	en	et	eu	fi	fr	got	he	hu	ro	sv
	Form Emb 65

.09 71.20 45

  .79 57.42 52.67

70.81 59.35 66.92 44.30 64.13 65.93

	Morph	hard OH soft OH	58.33 62.64 43.80 55.81 54.42 66.66 59.73 63.74 52.41 62.10 60.29 59.68 65.59

47.05 59.43 58.74 67

  .39 62.36 66.25 53.63 63.26 62.44 hard Emb 57.72 62.73 42.22 55.06 52.79 66.25 59.14 63.57 49.99 61.67 60.03 soft Emb 59.13 64.97 45.64 58.25 56.51 67.00 62.02 65.33 52.61 62.65 61.47

Table 5 :

 5 LAS scores for parsers using predicted morpho-syntactic attributes. First row is LAS using form representation. Rows 2 to 5 are LAS using morphological representation, either one-hot or embedding and either hard decisions or soft decisions.