Semantic Linking Maps for Active Visual Object Search (Extended Abstract)

1 Introduction

Being able to efficiently search for objects in an environment is crucial for service robots to autonomously perform tasks [Khandelwal et al., 2017; Veloso et al., 2015; Hawes et al., 2017]. When asked where a target object can be found, humans are able to give hypothetical locations expressed by spatial relations with respect to other objects. For example, a cup can be found "on a table" or "near a sink". Table and sink are considered landmark objects that are informative for searching for the target object cup. Robots should be able to reason similarly about objects locations, as shown in Figure 1. Previous works [Kollar and Roy, 2009; Kunze et al., 2014; Toris and Chernova, 2017] assume landmark objects are static. This assumption is invalid for dynamic landmark objects such as chairs. Further, there also exists uncertainty in the spatial relations between landmark objects and the target object, and between landmark objects themselves. For example, a cup can be "in" or "next to" a sink.

We propose the Semantic Linking Maps (SLiM) model to account for uncertainty of objects locations as well as interobject spatial relations during object search. Building on Lorbach et al. [Lorbach et al., 2014], we model inter-object spatial relations probabilistically via a factor graph. Inferred marginal belief from the factor graph is used in SLiM to account for probabilistic spatial relations between objects. We describe SLiMas a Conditional Random Field (CRF) model to simultaneously maintain the belief over target and landmark object locations with probabilistic modeling over inter-object spatial relations.

Using the maintained belief over target and landmark objects' locations from SLiM, we propose a hybrid strategy for active object search. We select the next best view pose, which guides the robot to explore promising regions that may contain the target and/or landmark objects. Previous works [Wixson and Ballard, 1994; Garvey, 1976; Sj¨o¨o et al., 2012; Aydemir et al., 2011] have shown the benefit of purposefully looking for landmark objects (Indirect Search) before directly looking for the target object (Direct Search). The proposed hybrid search strategy draws insights from both indirect and direct search. In our experiments, We demonstrate the robustness of SLiMto uncertainty of object locations and inter-object spatial relations, as well as the efficiency of the proposed hybrid search strategy.

2 Problem Statement

Let O = {o i |i = 1, · · · ,N} be the set of objects of interest, including landmark objects and the target object for search. Given observations z0:T and robot poses x0:T , we aim to maintain the belief over object locations P(OT |x0:T ,z0:T ), while accounting for the probabilistic spatial relations Ri j between objects o i ,o j ∈ O. For this work, we consider the set of spatial relations to be Ri j ∈ {In, On, Contain, Support, Proximity, Disjoint}. For example, the relation Ri j = In indicates that object oi is inside object oj. The probabilistic spatial relations between object o i ,o j is represented by the belief over Ri j, denoted as B(Ri j).

Based on the maintained belief P(OT |x0:T , z0:T ), the robot searches for the target object by selecting the next best view pose ranked by an utility function U : t ↦→R. t specifies the 6 DOF of camera view pose. During object search, the robot iterates between the belief update of objects' locations and view pose selection, until the target object is found or the maximum search time is reached.

3 Semantic LinkingMaps

For Semantic Linking Maps (SLiM), we consider inter-object spatial relations, while maintaining the belief over target and landmark objects' locations. Building on our previous work [Zeng et al., 2018], we probabilistically formalize the object location estimation problem via a Conditional Random Field (CRF). The model is now extended to account for probabilistic inter-object spatial relations, as shown in Figure 2.

The posterior probability of object locations O history is

where Z is a normalization constant. Robot pose xt and observation zt are known. We assume that the robot stays localized given a metric map of the environment.

fp(o i t , o i t-1 ) is the prediction potential that models objects to remain static or move with temporal coherence (varies across object classes) during the search. fm(o i t ,xt ,zt) is the measurement potential that accounts for the observation model, and zt = {z i t |i = 1, · · · ,N} are (potentially noisy) detections for each object o i at time t. We model the spatial relations between objects with context potential fc,B(Ri j ). Here, we extend fc from our previous work by parameterizing it with the belief B(Ri j) over the inter-object spatial relation between o i , o j ,

where r can take any value in the set of possible relations {In, On, Contain, Support, Proximity, Disjoint}. Please refer to the full paper [Zeng et al., 2020] for more details on each potential function.

