Building plans for household tasks from distributed knowledge
A system and a method are disclosed that provide plans for autonomous machines such as humanoid robots to perform indoor task. Human subjects contribute plans to a knowledge database. Information in the knowledge database is pre-processed to identify task steps and characterize them as action-object pairs, from which a plan database is created. A discriminative technique uses hierarchical agglomerative clustering to select an existing plan from the plan database. A generative technique formulates new plans from the plan database using first-order Markov chains, and may take into account information about the operational environment. Experimentation and evaluation by human subjects confirm the efficacy of both techniques.
1. A computer based method for a humanoid robot to identify steps to perform a task in a constrained environment, the method comprising:
receiving data collected by a distributed capture technique, said data comprising one or more plans for the humanoid robot to perform a task;
automatically extracting from said data a sequence of task steps for the humanoid robot to perform the task;
storing said sequence of task steps in a computer-readable memory;
extracting an action-object pair from said sequence of task steps, said action-object pair corresponding a task step of said sequence of task steps;
determining a conditional probability distribution for said action-object pair, said conditional probability distribution to handle constraints of the environment and specifying a probability distribution to handle constraints of the environment and specifying a probability of occurrence of an action of said action-object pair given a relative frequency of occurrence of an object and a relative frequency of joint occurrence of said action-object pair; and
storing said conditional probability distribution for said action-object pair in a computer-readable memory.
2. The method of claim 1 , wherein the step of receiving data further comprises receiving data from multiple users or from multiple locations.
3. The method of claim 1 , wherein said distributed capture technique comprises receiving a response to a query, the query specifying the task.
4. The method of claim 1 , wherein the conditional probability distribution is determined for each action-object pair according to
P
(
action
❘
object
)
=
f
(
action
,
object
)
f
(
object
)
,
wherein f(action, object) is relative frequency of joint occurrence of action and object, and f(object) is the relative frequency of occurrence of object.
5. The method of claim 1 , further comprising:
capturing a plurality of plan models comprising the task, said action-object pair and said conditional probability distribution for said action-object pair;
determining a set of similarity metrics, each similarity metric indicating a degree of relatedness of each pair of said plan models;
grouping pairs of said plan models whose similarity metrics exceed a first plan similarity into plan pairs;
clustering said plan pairs into hierarchical plan clusters such that an average plan pair similarity within each hierarchical plan cluster exceeds a first average plan pair similarity; and
making a selection of a plan model from one of said hierarchical plan clusters that corresponds to the greatest number of plan models.
6. The method of claim 5 , wherein said similarity metrics are determined according to
Sim
(
p
i
,
p
j
)
=
len
(
LMS
)
len
(
p
i
)
len
(
p
j
)
wherein len(LMS) is the length of the longest matching sequence of said steps of said pair of plan models and len (p i ) is the length of plan p i .
7. The method of claim 1 , further comprising:
extracting a plurality of action-object pairs from said sequence of task steps, each action-object pair corresponding to a task step of said sequence of task steps; and
synthesizing a task model from said plurality of action-object pairs, said task model comprising:
a plurality of nodes, said nodes comprising a start node, one or more task step nodes, and a stop node, each said task step node corresponding to an action-object pair, and
a plurality of links, each link connecting a pair of nodes.
8. The method of claim 7 , wherein the task model further comprises a plurality of transition probabilities, each transition probability indicating a likelihood of an associated task step given the occurrence of an associated preceding task step.
9. The method of claim 8 , further comprising the step of generating a plan, the plan comprising a sequence of said task steps for the humanoid robot to perform the task, each task step corresponding to a task step node, the sequence of said task steps determined according to the equation
NextState
(
t
)
=
arg
max
s
i
p
(
s
i
❘
s
j
)
,
wherein:
NextState(t) represents a task step to be executed at a time t,
s j is a task step that occurs at time t-1,
s i are candidate successor task steps of s j , and
p(s j |s i ) represents a probability of task step s j occurring given an occurrence of task step s i .
10. The method of claim 8 , wherein a transition probability is modified based on the presence of an object corresponding to a task step node in the indoor environment.
11. The method of claim 8 , further comprising the step of generating a plan, the plan comprising a sequence of said task steps, each task step corresponding to a task step node, the sequence of said task steps determined according to the equation
NextState
(
t
)
=
arg
max
s
i
p
(
s
i
❘
s
1
,
s
2
,
…
,
s
i
-
1
)
,
wherein:
NextState(t) represents a task step to be executed at time t,
p(s i |s 1 , s 2 , . . . ,s i-1 ) represents a probability of state s i occurring given occurrences of states s 1 , S 2 , . . . , s i-1 ,
s i are candidate successor task steps of S j ,
S 1, S 2 , . . . S i-1 are task steps preceding task step s i .
12. The method of claim 11 , further comprising the step of randomly selecting a plan in the event of a plurality of best candidate choices.
13. The method of claim 11 , further comprising the step of selecting a plan having a shortest length in the event of a plurality of best candidate choices.
14. A computer software program product embodied on a computer readable medium for performing the method of claim 1 when run on a computing device.