Journal of Software Engineering and Applications, 2011, 4, 156-160
doi:10.4236/jsea.2011.43017 Published Online March 2011 (http://www.SciRP.org/journal/jsea)
Sensor Robot Planning in Incomplete Environment
Shan Zhong1, Zhihua Yin2, Xudong Yin1, Yufeng Yao1
1Computer Science and Engineering College, Changshu Institute of Technology, Changshu, China; 2School of Computer Science and
Telecommunication Engineering, Jiangsu University, Zhenjiang, China.
Received February 15th, 2011; revised March 5th, 2011; accepted March 8th, 2011.
ABSTRACT
Aiming at the former formalized methods of robot planning should give the environment state, can not obtain the new
knowledge of the environment. In order to improve the reason ability for obtaining new knowledge of the environment
state, the actions in the process of planning such as external action and sensing action are formalized. A formalized
reasoning method—CPNI (Colored Petri Net for Planning in incomplete environment) based on two kinds of actions is
proposed, and the reasoning rule as Fluent Calculus in incomplete environment is applied. Robot planning experiment
is modeled and simulated by using the tool CPNTools and the result shows the state knowledge of the door and the
action sequence to reach the goal can be generated automatically in the CPNI net system.
Keywords: Sensor, Robot Planning, Colored Petri Net, Action Sequence
1. Introduction
Robot planning [1] is the behavior planning process to
reach the goal, it mainly includes two problems: generate
the action sequence to reach the goal, and obtain the dy-
namic knowledge in the process of reasoning.
Petri net [2-3] is a formalized description tool and sui-
table model for modeling the system characterized by
synchronism, dynamics, concurrency. Silva [4] converted
the planning graph to the acylic Petri net to plan, but can
not represent the incomplete state knowledge. Vittorio [5]
introduced a method for robot planning based on Petri net,
formally describing actions and the relations between the
actions, but it lacks the formal description for the state
including the environment state and robot state, can not
generate automatically the action sequence to the goal,
and also can not represent the incomplete knowledge.
The above work can not realize the robot planning, na-
mely, automatically generate the action sequence to the
goal and obtain the knowledge in the process of the rea-
soning, finally realizing robot planning in incomplete en-
vironment.
In this paper, the sensor is introduced into the robot,
converting the process of sensing the state to the sensing
action of the according CPNI net system, through the
sensing action, the robot can get the new knowledge of
the world state, realizing the representation of the dyna-
mic and unknown environment and then reasoning in an
incomplete environment. The Fluent Calculus [6-7], sen-
sing action and the external action are introduced to the
generating algorism of the CPNI net system, the gene-
rated CPNI net system can not only realize robot plan-
ning and also the dynamic knowledge of the robot rea-
soning.
2. Reasoning Rule and the Example
2.1. Fluent Calculus
As for the Fluent Calculus, all changes to the world can
be the result of named actions. A possible state history is
a sequence of actions to reach the goal called situation.
Fluent is for representation of the atomic properties of
the physical world. The function State(s) denotes the state
in situation s, which links the two key notions named state
and situation.
Precondition axioms are used to formally specify the
circumstances under which an action is possible in a state
in situation s, denoted by predicate Poss (a, state(s)) sho-
wed in Equation (1), which means at the state state(s), the
action A(x) can be executed. The

,
A
x
z as a pure
state axiom about z is the conjunction of the conditions
under which the action can be happened.



 
,
A
PossAxx z

 (1)
State update axioms defines the effects of an action a
as the difference between the state prior to the action,

Sensor Robot Planning in Incomplete Environment 157
State(s), and the successor State(Do(a, s)), showed in
Equation (2), in which

,
x
z is the pure state axiom
representing the current state, v (the positive effect)
represents the adding states, while v (the negative
effect) represents the removed states, and state(s) re-
presents the unchanged states and the unknown states.
   
 


,,
,
PossAxsx States
StateDoA xsState svv




 (2)
2.2. Example for Fluent Calculus
The robot example is showed as Figure 1. The round re-
presents the robot. There are four rooms such as R501,
R502, R503, R504, and alley. Every neighbor room is
connected by a door, and the door also connects the nei-
ghbor room and alley, for example, D12 connects room
R501 and room R502, and DA2 connects Alley and room
R502.
The actions which the robot can do are as follows: go
(door), enter(room) and open(door), the precondition axi-
om and the state update axiom are as follows:
1) The action go(x) means robot goes to the door x.
The constraint is the door x’ which the robot currently at
is different from the goal door x, the constraint can be
defined in the guard function of the transition. The pre-
condition axiom and the state update axioms will be de-
scribed showed in Equations (3) and (4):












