Ok this is a first draft, the file is Blocksworld_FSM.scm (in the branch
"restart_master") and the README explains almost everything (skip
implementation 1 as I still have to upload the file and look at
implementation 2).
https://github.com/raschild6/blocksworld_problem/tree/restart_master
<https://github.com/raschild6/blocksworld_problem/tree/restart_master>
Il giorno lunedì 16 agosto 2021 alle 13:14:38 UTC+2 Michele Thiella ha
scritto:
Before analyzing and answering what I have written, I am trying a
different approach, based on the examples of FSM.
Probably, there are big conceptual errors in my previous post,
so before we get lost in talking about that, maybe I'll try this new
approach first.
Michele
Il giorno sabato 14 agosto 2021 alle 16:36:17 UTC+2 Michele Thiella
ha scritto:
Hello everyone,
I will try to explain in a simple way:
1) my problem and my goal
2) the possible solutions
3) errors/shortcomings found and extra questions encountered
along the way
*1) The Problem:*
Let's start from scratch. My problem is based on the classic
problem called "blocksworld problem". That is:
- there is a robot manipulator that has 4 actions available:
pickup, putdown, stack, unstack.
- there are blocks on a table
- there is a goal to be achieved
*The Goal: *
I am trying to solve any possible arrangement of the blocks. So
my work aims to take as input a final arrangement of the blocks and
through backward inference, obtain the derivation tree to reach
that arrangement, through the 4 actions mentioned above.
(I'll explain better later)
*The construction of the problem:*
- each block can be "clear", ie. the robot can take it
(it is not clear to me if the vice versa "not-clear" is also
necessary)
- the robot hand may be "busy": so it is holding a block. Or
"free": it has nothing in its hand
- the 4 actions:
1) pickup:
- preconditions: "clear" block, "on-table" block and
"free" (robot) hand
- effects: "not-clear" block, "in-hand" block and "busy" hand
2) putdown:
- preconditions: "not-clear" block, "in-hand" block and
"busy" hand
- effects: "clear" block, "on-table" block and "free" hand
3) stack:
- preconditions: block1 "in-hand", block2 "clear" and
"busy" hand
- effects: block2 "not-clear", block1 "on" block2, block1
"clear" and hand "free"
4) unstack:
- preconditions: block2 "not-clear", block1 "on" block2,
block1 "clear" and hand "free"
- effects: block1 "in-hand", block2 "clear" and "busy" hand
Basically the 4 actions mirror physics.
Eg. If I want to take a block from the table, the block must be
free ("clear") and my hand must be free.
If block A is "on" block B then I can "unstack" block A and then
make block B "clear" and having block A in hand.
Obviously the pickup action is the opposite of putdown and are
used to take/place a block from/on the table.
The stack action is the opposite of unstack and are used to
put/take a block on/from another block.
I hope the introduction to the problem is complete enough.
*2) Implementation:* (note that I'm looking for an Atomese-pure
implementation)
- Initial Set in the atomspace:
An external algorithm detects all the blocks present on the table
(for now the initial arrangement of the blocks does not have any
blocks on top of another, as the detection of the blocks is done
through Apriltag
and therefore I would not be able to find the blocks placed
under others.
If I have time I will solve this problem using PointCloud.
This is to say that my initial block arrangement can be any.
Eg. 4 blocks:
- A on B on C, D on table
- A on D, B on C
- A, B, C, D on table
- and so on ...
)
So my atomspace will be about:
(SetLink
; block1
(InheritanceLink (stv 1 1)
(ConceptNode "block1")
(ConceptNode "object"))
(EvaluationLink (stv 1 1)
(PredicateNode "clear")
(ConceptNode "block1"))
; block2
; ....
; differentiate the various blocks
(NotLink (EqualLink (ConceptNode "block1") (ConceptNode
"block2")))
)
- Goal Implementation:
it completely depends on how the model is formulated.
If you look for a state resolution (finite state machine type)
the goal will be formulated as one of them.
Alternative: in the end, each block will always be on top of
something (table or other block) so a possible goal formulation
would be like:
(define (compute)
(define goal-state
(AndLink
(ListLink
(VariableNode "$ A")
(VariableNode "$ B")
)
(ListLink
(VariableNode "$ B")
(VariableNode "$ C")
)
(NotLink (EqualLink (VariableNode "$ A") (VariableNode
"$ B")))
(NotLink (EqualLink (VariableNode "$ A") (VariableNode
"$ C")))
(NotLink (EqualLink (VariableNode "$ B") (VariableNode
"$ C")))
)
)
(define vardecl
(VariableList
(TypedVariableLink
(VariableNode "$ A")
(TypeNode "ConceptNode"))
(TypedVariableLink
(VariableNode "$ B")
(TypeNode "ConceptNode"))
(TypedVariableLink
(VariableNode "$ C")
(TypeNode "ConceptNode"))
(TypedVariableLink
(VariableNode "$ D")
(TypeNode "ConceptNode"))
)
)
(cog-bc rbs goal-state #: vardecl vardecl)
)
- Rules for inference:
Same considerations made for the formulation of the goal.
Let's start with the rules corresponding to the 4 robot actions
and leave out extra rules.
If we rely on the definition above, then for example the stack
rule would be something like:
(define stack
(BindLink
(VariableList
(TypedVariableLink (VariableNode "?ob") (TypeNode
"ConceptNode"))
(TypedVariableLink (VariableNode "?underob") (TypeNode
"ConceptNode"))
) ; parameters
(PresentLink
(NotLink
(EqualLink (VariableNode "?ob") (VariableNode
"?underob")))
(InheritanceLink
(VariableNode "?ob")
(ConceptNode "object"))
(InheritanceLink
(VariableNode "?underob")
(ConceptNode "object"))
(AndLink
(EvaluationLink
(PredicateNode "in-hand")
(VariableNode "?ob"))
(EvaluationLink
(PredicateNode "clear")
(VariableNode "?underob"))
)
)
(ExecutionOutputLink
(GroundedSchemaNode "scm: stack-action")
(ListLink
; effect: this represent ?ob "on" ?underob
(ListLink
(VariableNode "?ob")
(VariableNode "?underob")
)
; precondition
(AndLink
(EvaluationLink
(PredicateNode "in-hand")
(VariableNode "?ob"))
(EvaluationLink
(PredicateNode "clear")
(VariableNode "?underob"))
)
)
)
)
)
*3)* Before talking about the problems that this writing (and
the state-based alternative) has, I would like to talk about
backward inference.
Probably the implementation and functioning of URE is my biggest
shortcoming
and also the reason why I don't find the right way to formulate
and solve this problem. Some questions:
3.1) I've always seen backward inference work via BindLink and
VariableNode. I have no idea if there is an alternative/better
way to do it.
3.2) As Linas mentioned, BindLink requires PresentLink and this
is one of the biggest problems.
By backward inference the rules are called and combine into a
large BindLink and the same is true for the PresentLink.
In the end, you get a large PresentLink made up of all the
PresentLinks of the called rules.
This means that for example I cannot use atoms like
; atom [0]
(EvaluationLink
(PredicateNode "clear")
(VariableNode "? Ob"))
; atom [1]
(EvaluationLink
(PredicateNode "not-clear")
(VariableNode "? Ob"))
because it doesn't make sense that the same block is both
"clear" and "not-clear".
----------------------
PS. this leads to another question: is what I am saying correct?
I'll explain:
Suppose I have 2 rules. One has the atom [0] in the PresentLink
and the other has the atom [1].
Suppose the rules are called in succession from backward inference.
When is PresentLink evaluated? From what I've seen:
1) the two rules compose the new BindLink, containing the
PresentLink of both (which I think is the "Expanded forward
chainer strategy")
2) The BindLink is evaluated and then the solutions are found or
not (which I think is the "Selected and-BIT for fulfillment")
Then, only at the end, the PresentLink is evaluated, this
implies that both atoms [0] and [1] must be present together in
the atomspace.
This is incorrect: "The PresentLink of each rule is evaluated
when that rule is called." Right?
----------------------
That said, it wouldn't seem like a problem. Instead it is,
because it means that once the rule writes a new atom into the
atomspace
then that atom will always be present and therefore the rule
that uses that atom as a precondition can be called whenever it
wants.
Consequently , in example:
- blocks A, B, C
- initial arrangement: A "on" B, C on the table
- goal: Variable ?ob "on" Variable ?underob
Consequently, for example, the use of certain atoms is no longer
good for trying to follow the physics of actions
(eg hand- "busy" and hand- "free": I can only take an object if
my hand is free).
The two atoms will always appear in the PresentLink and
therefore, after doing a "pickup" and a "putdown",
I can do two "pickups" in a row without worrying about having to
put the object down first.
So, you don't understand anything.
But essentially the presence of certain atoms to limit the
solutions to only physically correct sequences of actions does
not work (or at least I have not been able to find a logic that
fits).
3.3) Mirror problem with unstack rule:
First let's take a step back:
- blocks A, B, C
- initial arrangement: A, B, C on the table
- goal:
(AndLink
(ListLink
(VariableNode "?ob")
(VariableNode "?underob")
)
(NotLink (EqualLink (VariableNode "?ob")
(VariableNode "?underob")))
)
Backward inference could call the following rules in order:
(conjunction joins two Links in a AndLink)
(goal) <- conjunction <- stack <- conjunction <- pickup <-
(init-set)
(EvaluationLink (PredicateNode "clear")(VariableNode "?ob"))
----------------------------------------pickup-action----------------------------------------
(EvaluationLink (PredicateNode "in-hand") (VariableNode "?ob"))
(EvaluationLink
(PredicateNode "clear")(VariableNode "?underob"))
==========================================================conjunction============================================================
(AndLink
(EvaluationLink
(PredicateNode "in-hand")
(VariableNode "?ob"))
(EvaluationLink
(PredicateNode "clear")
(VariableNode "?underob"))
)
-------------------------------------------------------------------------------------------------------
stack-action ----------------------------------
(ListLink
(VariableNode "?ob")
(VariableNode "?underob")
(NotLink (EqualLink (VariableNode "?ob") (VariableNode
"?underob")))
==========================================================conjunction=========================================================================================
(AndLink
(ListLink
(VariableNode "?ob")
(VariableNode "?underob")
)
(NotLink
(EqualLink (VariableNode "?ob") (VariableNode "?underob")))
)
and returns as a solution all the combinations of the 3 blocks
one above the other two by two.
This is great, but analyzing the rules, then "unstack" would be
of the form:
(ListLink
(VariableNode "?ob")
(VariableNode "?underob")
-----------------------------------------------------------------------------------------------------------------
unstack-action
-----------------------------------------------------------------------------------------------------------------
(AndLink
(EvaluationLink
(PredicateNode "in-hand")
(VariableNode "?ob"))
(EvaluationLink
(PredicateNode "clear")
(VariableNode "?underob"))
)
and now the trouble begins, because, as for the conjunction rule
used for stack, then I need a disjunction for unstack rule,
(AndLink
(EvaluationLink
(PredicateNode "in-hand")
(VariableNode "?ob"))
(EvaluationLink
(PredicateNode "clear")
(VariableNode "?underob"))
)
==========================================================disjunction============================================================
(EvaluationLink (PredicateNode "in-hand") (VariableNode "?ob"))
(EvaluationLink
(PredicateNode "clear")(VariableNode "?underob"))
Which from what I know is not possible to have because there is
always a single atom as an effect and a single atom as a
precondition.
But there should be something like the composition rule:
Γ′⊢ψ Γ, ψ, Γ ”⊢ ∇
--------------------------------------------------
Γ, Γ ′, Γ′′⊢ ∇
3.4) Finally, the last and I think the most important question:
let's try to work by states.
Well, I have tried many ways and I have not succeeded in any.
Basically I found some shortcomings rather than logical errors.
As has been said, the number of states for this problem is large
to have them all in the atomspace (especially if we use a lot of
blocks) and a waste because, based on the goal, 3/4 of the
states would be useless.
So there are 2 ideas (always in Atomese-pure):
1) Find a rule that takes in (precondition) a state and an
action and returns (effect) a new state.
2) Find 4 rules (one for each action) that take in
(precondition) a state and return (effect) a new one.
So, first of all:
- I could not give as a precondition: the last state created.
The preconditions and effects of the rules are non-generic
atoms. The only possibility I had thought was to have the input
state as VariableNode, so that with fulfillment it would try all
the atoms that represented my states.
But this is not good because maybe after n actions, instead of
taking the n-th state and creating the n + 1-th state, it could
take the i-th state and create the n + 1-th state. And of course
it is wrong because the i-th state is old and the layout of the
blocks has certainly changed. (I hope it's clear enough)
This led me to think that StateLink was a good atom for this
purpose.
- StateLink is unique, so it's fine as a precondition of my rule
because it will definitely always represent the current
situation of my blocks.
Yet when I get a sequence of states as a solution to my
inference, then in the PresentLink of my final BindLink all
these states are required to be present in the atomspace. And
this does not work (always confirming my initial assumption that
the presence in the atomspace of the atoms contained in the
PresentLink is verified at the time of fulfillment and not at
the call of each rule), because all the StateLinks prior to the
last one no longer exist, for StateLink definition.
- I tried associating a Floats Value to the StateLink to
represent the state of each block, so for example for each block
one bit for "clear" / "not-clear", one bit for "in-hand" /
"not-in -hand ", etc ...
The idea was to change the status bits of an object as a rule
was called on that object.
I guess that's not good because:
- either the bits of the Value are the precondition and the
effect of the rule, or the inference does not perceive their
change during the calls of the various rules (if for example the
flips of the bits occur in the GroundedSchemaNode)
- even if the bits of the Value were the precondition and
the effect of the rule, there would still be the PresentLink
problem. So once I have created the "can-pickup" state of block
A, it will always be usable because it is inserted in the
atomspace, even when A is no longer "pickable".
*4) Conclusions:*
I think something is missing from the current system to solve
this problem (or I need some advice because I can't do it in any
way)
- The idea is a StateLink which however does not delete its old
state but which keeps it in the atomspace. But somehow it can be
called generically as a precondition of the rules, and this
generic call always refers to the last StateLink created. (I saw
that there was an obsolete atom: LatestLink, which maybe took
over part of this operation)
So the operation would be (call this new atom LatestStateLink):
(define choose-action
(BindLink
(VariableList
(TypedVariableLink (VariableNode "?ob") (TypeNode
"ConceptNode"))
)
(PresentLink
(InheritanceLink
(VariableNode "?ob")
(ConceptNode "object"))
(LatestStateLink "actual_state"
(ListLink (ConceptNode "?ob") (PredicateNode
"state"))
(FloatValue 0 1 0 .....)
)
)
(ExecutionOutputLink
(GroundedSchemaNode "scm: action")
(ListLink
; effect:
(LatestStateLink "actual_state"
(ListLink (ConceptNode "?ob") (PredicateNode
"state"))
(FloatValue 1 1 1 .....)
)
; precondition
(LatestStateLink "actual_state"
(ListLink (ConceptNode "?ob") (PredicateNode
"state"))
(FloatValue 0 1 0 .....)
)
)
)
)
)
This is very similar to StateLink except for the name given to
LatestStateLink. The idea is that the precondition for this rule
is to check only the last state relative to the ?ob block and
not the previous ones as well. If the last state, which I named
"actual_state", has the FloatValue corresponding to the
required ones then the rule can be called, otherwise not.
When the rule is called the effect is written on the atomspace
and then a new LatestStateLink "actual_state" is added and the
previous LatestStateLink is left in the atomspace losing the
name (so that you have one and only one "actual_state").
By doing this, it is possible to write rules in a generic way
that respect the physics of actions and function in states.
it's just a draft it will probably have other errors but it was
one of the ideas that came to me.
Unfortunately I haven't even looked at the C ++ implementation
part of the Atom and their types. So for "code additions" of
this type I think I don't have the time to get by, understand
how the C ++ part works and write the code correctly and completely.
This is all I have managed to write. I'm sorry it's so long and
I apologize for the many unclear parts and logical and
grammatical errors.
For those who like it, happy reading!
Michele
--
You received this message because you are subscribed to the Google
Groups "opencog" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to [email protected]
<mailto:[email protected]>.
To view this discussion on the web visit
https://groups.google.com/d/msgid/opencog/da3335d2-8255-4bea-aa1d-bef8823e7378n%40googlegroups.com
<https://groups.google.com/d/msgid/opencog/da3335d2-8255-4bea-aa1d-bef8823e7378n%40googlegroups.com?utm_medium=email&utm_source=footer>.
