SpaceServer (Obsolete) (Embodiment)

From OpenCog


The system described here is obsolete.. The code for this was removed from github circa 2015. This page remains as an archival page, showing what used to be. See SpaceServer for the current code.


The SpaceServer is an efficient way of storing and accessing information about where Atoms, associated with real/imaginary objects, are located in a spatial frame. The SpaceServer is specifically oriented to spatial domains where there is a global coordinate system (e.g. a simulation world, a video game world, or the planet Earth as viewed by an agent with a GPS system).

The currently implemented SpaceServer uses hash tables. At some point, if performance proves inadequate, it will be upgraded to the design below.

The SpaceServer design suggested here is based on octrees and quadtrees. Before reading on, you should look at the wikipedia pages, unless you are familiar with these data structures.

For the AI Skeleton we will only need the Quadtree part. However, to deal with birds usefully we will need the Octree part as well. Also, dealing with dogs that can navigate up stairs, through multi-story houses, etc., will be annoying without the 3D map (one can of course handle this without a 3D map, but it would likely add more complication than just making a 3D map.) In short, the Octrees are necessary for capturing the 3D structure of the world.

Note that the simple hierarchical structure of the SpaceServer matches naturally with the hierarchical perception architecture suggested in the Novamente book (which matches nicely with what's known about perception in the human brain, see e.g. Jeff Hawkins' book _On Intelligence_ among many other sources).

We considered using R-trees in the SpaceServer, but they turn out not to meet the needs of TangentBug very well (compared to quadtree/octrees, they would make TB both more complicated and slower); and looking further ahead, the simpler hierarchical structure of quadtrees and octrees fits in better with the OpenCog design.

Example Octree code

A nice GPL implementation of Octrees is given here (well the API is nice, I didn't look at the code ;-p ...

(and the author indicates he might be flexible about licensing); however, that implementation does not provide all that we need either as a data structure nor in terms of the API.

I am not sure whether it would be easier to modify this code or just start from scratch. But in any case this code is worthy of study.

Overall SpaceServer Architecture

The SpaceServer, in general, contains a collection of LocalSpaceMaps.

Each LocalSpaceMap is defined by:

  • an identifier indicating the owner of the LSM (a specific avatar] application)
  • an "index tuple": a coordinate tuple, indicating the coords of its lower left front corner in the external world
  • a TimeStamp indicating the time at which it was sampled.
  • an int indicating the number of cells along (any) one of its sides
  • a float indicating the distance, in the external world, covered by one side of one of its cells
  • a float "max_height" indicating the height above ground level at which objects are considered irrelevant for navigation
  • a float "jump_height" indicating how high the avatar can jump
  • a float "avatar_width" indicating how wide the avatar is

In the OAC of simple, single-avatar system we only have one LocalSpaceMap, corresponding to the single avatar at the current time.

In the OAC of a multi-avatars-per-process system, we would have multiple LocalSpaceMaps inside the same SpaceServer.

In the CES, we would have multiple LocalSpaceMaps corresponding to the world-images collected by multiple avatars at multiple times. (In this context, there could be process that merged adjacent or overlapping LSM's into single, larger LSM's. But we can worry about that later.)

In a multi-avatar system and/or the CES, we might want to create some efficient method for finding the LocalSpaceMap with the coordinate tuple closest to a certain query tuple. (E.g. one would build an R-tree or ball tree on the coordinate tuples.) This would allow avatars to efficiently find and look into each others' LocalSpaceMaps.