,1,,_,,_PossgoxzInrAt xC xrC xr

 
(3)
The Equation (3) represents the preconditions of the
action go(x), In(r)At(x') denotes the robot is at the door
x’ of the room r, c(x1,r,_) represents the door x1 connects
the room x1 and _.
   


 

 

,,
,
1,,_,,_
PossgoxsHoldsIn rAtxs
StateDo go xsInrAtx
CxrCxrAtx Atx





 


(4)
The Equation (4) represents the successor state of action
Figure 1. Robot planning in the incomplete scene .
go(x), the predicate c(x',r,_) represents the unchanged
state, the adding state v

is represented by the predicate
At(x) The removed state v is represented by the pre-
dicate At(x'), and it means the robot is not at the door x’
of the room r.
2) The action enter(r) represents the robot enter the
room r, the constraint is the current room r’ which agent
in is different from the goal room r. The precondition
axiom and the state update axioms are showed as Equa-
tions (5) and (6):





 
,,,
P
ossenterrzInrAtxCx rr

 (5)
The Equation (5) represents the precondition of the ac-
tion enter(r), namely, the robot is at door x in the room r'
and the door is closed.



   
 

 
 
,,
,
,,
Poss enterrsHolds In rAtxs
StateDo enterrsIn rAtx
CxrrClosedx Closedx








(6)
The successor state of the action enter(r) showed in
Equation (6) are as follows: The adding state v

is
closed(x), the deleted state is closed(x).
3) The action open(x) represents opening a door. The
precondition axiom and the state update axiom are sho-
wed as Equations (7) and (8), respectively.



 


,Poss Openxzclosedxkeyx (7)
The Equation (7) represents the preconditions of the
action: the predicate closed(x) represents the door x is
closed and the robot has the key to the door x.



  
 

 
 
,,
,
Poss openxsHolds Closedxs
State Do openxsClosedxKeyx
Closed xClosed x




(8)
The Equation (8) represents the state update axiom of
action open(x), the adding state v is closed(x), the
removed state v

is closed(x).
4) The action check_true(x) and check_false(x) repre-
sents sensing the state of the door. The precondition
axiom and the state update axiom are showed as Equa-
tions (9) and (10), respectively.




  
_
_,Posschecktrue xcheckfalse xz
closedxclosed x

 (9)
The Equation (9) shows the precondition of the action
check_true(x) and check_false(x) is that robot do not
know the state of door x.

Sensor Robot Planning in Incomplete Environment 158
 
  

 
  

,
_
_,
Poss enterrs
StateDo checktruexcheckfalsexs
senseClosedx
trueClosed xsenseClosed x
falseClosed x


 

