ASP Planner

Clingo Interface

Observable Fluents

This sections lists all observable fluents and there definitions:

1. loc
   • looks up conversion from a discretized world space to logical location conversion
   • There is a small tool that constructs this conversion
   • returns self location
2. open, n_open
   • The robot path plans (but does not execute) between 2 points on opposite sides of the door and returns whether the door is open based on whether the plan succeeded. The planned solution needs to be within a reasonable multiple (~2-3) of the euclidean distance between the 2 points.
   • The global understanding of the world map is used for sensing the door. In this global understanding, all doors are initialized to open. The robot will return open, n_open for doors it cannot see at the current moment as well.
   • As the robot moves around, it will update the global map. This means that it's understanding of a particular door being open can change even if it was not trying to approach the door, but simply saw the space through its sensors.
3. beside, n_beside
   • When explicity sensed, beside is returned true if the robot is within 0.5 meters of the door (rough heuristic), otherwise n_beside is returned. This gives no guarantee that the robot will be at most beside 1 door.
   • This is returned true whenever approach and gothrough a door are called (for that door) and the action succeeds. In that case, all other doors are returned as n_beside. If the action does not succeed, then proximity to all doors is computed based on location.
4. visited
   • The interface does not handle this well as of right now.
   • This fluent is returned once the goto action is executed. I am not sure how to sense it.
   • TODO: Any thought on how to handle this better?
   • There is no need to sense it so far in our application (Fangkai)
5. ploc
   • fluent stating object is at location
   • currently published when an explicit sense action is called asking the user to supply a location.

Interface Actions

There are 3 types of calls you can make to the interface:

• Action Request
• Sense Request
• Evaluate Plan Cost

Action Requests

The following actions are available. All actions are blocking and only return back when the task succeeds.

1. approach <door_x>
   • door_x needs to be valid. One side of door_x should be in the same logical location as the robot.
   • executes a navigation task to the side of door_x in our current logical location, attempting to face door_x
   • returns loc, open/n_open door_x, beside door_x (on success), n_beside (all other doors, on success).
   • beside and n_beside are sensed if the navigation task fails. TODO: Should this behaviour be any different?
2. gothrough <door_x>
   • exactly same as approach, but executes a navigation task to the side of door_x not in our current logical location. This attempts to face away from the door.
3. callforopen <door_x>
   • continuously senses if a door is open or not. If a door is not open, it displays a message asking the user to open the door.
   • waits 30 seconds for the user to open door. Returns open and n_open based on whether the door was successfully opened.
   • TODO: in case of failure, should there be some other way of communication that we were unable to open the door?
4. goto <random_string>
   • TODO: this is poorly implemented. Simply displays “Hello random_string!!” to the screen and returns visited <random_string> as a sensed fluent. There is no failure mode.

Sense Request

The following sense actions are supported:

1. open door_x
   • The robot explicitly senses an open door, and returns open/n_open door_x. For now, there is no unavailable/unknown option.
2. beside door_x
   • The robot explicitly senses proximity to a door using a 0.5 m heuristic, and returns beside/n_beside door_x. For now, there is no unavailable/unknown option.
3. ploc
   • The gui asks for the location of and checks whether the location is a valid location
   • if the location is valid, a fluent is returned as ploc(, location)

TODO: I am not sure how sense(visited) is supposed to be handled.

Evaluate Plan

Plan evaluation is done based on a supplied list of interface actions. The list needs to in sequence. The returned cost is an approximate measure of path distance in meters. Actions are evaluated as follows:

1. approach
   • The robot plans from previous end point in plan to the approach point to the door.
   • The distance of the path is added to the cost
   • If this is the first action for the plan, the plan is evaluated from the current location of the robot to the approach point
2. gothrough
   • The robot takes the euclidean distance from previous end point in plan to the through-door point for the door. This is done for the time being to ensure that the door being closed does not skew the normal measurement of euclidean distance. This assumption is not a bad one as gothrough should only be called once the robot has approach a door.
3. all other actions have no cost

Answer Set Programming Encoding

Commonsense knowledge about domains, effects of actions and fluents are encoded in the language of answer set programming (logic programming), under stable model semantics:

  M. Gelfond and V. Lifschitz, The`` ``stable`` ``model`` ``semantics`` ``for`` ``logic`` ``programming， 1988.

