SpaceServer
From OpenCog
SpaceServer is a member of AtomSpace that provides indexing and searching of atoms (representing objects) based on spatial criteria (among other functionality). This page describes the current implementation of the SpaceServer component in Opencog's code. There is also an old page that suggested a design (and specific data structures) for this software component at SpaceServer_(Embodiment), from which the current Space Server inherited some concepts.
Ideally, any data stored in the Space Server should be obtained by mining data in the AtomSpace's hypergraph somehow. In other words, SpaceServer should work like an index component, which may be rebuilt anytime it's needed. However, there are some data in SpaceServer that is not currently stored in the AtomSpace's hypergraph. These are usually required by embodiment code (i.e., depends on the embodied agent being controlled by the Opencog system), as follows:
- the agent radius (for navigation mesh)
- the boundaries of the area the agent is able to perceive (or the agent's FOV)
- for each object in the SpaceServer, a flag that indicates if it's an obstacle or not (for the agent)
So, in addition to provide faster queries about the spatial information of a given object (or queries about which objects match a given spatial criteria), SpaceServer also provides other functionality (like path finding), which depends depends on some properties of the embodied agent being controlled by the system (as listed above).
Another desirable feature would be that whenever spatial information were added to the AtomSpace's hypergraph, SpaceServer were updated consistently without need for explicit and independent calls to SpaceServer's methods. Unfortunately, the insert, remove and update operations of spatial information in AtomSpace's hypergraph are currently independent from these same operations in the SpaceServer. This means that the spatial data consistency between these components depends on the application code (i.e., the programmer is in charge of keeping such a consistency by adding/updating/removing data in both components) So, although SpaceServer is currently a member of AtomSpace, it does not behave like TimeServer, which adds query power to AtomSpace but also ensures its data is consistent with AtomSpace's hypergraph.
Contents |
Representation of spatial information
The first atoms representing spatial information in Opencog hypergraphs (or in Novamente's, to be precise) were created when the AGISim (http://www.agiri.org/wiki/AGISim) project was used as a 3D simulation world for performing some AGI experiments. Since that time, each object in the virtual world is represented by a single atom in the AtomSpace and the spatial information about each object is represented by predicates, which are composed of some specific atoms, as follows:
EvaluationLink
PredicateNode:"AGISIM_position"
ListLink
ObjectNode:"$id"
NumberNode:"$x"
NumberNode:"$y"
NumberNode:"$z"
EvaluationLink
PredicateNode:"AGISIM_rotation"
ListLink
ObjectNode:"$id"
NumberNode:"$pitch"
NumberNode:"$roll"
NumberNode:"$yaw"
The current Opencog code still uses these same atom structures and some other spatial predicates were also added, as follows:
EvaluationLink
PredicateNode:"AGISIM_velocity"
ListLink
ObjectNode:"$id"
NumberNode:"$vx"
NumberNode:"$vy"
NumberNode:"$vz"
EvaluationLink
PredicateNode:"size"
ListLink
ObjectNode:"$id"
NumberNode:"$length"
NumberNode:"$width"
NumberNode:"$height"
See also Perception/Action_Interface for more information about how these spatial predicates come from virtual worlds and are added into Opencog's data structures (via embodiment sub-system).
The requirements for spatial information increased with the development of more features needed to control virtual pets in simulated worlds like Second Life, Multiverse and RealXtend. Some examples of these requirements are:
- the association of time to some spatial information.
- the need for finding paths for a virtual agent controlled by Opencog engine.
- the need for querying about spatial relations between objects in the simulated world (near, next, above, behind, etc).
Although all that spatial information may be represented within Opencog's hypergraph, specialized data structures are needed for a satisfactory performance of the required functionality. These data structures are basically spatial indexes (see http://en.wikipedia.org/wiki/Spatial_index).
The current implementation of Opencog's SpaceServer uses a 2D grid-based spatial index (http://en.wikipedia.org/wiki/Grid_(spatial_index)), which are implemented by the LocalSpaceMap2D (or LSM) class (see details bellow in this page). SpaceServer is actually a set of LSM objects. Each LSM object inside SpaceServer is associated to a given timestamp through its identifier, which is a Handle of the atom that represents the space map in the AtomSpace's hypergraph, as follows:
AtTimeLink
TimeNode <timestamp>
ConceptNode "SpaceMap"
SpaceServer API
Since SpaceServer is basically a set of LocalSpaceMap2D objects (or simply SpaceMaps). The SpaceMaps are added to SpaceServer in chronological order as the embodied agent perceives new spatial data over the time. So, the SpaceServer API basically provides methods for dealing with SpaceMaps. Each SpaceMap is identified by a spaceMapHandle, which is actually the Handle of the AtTimeLink that represents the SpaceMap in a specific timestamp in the AtomSpace's hypergraph. All query methods are actually provided by SpaceMap API. The SpaceServer API contains basically the following methods:
void setMapBoundaries(double xMin, double xMax, double yMin, double yMax,
unsigned int xDim, unsigned int yDim);
void setAgentRadius(double radius);
The methods above provide the parameters to construct the next SpaceMap, which corresponds to spatial information currently perceived by the embodied agent controlled by the specialized Opencog server (aka OPC - Operational Pet Controller - that controls the agent in a virtual world).
bool add(bool keepPreviousMap, Handle spaceMapHandle,
const std::string& objectId,
double centerX, double centerY, double centerZ,
double length, double width, double height,
double yaw, bool isObstacle = true);
The add method adds or updates spatial information perceived about a given object at a given time. It receives the spaceMapHandle (which specify the timestamp the data was perceived), the ID and some spatial properties of the perceived object. The keepPreviousMap argument is set to false to save memory whenever the previous map may be discarded (this depends on the application state). It's important to say that a SpaceMap for a given timestamp is created at the first time the corresponding spaceMapHande is passed as argument to the method add (or remove) method. At this time, if there is a previous SpaceMap, the new SpaceMap will be created as a clone of the previous one, since spatial information about perceived objects at the previous time is considered true while there is no more recent information about these objects. If there is no previous SpaceMap, an empty SpaceMap is created instead. Then, the information about the object is updated in the cloned/created SpaceMap.
Note: As you can see, the addition of an object inside the SpaceMap requires several spatial properties of this object. And these properties are represented by different predicates in AtomSpace's hypergraph (as shown above). This makes harder to keep consistency between AtomSpace's hypergraph and SpaceServer, since some atoms (related to a specific spatial predicate) may be removed while others may not.
void remove(bool keepPreviousMap, Handle spaceMapHandle, const std::string& objectId);
The remove method removes the object with the given ID at the time represented by the spaceMapHandle argument. Note that the object with the given ID may have been cloned from the previous SpaceMap (as explained in the comments about the add method above) and, so, this operation will just fix that information by removing it from the current SpaceMap because the object is not really there anymore.
The remaining methods just deal with SpaceMaps, not their contents:
const bool containsMap(Handle spaceMapHandle) const; const SpaceMap& getMap(Handle spaceMapHandle) const; const SpaceMap& getLatestMap() const; Handle getPreviousMapHandle(Handle spaceMapHandle) const; Handle getNextMapHandle(Handle spaceMapHandle) const; void removeMap(Handle spaceMapHandle); void add(Handle spaceMapHandle, SpaceMap * spaceMap);
AtomSpace API related to SpaceServer
There are also some methods in AtomSpace API that are only related to SpaceServer. They are implemented there because they need to convert timestamp values to their corresponding Handles (the Handles of the AtTimeLinks for each SpaceMap). This should be reviewed in order to get rid of these methods from AtomSpace API. An option to do that would be to use timestamps (instead of Handles) as IDs of the SpaceMaps contained by SpaceServer.
The following methods of AtomSpace are related to SpaceServer:
SpaceServer& getSpaceServer() const;
This just gets the reference of the SpaceServer object.
bool addSpaceInfo(bool keepPreviousMap,
Handle objectNode, unsigned long timestamp,
double objX, double objY, double objZ,
double objLength, double objWidth, double objHeight,
double objYaw, bool isObstacle = true);
Handle removeSpaceInfo(bool keepPreviousMap,
Handle objectNode,
unsigned long timestamp);
The methods above call respectively the add and the remove methods of SpaceServer, after converting objectNode to string and timestamp to Handle (spaceMapHandle).
template<typename OutputIterator>
OutputIterator getMapHandles( OutputIterator outIt,
unsigned long startMoment,
unsigned long endMoment) const;
The getMapHandles method gets all SpaceMaps whose timestamp are within the interval [startMoment, endMoment]. This is used to send spatial information to LearningServer (for imitation learning).
Handle addSpaceMap(unsigned long timestamp, SpaceServer::SpaceMap * spaceMap);
The addSpaceMap adds an entire SpaceMap into SpaceServer. This is used by LearningServer to update its SpaceServer on reception of a set of SpaceMaps from OPC (Operation Pet Controller) for imitation learning purposes.
void cleanupSpaceServer();
This method removes any SpaceMap that is not marked as persistent (i.e., cannot be removed even by forgetting mechanism, or whose spaceMapHandle is set to a high LTI).
LocalSpaceMap2D (SpaceMap)
The LocalSpaceMap2D class implements a grid-based spatial index for representing and querying about all objects (atoms) and points that are in a given rectangular area.
This class support most of the (2D only) queries that will be handled by the final (3D with more efficient data structures) space server, but does so in a possibly less efficient (flat vs. hierarchical) fashion. The 2D Local Space Map is in Launchpad (BZR) as opencog/spatial/LocalSpaceMap2D.h.
Paths and intersections are computed based on a discrete grid and used to identify the distances and possible route paths between objects.
Basic methods
This class has only a constructor that defines a map over a given rectangle of space (specified by xMin, xMax, yMin and yMax arguments), with a discrete grid of xDim * yDim points. The radius of the agent (for navigation algorithms -- see bellow) is also taken as an argument so that certain constraints can be precomputed:
LocalSpaceMap2D(Distance xMin, Distance xMax, unsigned int xDim,
Distance yMin, Distance yMax, unsigned int yDim,
Distance radius);
The addObject method receives the id and some properties (position, bounding box and rotation information) of the object to be added. Also, for agent navigation purposes, the caller of this method must inform if this object is an obstacle or not, as follows:
void addObject( const Spatial::ObjectID& id, const Spatial::ObjectMetaData& metadata, bool isObstacle = false );
For updating the properties of an object already added to a map, one should use the updateObject method, which has the exactly same arguments of the addObject method.
For removing an object from a LSM, the removeObject method is provided:
//remove an object from the map entirely void removeObject(const Spatial::ObjectID& id);
Queries
LocalSpaceMap2D implements several methods for querying about objects and points inside the represented rectangular area. These methods are added on demand. Here is a list of some of the query methods:
// Is the given point occupied by any obstacle or out of bounds? bool illegal(const Spatial::Point& pt) const;
// Gets the nearest free (not occupied or out of bounds) // point from the given point Spatial::Point getNearestFreePoint(const Spatial::Point& pt);
bool containsObject(const Spatial::ObjectID& id) const; bool isObstacle(const Spatial::ObjectID& id) const;
// Gets the grid points occupied by the object with the given id const std::vector<Spatial::GridPoint>& getObjectPoints(const Spatial::ObjectID& id);
// Finds the IDs of all objects within distance d of a certain point g template<typename Out> Out findEntities(const Spatial::GridPoint& g, Spatial::Distance d, Out out) const;
// Finds the nearest entity to a given point satisfying some predicate template<typename Pred> ObjectID findNearestFiltered(const Point& p, Pred pred) const;
Pred is usually a functor class whose operator () receives an object ID as argument and check if it satisfy some predicate or not (e.g., if it's considered a big object based on a specific criterion).
Navigation/Path finding algorithms
There are 3 navigation algorithms implemented within Opencog that uses the LocalSpaceMap2D class:
- TangentBug (first implemented one) -- see TangentBug.h
- A* (implementation using STL by Justin Heyes-Jones) -- see AStartController.h
- HPA (the faster one) -- see HPASearch.h
You can find how these algorithms are used in the PAIWorldWrapper::getWaypoints method where they are selected/executed based on a configuration parameter (see opencog/embodiment/WorldWrapper/PAIWorldWrapper.cc file).
Miscellaneous
Miscellaneous functionality is also provided by LocalSpaceMap2D API - see the class header for details.