(10)
The Equation (10) denotes shows the successor state of
action enter(r), if the robot senses the door is closed, then
the adding state v is closed(x), else the adding state is
closed(x).
3. CPNI Net System
3.1. The Introduction for CPNI Net
Definition 1 A CPNI net system is a 7-tuple system ∑ =
(P, Tv; F, C, I−, I+, M0), which is a timed colored Petri
net system has the following characteristics:
1) The place i pP represents the states place and
the auxiliary place, the state place includes both the state
of robot and the environment state, the auxiliary place is
playing an auxiliary role in the robot planning such as the
sensor place, the action sequence place and the goal place.
2) The transition tT represents the actions which
the robot has the ability to do. The actions include exter-
nal action and sensing action.
3) M0 is the initial state represents the initial state of
the agent and the environment.
3.2. The Representation of External Action
Definition 2 The external action in the robot planning
can be represented as Figure 2. The place pi1, pi2, ···, pik
denotes the removed states, po1, po2, ···, pom denotes the
adding states, pio1, pio2, ···, pio denotes the states repre-
sented by the same place including the unchanged states
(the place and the token are the same before and after
action happened) and the changed states (the place is the
same and the token is changed).
3.3. The Representation and the Sensing Action
Definition 3 The internal action namely the sensing ac-
tion is showed as Figure 3, the place _PSense denotes
the existing of the sensor, according to the different sen-
sors, there are different sensing actions. If there are to-
kens in place _PSense, then the robot can do the sens-
ing action, the transition check_true(x) represent when
the robot sensing the state is true, then a token is flowed
to the place Check_state, while the transition check_
false(x) represents when the robot sense the state is
holding, then a negative token is flowed to the place
_Checkstate .
Figure 2. Representation of external action.
Figure 3. Representation of sensing action.
4. The Constructing Algorism for CPNI Net
System
The input of algorism: the precondition axiom and the
successor state axiom, the initial state and the goal state.
The output of algorism: the robot planning CPNI net
system.
Step 1 Define P, T, F, C, I−, I+, M0 as set, P is the col-
lection of places, ActionSequences
pP stores action se-
quence, Goal
pP

stores the goal of agent, T is the col-
lection of timed transition, F is the collection of arc, I−
and I+ are the arc set, M0 is the initial marking converting
from initial state, for the convenient, the subset F1 of F is
defined.
Define i as a counter, the initial value of i is 1
ActionSequences Goal
PP pp

;
Step 2 Loop the implementation of the following part
until all the preconditions and successor states of the ac-
tion have already been constructed, and when the i-th
action is executing,
T = T ∪{ti}; //Action is represented by transition

Sensor Robot Planning in Incomplete Environment 159
 



1,,,,
,,,,,
iActionSequencesActionSequences i
iActionSequencesiGoalGoal i
F
Ftpp t
tptpp t

;
if ti is the external action, then
if pik is the removed state, then

,,
ActionSequences Goal ik
PP ppp ;



1,
ik i
F
Fpt ;
else if pik is the unchanged state then

,,
ActionSequences Goal ik
PP ppp ;



1,,,
iik iki
F
Ftppt ;
else if pik is the adding state then

,,
ActionSequences Goal ik
P
Ppp p ;




1,
ik i
F
Fpt ;
end if
else if ti is a sensing action then

_
,,
ActionSequences Goal
PP pppsense ;



 
 
 
1_, _,
_, _,_,_ ,
_
,_,_,_,
_, _
FFpsense CheckF
p senseCheckTCheckFp sense
Check TpsenseCheck TCheckState
CheckF CheckState

