SpaceServer (Embodiment)
From OpenCog
What is the Space Server?
This page outlines the design of a software component I'm calling the SpaceServer.
It is needed for PetBrain, and should also be useful within NCE.
Also, the design proposed here is intended to be useful both in the PetBrain case where each pet is in its own OS process, and in the PetBrain case where all the pets are in the same OS process.
The basic point of the SpaceServer is to have an efficient way of storing and accessing information about what Atoms are located at what objects in space. It 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 SpaceServer needs to support a number of different use cases already in PB 1.0, and will need to support even more as we expand PetBrain further. So we need a simple, reasonably efficient, and flexible/adaptable data structure.
The currently implemented SpaceServer uses hash tables, and is described at RudimentarySpaceServer. At some point, if performance proves inadequate, it will be upgraded to the design below. For now, the information below will not be updated (so see RudimentarySpaceServer instead)...
The SpaceServer design suggested here is based on _octrees_ and _quadtrees_, see
* http://en.wikipedia.org/wiki/Octree * http://en.wikipedia.org/wiki/Quadtree
(thx go to Dan for identifying the names of these data structures, which I had forgotten). Before reading on, you should look at these brief wikipedia pages, unless you remember 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 Novamente 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 ...
http://nomis80.org/code/octree.html
(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 pet, in the PetBrain 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 pet can jump * a float "pet_width" indicating how wide the pet is
In the OPC of simple, single-pet system we only have one LocalSpaceMap, corresponding to the single pet at the current time.
In the OPC of a multi-pets-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 pets 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-pet 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 pets 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 pet 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 pet 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 pet 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 pet 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_pet)
// 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 =is_empty_rectangle()
ray direction_of_closest_point()
I think if it's no more trouble, =<verbatim>ray direction_of_closest_point(point pt = current_position)</verbatim>= 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.
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
-- Main.BenGoertzel - 11 Jul 2007