Most of the encoding principle follows

  Joohyung Lee, Vladimir Lifschitz and Fangkai Yang, Action`` ``Language`` ``BC:`` ``Preliminary`` ``Report， 2013.

Floor Plans and Residents in GDC North Wing (3rd floor)

We encode the information of corridor, offices, and doors in GDC north wing, and the persons that are assigned to the offices. For the current submitted code, we only limit the floor plan to 4 faculty offices, 4 people, but it can be trivially generalized to formalize the whole north wing, by adding more facts.

This part also formalizes commonsense knowledge about the accessibility of rooms, such as by rule

 acc(X,Y,cor) :- room(X),door(Y),hasdoor(X,Y).  acc(Z,Y,X) :- acc(X,Y,Z).

TODO: add facts for complete floor plans and all residents of north wing for a large scale test.

Knowledge of the Residents

We encode the knowledge of robots about “who knows what”. This is important for the robot to acquire knowledge by asking the right person. For instance, we formalize that Stacy Miller knows where is Raymond Mooney. If the robot goes to Ray's office but don't see him there, he can then go to Stacy's office to ask about it.

This part of formalization is currently very simple, due to a very simple task to perform: we only formalizes Stacy knows where is Ray:

  knows(stacymiller, ploc(raymooney)).

TODO: As we are going to implement more complicated task, more facts can be added.

Effects of Actions and the Change of Fluents

This section lists all time-dependent fluents that are formalized.

Fluents

1. open(X,I), n_open(X,I):
   • X is a door, I is a time label
   • it denotes the status of the door at time I
   • it is an inertial fluent
   • these two fluents may not hold altogether because they represent complementary information, but they can be missing altogether, denotes the robot does not know the value.
2. inside(X,Y,I), n_inside(X,Y,I)
   • X is a person, Y is a room, I is a time label
   • it denotes at time I, X is in Y or not.
   • it is an inertial fluent
   • these two fluents may not hold altogether because they represent complementary information, but they can be missing altogether, denotes the robot does not know the value.
3. beside(X,I), n_beside(X,I):
   • X is a door, I is a time label
   • it denotes if the robot is beside door X at time I or not.
   • it is an inertial fluent
   • these two fluents may not hold altogether because they represent complementary information, but they can be missing altogether, denotes the robot does not know the value.