;
end if
Step 3 i: = i + l, if all the actions have been iterated for
once, then go to the Step 4, else go the Step 2
Step 4 After the unchanged state, the adding state and
the removed state of all the actions are constructed, ac-
cording to the initial states of system, the token is added
to the relative place then the initial marking M0 is ob-
tained. In the following part, the CPNI model of the en-
tire system will be constructed in the example.
5. Simulation Experiment
The initial state for the robot is showed as Figure 1, the
robot is at the door “D23” of the room “R503” and has the
key of door “DA3”. The doors “DA3” and “D23” are clo-
sed. The initial state are as follows: M0 = {In(“R503”) At
(“D23”), Key{“DA3”}, Closed{“D23”,“DA3”},C{(“DA1”,
“R501”,“Alley”),(“DA2”,“R502”,“Alley”),(“D23”,“R502”,
Figure 4. Simulation figure for the office scene.

Sensor Robot Planning in Incomplete Environment 160
“R503”),(“D34”,“R503”,“R504”),(“DA2”,“Alley”,“R50
2”),(“DA3”,“Alley”,“R503”),(“DA4”,“Alley”,“R504”)}}.
The transition go(x), enter(r) and open(x) represents the
action of robot such as go(x), enter(r) and open(x), res-
pectively. The internal action needs two transitions to de-
note, the transition check_true(x) denotes the executing
action when the sensing state is true, while the check_
false(x) denotes the executing action when the sensing
state is false.
The goal for robot is in room “R501”, so the four
places to represent the goal marking is: Mg = In(“R501”),
D, D, D }, in which D is any value.
Using the constructing algorism of CPNI net system
for the office instance, the simulation result is showed in
Figure 4 using CPNTools [8].
The simulation result is shown in Figure 4, the CPNI
net system is at the end state, the token in the place In is
“R501”, the token in the place AT is “DA1”, and the
robot has realized the goal.
The action sequence showed in place Action-Sequence
is showed as: 1“go(DA3),check_true(DA3),enter(Alley),
go(DA2),check_true(DA2),enter(R502),go(D12),check_
false(D12),go(DA2),enter(Alley),go(DA1),open(DA1),
enter(R501)”,
From the action sequence place we can conclude:
when the sensor robot go to the unknown state door such
as “DA3”, the robot will use the sensor to sense the door
state, and get the state of the door is not closed, so the
state of door “DA3” is updated, and a token “-DA3” is
flowed to the place Closed. When the robot go to the door
D12, then the sensing action check_false(D12) happened,
so the robot can not go to the goal room through the door,
therefore, the robot re-plan to the door D12, and finally
searched a path from the initial state to the goal state.
6. Conclusions
This paper does some tries in applying sensor in the ro-
bot planning and resolves the robot planning in income-
plete environment. Compared to the former work in the
literature [3-5,9], our paper does some tries to represent
robot planning in incomplete environment, which is real-
ized by divided the actions to two sorts, one is external
action which the robot used to change itself and envi-
ronment state, and the other is the sensing action which
the robot used to sense the unknown environment state.
The next work is to use hierarchical Petri net to represent
robot planning to solve the state explosion problem.
REFERENCES
[1] R. Reiter, “Knowledge in Action: Logical Foundations
for Specifying and Implementing Dynamical Systems,”
MIT Press, London, 2001.
[2] C. Y. Yuan, “The Principle and Application of Petri Net,”
Electronic Industry Press, Beijing, 2005
[3] P. F. Palamara, V. A. Ziparo, L. Iocchi, et al., “A Robotic
Soccer Passing Task Using Petri Net Plans,” Proceedings
of 7th International Conference on Autonomous Agents
and Multiagent Systems, Estoril, 2008, pp. 1711-1712.
[4] F. Silva, M. Castilho and L. Kunzle, “Petriplan: A New
Algorithm for Plan Generation,” Proceedings of
IBERAMIA/SBIA, Spinger-Verlag, Brazil, 2000, pp. 86-
95.
[5] V. A. Ziparo and L. Iocchi. “Petri Net Plans,” Fourth
International Workshop on Modelling of Objects, Com-
ponents, and Agents, Roma, 2006, pp. 267-290.
[6] Y. Jin and M. Thielscher, “Iterated Belief Revision, Re-
vised,” Artif Intell, Vol. 171, No. 1, 2007, pp. 1-18.
doi:10.1016/j.artint.2006.11.002
[7] S. Sardina, G. De Giacomo, Y. Les-Perance, et al., “On
the Semantics of Deliberation in Indigolog-from Theory
to Implementation,” Annals of Mathematics and Artificial
Intelligence, Vol. 41, No. 2-4, 2004, pp. 259-299.
[8] CPNTools, “A Computer Tool for Colored Petri Nets,”
2008. http://www.daimi.au.dk/CPNTools/
[9] Y. S. Liu, S. Zhong and Y. Z. Zhan, “A Model for
Representing Reasoning about Actions Based on Colored
Petri Net,” Journal of Jiangsu University, Natural Science
Edition, Vol. 31, No. 3, 2010, pp. 335-338.