3.1 Inference

We propose a particle filtering inference method for maintaining the belief over object locations. Instead of estimating the posterior of the complete history of object locations p(O0:T |x0:T , z0:T ), we recursively estimate the posterior probability of each object o i t ∈Ot , similarly to [Zeng et al., 2018; Limketkai et al., 2007]. Please refer to the full paper [Zeng et al., 2020] for more details on the particle filtering algorithm.

3.2 Probabilistic Inter-Object Spatial Relations

To get the belief over inter-object spatial relations B(Ri j) for each object pair o i , o j ∈ O, we use a factor graph by building on preceding work by Lorbach et al [Lorbach et al., 2014]. We generalize [Lorbach et al., 2014] by relaxing the assumption on known spatial relations between landmark objects.

The factor graph G : {V,F,E} consists of variable vertices V={Ri j|∀i̸=j o i ,o j ∈O}, factor vertices F={FCS,FLC} and edges E which connect factor vertices with variable vertices. Specifically, FCS : Ri j ↦→ R is a unary factor that considers commonsense knowledge on spatial relation between objects, FCS(Ri j ) = Frequency(Ri j ), extracted from online image search engine (e.g. Flickr) by counting the frequency of Ri j, similarly to [Lorbach et al., 2014]. FLC : (Ri j,Rik,Rjk) ↦→{0,1} is a triplet factor that considers logical consistency between a triplet of objects o i , o j , o k , with 1 if consistent and 0 otherwise. For example, if o i is in o j , and o j is in o k , then o i should be in o k to satisfy logical consistency. We infer the marginal belief over inter-object relations B(Ri j) through Belief Propagation [Kschischang et al., 2001].

4 Search Strategy

Based on the belief over object locations, we actively search for the target object, by generating promising view poses and select the best one ranked by a utility function. Given the maintained particles of the target object o in section 3, we fit Gaussian Mixture Models (GMMs) with auto selecting the number of clusters [Figueiredo and Jain, 2002],

4.1 View Pose Generation

For each Gaussian component N (xn, Sn), we generate a set of camera view pose candidates {t i n = (c i n,y i n)}, where cn and yn denote the translation and the rotation of the camera respectively. Initially, we sample cn evenly from a circle with a fixed radius around the center xn of the Gaussian component, and assign a default value to yn. Then, we optimize each sampled view pose via

where vn is the view direction given tn, Etn denotes the effective observation region of the target object at camera pose tn, and c : t ↦→R is a function that computes a signed distance of a configuration t to the collision geometry of the environment.

4.2 View Pose Selection

We propose two different utility functions that trade off between navigation cost and the probability of search success.

Direct Search Utility

UDS enables direct object search, by encouraging the robot to explore promising areas that could contain the target object while accounting for navigation cost,

where wn is the weight of the Gaussian component (as in (3)) that tk is generated from, and dnav is the navigation distance from the current robot location to view pose tk. Parameter a trades off between the probability of finding the target object and the navigation cost. Parameter s determines how quickly the arctan(sdnav) plateaus. In our experiments, we use a A∗ based planner to compute dnav. We empirically set a = 0.1, b = 0.4 , and s = 0.5 such that arctan(sdnav) plateaus as dnav goes beyond 3m.

Hybrid Search Utility

UHS enables hybrid object search, by encouraging the robot to explore promising areas that could contain the target object and/or any landmark object, while accounting for navigation cost

where the additional term compared to UDS acts to encourage the robot to also explore areas that could contain landmark object o j which co-occurs with the target object o with probability CoOccur(o, o j ), inspired by indirect object search strategy [Garvey, 1976; Wixson and Ballard, 1994]. Specifically, CoOccur(o, o j ) = (1 -B(Rtarget , j = Disjoint)), and w j n is the weight of the n-th Gaussian component of GMMs fitted to landmark object o j particles. And I j n is 1 if the n-th Gaussian of object o j is within the effective observation region at camera pose tk, otherwise 0.

5 Experiments