4. at(X,I):
   • X is an room (including corridor), and I is a time label
   • it denotes the location of robot is X at time I.
   • it is an inertial fluent with functional property (the robot's location is unique and always exists, and the robot knows it)
5. visited(X,I), n_visited(X,I)
   • X is a person, and I is a time label
   • it denotes at time I, the robot visits person X, or not.
   • it is not an inertial fluent. By default, the robot assumes he is not visiting a person (that means, visited holds positive value only if the robot is visiting that person)

Note:

• Complementary fluents beginning with “n_” can also be replaced using strong negation “-”, and dropping the consistency constraints.
• Commonsense law of inertia for boolean fluents (that is, all above inertial fluents except “at”), follows the representation with strong negation, for example,

  open(X,I+1) :- open(X,I), door(X), not n_open(X,I+1), I<n.   n_open(X,I+1) :- n_open(X,I), door(X), not open(X,I+1), I<n.

• There is no completeness constraints for the complementary pair of fluents, like

  :- not open(X,I), not n_open(X,I), door(X), I<n.

• The above formalization is different from what is proposed in (Lee, Lifschitz and Yang, 2013), in particular, the first semantics of BC where strong negation is not used. Complementary pair of boolean fluents must be introduced in this formalization for the reason that it represents 3-value state of robot's belief: know positive, know negative or don't know. In order to accommodate the third case (don't know), completeness constraints are also dropped.

Actions

Actions are divided into sensing actions and nonsensing actions. Nonsensing actions are those such that by performing them, it changes the state of the world, and projects the robot's belief to next time instance. Sensing actions are those such that by performing them, it changes the robot belief state (usually by adding more information) but does not change the state of the world.

Actions may not be executed concurrently. All actions are exogenous.

Nonsensing Actions

1. approach(X,I)
   • X is a door, and I is a time label
   • executing approach(X,I) lead to beside(X,I+1).
   • it is not executable if the robot is at Y, and door X is not connected to Y or beside(X,I) holds, or n_beside(X,I) is unknown.
   • TODO: the action is not executable when the robot does not know beside(X,I) as well, which is not present in the current encoding. Should Fix.
2. gothrough(Y,I)
   • X is a door, and I is a time label
   • executing this action under the condition of at(X,I), acc(X,Y,Z) leads to at(Z,I+1).
   • the action is not executable if Y does not lead to anywhere from X, or the robot does not know if open(Y,I), or beside(Y,I).
3. goto(X,I)
   • X is a person, I is a time label
   • executing this action lead to visited(X,I), and cancel the value of beside(D,I) (that means, if the robot goto a person from a location beside the door, than after visiting that person the robot is no longer beside the door).
   • TODO: this logic representation causes a mismatch in its physical implementation: in physical implementation goto does not actually change the location of the robot. Should fix this from the plan executor part.
   • goto(X,I) is not executable if the robot is at(Y) and the person X is not inside Y, where Y is a room, or if the person X is in room Y but the robot is not.
4. callforopen(X,I)
   • X is a door, I is a time label
   • executing this action changes the status of the door from n_open to open.
   • the action is not executable if the robot is not beside(X,I), or the door is known to be open, or the robot does not know if the door is open or not.

Sensing Actions

There is only one sensing action: sense(X,I), where X is a “sensing fluent name”, and I is a time label.

Details of the effects of sensing actions are listed as follows

1. sense(open(X),I)
   • X is a door, I is a time label
   • executing this action, the robot gets the value of open(X,I+1) or n_open(X,I+1)
   • this action is not executable when the robot does not know beside(X,I), or knows n_beside(X,I), or knows open(X,I), or knows n_open(X,I)
2. sense(beside(X),I)
   • X is a door, I is a time label
   • executing this action, the robot gets the value of beside(X,I+1) or n_beside(X,I+1)
   • this action is not executable when the robot knows the value of beside(X,I) or n_beside(X,I)
3. sense(ploc(X),I)
   • X is a person, I is a time label
   • executing this action, the robot gets the value of inside(X,Y,I+1) where Y is a room
   • this action is not executable if visited(Y,I) holds for at least one person Y, or visited(Y,I) holds for some Y, but knows(Y,inside(X)) does not hold.

Note: in (Lee, Lifschitz and Yang, 2013) there is no sensing actions.

Initial State

There is no need to represent initial states in the logic program. It is obtained from the sensors and grounded into logical symbols.

Note: this is different from what is proposed in (Lee, Lifschitz and Yang, 2013), where choice rules for initial states are used to make the initial state completely determined.

Goal State

Goal state are encoded as constraints. However, since robot can accept several goals, it is encoded in a slightly more sophisticated way.

1. goal(X,I)
2. X is a label of the goal, and I is a time label
   • the goal with label X is achieved at time label I
   • if a goal is achieved at time I, then it remains achieved afterwards
   • at time n (the maximal steps), each goal must be achieved for some I.

Plan Generation, Observation and Replanning

Plan Generation by Optimistic Estimation

Different from traditional planning and reasoning about actions where the world is completely described, in this application formalized by logic program, plan is generated from an initial state with incomplete information. This is achieved by sensing actions. During plan generation, sensing actions are used to perform an “optimistic estimation” for the incomplete information to contribute to obtain an initial plan. The initial plan may not correctly correspond to the state of the world, and will be further revised when these information become available.

For instance, assume the robot is in the corridor, and wants to go to office o3_508. In order to obtain a complete plan, he needs to know if he is beside the door, and if the door is open. Since these informaiton is not available at the time of initial plan generation, he will use sensing action to provide an estimation, and generate the following plan:

 sense(beside(d3_508),0) sense(open(d3_508),1) gothrough(d3_508,2)

And his belief state contains the following information:

1. After executing sense(beside(d3_508),0), he estimates (optimistically) that he is beside d3_508.
2. After executing sense(open(d3_508),1), he estimates (optimistically) that the door is open.

Based on this optimistic estimation, the robot gathers enough information to complete the generation of the next action gothrough(d3_508,2) so that he enters office o3_508.

Sensing, Execution Monitor and Replanning

After the initial plan is generated, it is sent to plan executor for execution, and when sensing actions are executed, the robot will confirm or retract his initial estimation. If the initial estimation coincide with the real sensing results, then there is no need to replan; otherwise, replan is called. In this way, plan generation is interleaved with execution.

In the above example, the robot will send action

  sense(beside(d3_508),0)

to the executor. The executor will sense the environment and returns it to the planner. Since the robot is in the corridor not necessarily beside d3_508, the returned result is

  n_beside(d3_508,1)

This information contradicts with the robot's estimation

  beside(d3_508,1)

leading to a replan to be called. The new plan is as follows:

  approach(d3_508,0) sense(open(d3_508),1) gothrough(d3_508,2)

In the new plan, the robot will approach to the door. The plan proceeds following this cycle until the goal is achieved.

Related Work and References

The method of interleaving plan generation and execution is similar to the idea presented in the following paper:

  Peter Stone, Manuella Veloso, “User-guided`` ``Interleaving`` ``of`` ``Planning`` ``and`` ``Execution”, 1996

Sensing action is formalized in

  Tran Cao Son, Chitta Baral, “Formalizing`` ``sensing`` ``actions`` ``--`` ``A`` ``transition`` ``function`` ``based`` ``approach”, AIJ(2001)

Offline conditional plan generation is investigated in

  Tran Cao Son, Phan Huy Tu, Chitta Baral, “Planning`` ``with`` ``Sensing`` ``Actions`` ``and`` ``Incomplete`` ``Information`` ``Using`` ``Logic`` ``Programming”, 2004

Environment is also sensed every time after an action is executed. The sensors will return all obtained results to the planner. The planner will do “reality check”, by comparing if any observed results is different from the projected belief. If any incompatibility is determined, a replan is called.

The plan-execution monitor-replan cycle is similar to the architect proposed in

  Marcello Balduccini, Michael Gelfond, “The`` ``AAA`` ``Architecture:`` ``An`` ``Overview”, 2008

and

  Ezequiel Antonio Quintero, Ángel García-Olaya, Daniel Borrajo, Fernando Fernández, “Control`` ``of`` ``Autonomous`` ``Mobile`` ``Robots`` ``with`` ``Automated`` ``Planning”, 2011

Implementation

The whole plan-monitor-replan cycle is implemented by a Python script that interacts with answer set solver clingo and clingo-gui interface. To run the planner, the commandline format is:

  $.\planner.py   

The domain description corresponds to the logic program encoding of the domain. The file containing initial state is empty, because the initial state is obtained by querying the sensor. Query is a list of logic program rules that specify the task.

Demo Up to July 14

Up to July 14, the following task can be demonstrated in simulation environment:

1. Initially, the the robot is in the corridor, and he can only observes his location.
2. The robot knows the location of Peter and Stacy, but does not know the location of Ray. The robot knows Stacy knows where is Ray
3. goal: visit Peter, and visit Ray

The result demonstrated is: the robot will visit Stacy first, to ask about the location of Ray, and visit Ray, and then visit Peter.

Future Work

1. Fixing some bugs in the navigation module and demo in Segway robot. (Piyush)
2. Incorporating the plan cost evaluation for better routing cost and avoiding detours. (Fangkai)
3. Theoretical studies about the methodology for formalizing dynamic domain and planning under incomplete information with sensing. (Vladimir, Fangkai)
4. Sensing action as a way to do hierarchical planning in logic programming (Fangkai)
5. Elaborate the domain into more interesting and complicated Task. we can easily generalize the current demo to a general-purpose delivery robot. The robot accepts a set of requests to deliver items to different people, including coffee, documents or other personal items. The robot may know where these persons and items are, but if not, he will try to find the person, just like what is shown in current demo, but the robot will need to revise his plan regarding to the new requests that come online. Also, some tasks are more important than the others that the robot should finish as soon as possible, rather than be delayed by later requests. So the cost evaluation of a plan is crucial and more sophisticated in this case. (Piyush, Fangkai)
6. Coffee delivery from the Cafe downstairs