In the CES, we will want to be able to search the SpaceServer by time as well as space (e.g. find all LSM's corresponding to this region of space, during this interval of time). This requires the LSM's to be indexed by the TimeServer, just like any other TimeStamped entities.

Inside the LocalSpaceMap

Internally, each LocalSpaceMap is an (octree, list of 2DMapTree) pair, with details as described below.

The octree corresponds to a particular 3D region of space.

A 2DMapTree consists of

  • a 3-vector indicating the southwest corner of the region corresponding to the 2D map
  • two ints (m,n) indicating the size of the 2D map (in the x and y dimensions)
  • a quadtree

The most important 2DMapTree in the list corresponds to _ground level_ in the whole 3D region of space covered by the octree. It has n=m equal to the size of the octree, and its southwest corner is the southwest bottom corner of the region covered by the octree.

(Note of course that ground level may vary in its absolute z-coordinate, because there may be hills and valleys, and slanted ground.)

Other 2DMapTrees in the array correspond to "quasi ground level" in that particular 3D region of space: for instance, the floor of the second story of a house.

Basically, if the avatar finds itself on a reasonably large flat surface that is vertically _above_ the ground level, then it should construct a 2DMapTree corresponding to that surface, based on the information in the octree.

For the AI skeleton, we will only deal with the main ground-level 2DMapTree. But for PB 1.0, it may be hard to avoid the other ones, if we want the avatar to successfully navigate multi-story buildings, and recall its information about this effectively in the CES.

Requirements for SpaceServer Quadtrees

Leaf Nodes

Each leaf node N in the quadtree should contain an EntityStructure, consisting of a list of tuples of the form

(entityID, int jumpHeight, int whichSide)

The lists should contain only entities whose perimeters intersect the spatial region defined as follows:

  • base corresponding to the square region R in the x-y plane corresponding to N
  • z-coordinate between ground-level G (defined as G=(maximum ground level in R)) and (G + height)

The jumpHeight int corresponding to EntityID E indicates how high the avatar will have to jump to get over the obstacle corresponding to the part of E in that cell. If there is not room for the avatar to jump (e.g. if there is a solid wall there, or say a wall with a tiny window), then the int can be null or negative or whatever (;-p).

The int whichSide is used to indicate whether the given cell constitutes the front, back, right, left, top or bottom of the entity. (This is used by predicates like nextTo). All these directional qualities are to be judged from the entity's perspective, not the observer's.

For the AI Skeleton we can ignore jumping and whichSide, but they need to be considered for PB 1.0....

Non-Leaf Nodes

A non-leaf node should contain an EntityStructure, formed by merging the EntityStructures of its children.

Requirements for SpaceServer Octrees

These are actually simpler than the quadtrees, as jumping doesn't need to be explicitly considered.

A leaf node contains a list of EntityID's of entities that intersect the voxel (cell) corresponding to the node.

A non-leaf node contains the merger of the EntityID lists corresponding to its children.

Buffer entities are still needed.

SpaceServer API

API for 2D Maps

Requirements for TangentBug

 set<int> findNearObjects(float radius, Point position = current_position_of_avatar)
 // or return a vector<int>

returns all object IDs that are within =radius= of the given position position.

 int find_blocking_obstacle(Point pt1, Point pt2)
 set<int> points_on_perimeter(int objectID, int depth)

Returns the nodes that contain Entity objectID at a given depth of the tree.

I need to be able to look up the center of an object, given its ID.

Given a grid cell, I should be able to query for its coordinates within the quadtree. Ben indicated that this method will return four corners, each having integer coordinates.

 // intersection of an object (an object's perimeter) with a ray at a given tree depth:
 std::vector<cell> intersection(int objectID, Point pt, Point offset, int depth = MAXDEPTH)

The ray starts at pt, and intersects (pt + offset) [using vector addition]

 is_empty_rectangle(rectangle r)

This method will determine whether a given region is free of obstacles. If a section of the map is not known, this method should assume it to be empty. It would be useful but not essential for this method to also return the point where it failed (the first point that turned out to be occupied). The rectangle does not have to be parallel to the x and y axes.

 is_empty_circle(point center, float radius)

Acts similarly to

 ray direction_of_closest_point()

I think if it's no more trouble,

ray direction_of_closest_point(point pt = current_position)

would be better for the future--we hope that Moses will be able to experiment with navigation algorithms in the future.

This method returns a ray (not normalized) pointing from the given point to the nearest object. If there are no objects in the map, I'm not quite sure what this should do. Note that the ray that is returned does not point to the center of the closest object. It points to the closest occupied cell at the maximum tree-depth (maximum resolution).

Requirements for Predicate Mining

The main things we need here are:

  • an index listing all the cells containing EntityID E in their EntityStructure
  • an efficient method to find all entities that are within radius r of a certain point

Note that it's not important to exactly find all entities in the circle of radius r. Approximating the circle with squares fairly crudely is just fine.

Notes on opencog\spatial\

Class Entity holds a position and bounding box of an object in a virtual world.

Class SuperEntity holds a list of overlapping Entity ‘s. The edges of the resulting SuperEntity object consist only of the outside perimeter of the overlapped Entity ‘s. Methods rebuild() and splitEdges() are used to re-compute the outside edges of the combined Entity’s outside edges. An exception will be thrown if attempting to create a SuperEntity with Entity’s that don’t overlap.

The outside perimeter of combined objects may be used for 2D navigation in a virtual world. See image of overlapping Entity’s forming the SuperEntity (SuperEntity.png).


API for 3D Maps

Requirements for TangentBug

Dan will fill this in ... later...

Requirements for Predicate Mining

As for 2D, the main things we need here are:

  • an index listing all the cells containing EntityID E in their EntityStructure (this should be organized by node depth, so that queries can be constrained to a given "resolution"/granularity).
  • an efficient method to find all entities that are within radius r of a certain point