We perform object search tasks in both simulation and realworld environments with a Fetch robot. In the simulations, we quantitatively benchmark methods that resemble previous works and our proposed method. In real-world, we demonstrate qualitatively that the proposed method scales to realworld applications. In both simulation and real-world, the robot moves at most 1m/s and turns at most at 1.7rad/s.

Simulation Experiments

The simulation experiments are performed in an apartmentlike environment (10mx11m) in the Gazebo, as shown in Figure 3. Object detector returns an object detection, if the object is in view, not fully occluded, and within the effective observation range. For large objects (e.g. sofa, fridge), mid-sized objects (e.g. table, sink), and small objects (e.g. cup, laptop, coffee machine), the effective observation range is 5m, 4m, 2.5m respectively. We benchmark following methods.

UDS. Uninformed direct search (Eq.5). The robot does not account for the spatial relations between the target and landmark objects (omitting Eq. 2 in SLiM). This baseline represents a naive approach for object search.

IDS-Known-Static. Informed direct search (Eq.5) with a known prior on landmark object locations. The robot assumes that landmark objects are static. This method resembles previous works [Kollar and Roy, 2009; Kunze et al., 2014; Toris and Chernova, 2017].

IDS-Known-Dynamic. Informed direct search (Eq.5) with a known prior on landmark object locations. This is similar to IDS-Known-Static except that the robot does not assume the landmark objects to remain static.

IDS-Unknown. Informed direct search (Eq.5) without prior on landmark object locations. The particles for landmark objects are initialized uniformly across the environment. This method resembles previous works [Loncomilla et al., 2018; Aydemir et al., 2010].

IHS-Unknown. Informed hybrid search (Eq.6) without prior on landmark object locations.

All methods except for UDS are using the full SLiM model. We assume that an occupancy-grid map of the environment is given. We also assume that the room types are accurately recognized. IDS-Known-∗ methods are provided with a noisy prior on landmark object locations, to emulate the common cases where perfect knowledge about landmark locations is not available. For all methods, the particles for the target object are initialized uniformly across the environment.

For each target object, we run 6 trials per method. In each trial, the robot starts at the same location shown in Figure 3. A trial is successful if the robot finds the target object (i.e. belief converges at the correct location) before timeout. For each target object and each method, we measure the number of view poses, search time, distance travelled by the robot, and search success rate averaged across all trials. The benchmark result is as shown in Table 1. Examples of the resulting search path from each method are depicted in Figure 4. As we can see, UDS is not as efficient because it is not making use of the spatial relations between the target and landmark objects in the environment. Given a noisy prior on landmark object locations, IDS-Known-Dynamic outperforms IDS-Known-Static because it accounts for the uncertainty of the landmark object locations, whereas IDS-KnownStatic is misled by the noisy prior.

Given no prior information, IHS-unknown outperforms IDS-unknown because it encourages the robot to explore promising regions that contain the target and/or useful landmark objects, whereas IDS-unknown only considers promising regions that contain the target object. With IHS-unknown, the robot benefits from finding landmark objects which help narrow down the search region for the target object.

Real-World Experiments

The real-world experiment is executed in an environment (8mx8m) that consists of a kitchen and a living room. The robot stays localized with LIDAR, and navigates with a MPEPC path planner [Park et al., 2012]. The target object is a cup, and landmark objects include table, sofa, coffee machine and sink. IHS-Unknown reached average success rate of 0.7 (7 out of 10 trials). The average number of view poses, search time and search path is 4.86, 103s, and 8.32m repectively. The failure cases were due to false negative detection of the cup due to lighting (we used Faster R-CNN [Ren et al., 2017] trained on COCO dataset [Lin et al., 2014]). Examples of real-world experiments with a Fetch robot is available in online video https://youtu.be/uWWJ5aV6ScE.

6 Conclusion

In this paper we present an efficient active visual object search approach through the introduction of the SLiMmodel. SLiM simultaneously maintains the belief over target and landmark objects locations, while accounting for the probabilistic interobject spatial relations. Further, we propose a hybrid search strategy that draws insights from both direct and indirect object search. Given noisy or no prior on landmark objects locations, we demonstrate the benefit of modeling landmark objects locations under uncertainty in SLiM, and the hybrid search strategy that encourages the robot to explore promising areas that can contain the target and/or landmark objects in both simulation and real-world experiments.