progress_note_2021_07_21

Progress notes of 21st July 2021

Author: Jérémy Turi
Date: 21/07/2021

Introduction

The Refinement Acting Engine is an acting engine first described in Planning and Acting from Ghallab & Co. A first version has been developped by Sunandita in python. This version integrates a first prototype of RAE working in simulation. The select method to refine a task was using RAEPlan, UPOM or UPOM with learning capabilities. The goal of my thesis is to work from operationnal models to generates plans using planning technics, and then executes the plan. In our scenario, planning is continuously working online in parallel of the execution. Previous works exist combining both approches to maximise long-term utility and prevent deadlock (Propice-Plan, FAPE, others?) The first step has been to look at the state-of-the-art in term of executing engine and their languages. From this preliminary search, the choice has been made to base the RAE Description Language (RAEDL) on Scheme. Once the language has been defined, we used it to build RAEDL on top of it. RAEDL is used to describe domains and the environment (as special functions and initial facts that can be asserted).

Todos

Describe the scheme interpreter briefly
- Basic structures : LValue, LError
- Core operators
- How library systems works
- How macros work
- How to run it from the project
RAE Architecture
- Main algorithm
- How threads communicates (diagram)
- TaskHandler
- Async/Await system
- Action Status update and check
RAEDL
- Elements of description: facts, actions, tasks, methods
- Functions to define the environment
Using RAE:
- How to launch it, monitor
- trigger a task
- link with godot
What is still to be done:
- check proper tail recursion (some stack overflow to be checked, maybe caused by the construction of recursive environments)
- Implement agenda for methods
- Implement error handling when a method fails and retry
- Implement enumeration of applicable methods
Future work for RAE V2.
- Generation of chronicles/ppdl problems/hddl problems from operationnal models to call a planner online (aries/fape)
- STN network for actions.

Outline

A Scheme Interpreter in Rust
Implementation and adaptation of the RAE Algorithms
RAE Description Language
Overview of the global progress

A Scheme Interpreter in Rust

Scheme is derived from the functionnal language Lisp.Peter Norvig made a tutorial to implement a basic version in Python. The Rust implementation is based on Lis.py and Lispy.py (the second version integrates advanced features). The main idea developping our own Scheme Interpreter is first, to better understand how an interpreter works and how Scheme works. Another good point developping our custom interpreter is that we can add special features that we want to implemented.

A first glance at the Scheme Interpreter.

A scheme interpreter is a REPL (Read-Eval-Print-Loop). It takes from the standard input a string, parse it to transform it into an SExpr (or LValue in our case) and then evaluates it in an environment.

An environment contains bindings between symbols and LValues. Interpreting an expression in lisp can either returns a LValue or an LError

LValue

The LValue is the basic object used in our intrepreter to represent any kind of object. In rust it is an enumeration with the following kinds:

Number: any kind of number. We distinquish three kinds of numbers: Integer, Float and Usize. Usize is a particular type that can only be built by internal functions.
Symbol: A string containing a unique word
String: Mainly use for debugging and pass messages.
Character: A simple character.
Nil: Represent both boolean value false and the empty list
List: A list LValues
Map: A HashMap of LValues. This type is not originally in the basic structures of scheme. However it is of great interest for us to be implemented in the core functions, we added it the basic types.
Fn: Pointer to functions with low level computation (i.e. here rust).
MutFn: Same as Fn but it can modify objects.
Lambda: Lambda function that can be called using other kinds of LValues.

LError

Some errors can occurs evaluating LValues:

WrongType: Error that his raised when the wrong kind of LValue is received.
```
>> (* 3 t)
LI>> error: In LValue::mul, t: Got Symbol, expected Number
```
NotInListOfExpectedTypes: Same as wrong type, but several types could have been ok.
```
>> (length 10)
LI>> error: In length, 10: Got int, expected [List, Map]
```

WrongNumberOfArgument: The number of arguments is not in the expected range

>> (- 10 25 3)
LI>> error: In -, "(10 25 3)": Got 3 element(s), expected 2

UndefinedSymbol: The symbol as no binding in the environment.
```
>> (set! x 10)
LI>> error: In set!: x is undefined
```
SpecialError: Special error with formatting string in function of the context. Mainly used for internal errors. Special Errors should not occur and raise a bigger programming problem that needs to be adressed.
ConversionError: Conversion Error when transforming a LValue to its inner type (Internal Error). Should not occur if functions are safe and type verifications are done.

Functions

Scheme has two kinds of functions. Core operators that are optimized and can mutate the environment, and pointer to functions.

Core operators

Core operators are the very basic functions present directly in the eval function:

Define : binds a symbol to a LValue

(define x 10); the symbol will be bound to the value x

Set: modify the value of a symbol already defined in the environment.

(set! x 12); x previously bound the value 10 will now have the value 12

If : Basic conditional structure. Evaluates an expression that returns a boolean, executes two differents branches in function of the result.
```
>> (if (> 3 10) (+ 3 3)  (* 10 5))
LI>> 50
```
Begin: Evaluates a list of expressions and return the result of the last.
```
>> (begin (define x 10) (define y 20) (+ x y))
LI>> 30
```

Eval: Explicitely evaluates an expression.

'(* 3 3)
LI>> (* 3 3)
(eval '(* 3 3))
=> 9

DefLamda: creates a lambda expression.
```
>> (define square (lambda (x) (* x x)))
; defines a new lambda in the environment binded to symbol 'square' 
>> (square 5)
LI >> 25
```
There is two ways to define the arguments of a lambda. (lambda args body) will consider args as a list of arbitrary length when (lambda (x y) body) will wait for two arguments that will be bound to x and y.

DefMacro: defines a lambda that format lisp code

(defmacro cadr (lambda (x) `(car (cdr ,x))))
(cadr '(3 4)); <=> (car (cdr '(3 3)))
LI >> 4

Async & await: Evaluates asynchronously an expression. Returns a pid (usize) of the task. The pid can be used with await to get the result of the evaluation.

>>(await (async (*3 3)))
LI>> 9
;we can split await and async to launch several async blocks and await on the results later
>> (let ((x (async (* 3 3))); x is the pid of the async block
       (y (async (* 4 5)))); y is the pid of the async block
      (+ (await x) (await y)))
LI>> 29

Quote: Prevent evaluation of the expression
```
>>(quote (*3 3))
LI>> (* 3 3)
```

QuasiQuote & UnQuote: Creates a block in which everything is quotted except unquotted expressions:

>> (quasiquote (3 (+ 6 7) (unquote (- 2 1)))))
LI>> (3 (+ 6 7) 1); the unquotted expression has been evaluated

Environment

In Scheme, an expression is evaluated in an environment in which symbols have meaning. For example a symbol can have a value or be a function. Unless the expression is quotted, the first element of a list should be a function (lambda, lfn, lmutfn or core-operator).

Root Environment: provides basic functions
- env: returns the list of all elements defined in the environment
- get: function to get an element from a list of a map (for map objects, prefer get-map)
- map: constructs a map.
- list: constructs a list.
- car: returns the first element of a list, nil if the list is empty.
```
>>(car '(3 4 5))
LI>> 3
```
- cdr: returns list without the first element, nil if the list has one element.
```
>>(cdr '(3 4 5))
LI>>(4 5)
```
- last: returns the last element of a list.
```
>>(cdr '(3 4 5))
LI>>5
```
- cons: creates a cons of two elements
```
>> (cons 3 nil)
LI>> (3)
>> (cons nil 3)
LI>> (nil 3)
>> (cons 4 '(3))
LI>> (4 3)
>> (cons '(4) '(3))
LI>> ((4) 3)
```
- get-map: get the value inside a map
```
>> (define m1 (map '((test . 10))))
>> (get m1)
LI>> test: 10
>> (get-map m1 test)
LI>> 10
```
- set-map: returns a map with the new value inserted.
```
>> (define m1 (set-map m1 '(twenty . 20)))
>> (get m1)
LI>> twenty: 20
test: 10
```
- basic math functions:
  - add (+)
  - sub (-)
  - div (/)
  - mul (*)
  - eq (=)
  - gt (>)
  - ge (>=)
  - lt (<)
  - le (<=)
- type verification
  - lambda? : returns true if the LValue is a lambda.
  - integer?: returns true if the LValue is an integer.
  - float?: returns true if the LValue is a float.
  - nil?: returns true if the LValue is nil.
  - bool?: returns true if the LValue is a boolean.
  - symbol?: returns true if the LValue is a symbol.
  - fn?: returns true if the LValue is a function.
  - mut-fn?: returns true if the LValue is a mutable function.
  - quote?: returns true if the LValue is a quote.
  - map?: returns true if the LValue is a map.
  - list?: returns true if the LValue is a list.
  - pair?: returns true if the LValue is a list with at least one element.

All aboves functions are defined in the root environment.

Some macros and lambdas are also defined for syntactical sugar.

Macros:

caar => (car (car ..))
cadr => (car (cdr ..))
cdar, cddr, cadar, caddr, and lot others added in function of the use.
and, or and !=
let and let*: Used to evaluate a code with locally binded variables. The difference lies in the possibility to bind variables in function of previous bindinds with let*
```
>>(let   ((x 3)
       (y 4))
      (+ x y))
LI>> 7
>>(let* ((x 3)
       (y (x +1)))
      (+ x y))
LI>> 7
```

cond: equivalent to successive if else if ... else

>> (define weather 
  (lambda (x)
      (cond ((< x 10) '(It is cold!))
          ((< x 20) '(It is cool!))
          ((< x 30) '(It is warm!))
          (else '(It is hot!)))))
>> (weather 10)
LI>> (It is cool!)
>> (weather 9)
LI>> (It is cold!)
>> (weather 25)
LI>> (It is warm!)
>> (weather 36)
LI>> (It is hot!)

await-async => (await (async ..))
apply : applies a function to a list of args
```
>> (apply + (10 6))
LI>> 16
```

Lambdas:

zip: zip elements of two lists in pairs

>> (zip '(1 2 3 4) '(5 6 7 8))
LI>> ((1 5) (2 6) (3 7) (4 8))

unzip: undo a zipped list.

>> (define zipped (zip '(1 2 3 4) '(5 6 7 8)))
>> zipped
LI>> ((1 5) (2 6) (3 7) (4 8))
>> (unzip zipped)
LI>> ((1 2 3 4) (5 6 7 8))

mapf: maps a function to a list of argument

>> (mapf weather '(9 15 25 36))
LI>> ((It is cold!) (It is cool!) (It is warm!) (It is hot!))

Modules: In addition to the basic functions, we can add modules linked to a specific context that can handle special objects.
- DOC: provides a unique function help that prints the whole help if called withour arg. Prints verbose help of symbol if called with a symbol.
- IO:
  - print: print a LValue
```
>> (print test)
test
```
  - read: reads an expression from a file.
```
>>(read <path-to-file/name-file.extension>)
```
  - write: write a LValue to a file.
```
>>(write <path-to-file/name-file.extension>)
```
- Math: provides advanced math functions as sin, cos, rand-int-in-range and rand-float-in-range that generate respectively a random integer and a random float from a range of number:
```
>> (rand-int-in-range 0 10)
LI>> 6
>> (rand-float-in-range 0 10)
LI>> 1.875527591323538
```
- Utils: provides a bunch of utility functions:
  - rand-element: pick a random element from a list
```
>> (rand-element '(10 2 6))
LI>> 2
```
  - enumerate: enumerates all possible sets of combination from several lists.
```
>> (enumerate '(1 2) '(3 4) '(5 6))
LI>> ((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6))
```
  You now have a brief overview of the Scheme Interpreter.
  
  How to run the Interpreter.
  
  From the project you can run an executable without rae libraries loaded:
```
cargo run --bin lisp_interpreter
# to enter debug mode
cargo run --bin lisp_interpreter -- -d
```
  RAE
  
  The Refinement Acting Engine (RAE) is based on the Algorithm first described in Ghallab, co 2016 (Book Acting and Planning). Several articles expanded the algorithm:
- Refinement Planning and Acting, 2017
- Acting and Planning Using Operational Models, 2019
- Decentralized Refinement Planning and Acting, 2021
- Deliberative acting, planning and learning with hierarchical operational models, 2021
- TODO: Complete lists of State of the Art concerning RAE, APE, etc.
  
  RAE Architecture
  
  The executable of RAE is decomposed in several processus and asyncrhonous tasks. The following diagram gives an overview of the Architecture and how tasks are communicating, what object is shared between tasks and threads etc.
- The main process is the process that is launched with the command cargo run, i.e. unnamed_superviser.
  
  At initialisation it launches a repl that communicates via a channel with the Scheme Interpreter task.
  
  This task await on a channel to receive raw (str) Scheme expression, that will be parsed, expanded and evaluated.
  
  The result is then sent back to the REPL to be printed on stdout. Other processes can call the Scheme Interpreter to Evaluate Expressions.
  
  However the return of the value is only available for the REPL Task (To be implemented later if future case need this feature...)
- The task RAE is launched via the REPL with the command (rae-launch). It will successively launch rae_main and the platform. In our case godot3 via command line loaded with an hardcoded scenario and options. The platform godot then opens a tcp connection to receive state updates and action status updates.
- The objects RAEState and Status are shared between the different tasks (using Arc).
  
  Main algorithm
  
  The main algorithm of rae receives job via a channel. A job is lisp code that will be evaluated in RAE environment. Here is a simple view of how RAE works. It has been extremly simplified in its main algorithms as most of the reasoning part is done during evaluation and in RAEExec context.
```
rae_main(context: RAEEnv)
  loop:
      new_job <- job_receiver
      spawn(progress(new_job, RAEEnv.env))
  end

progress(job: Job, env: LEnv)
  eval(job, env)
```
  TaskHandler
  
  The TaskHandler is a simple way that I found to stop all tokio tasks spawned that are looping during the whole process lifetime. In the REPL, when it receives a CTRL-C entry, it calls task_handler::end_all(). Every task can get the end signal by calling task_handler::subscribe_new_task. It returns a broadcast receiver. Here is one example of how to use it. We recommand to use tokio::select! has it awaits concurently several futures and executes the code of the first received future. In this example it loops and awaits on two futures given by receiver.recv() that awaits on messages to send to godot, and end_receiver.recv() that awaits on a message from the task_handler. If the task_handler broadcast the end message, the task breaks it main loop and end the task process by ending the function.
```
let mut end_receiver = task_handler::subscribe_new_task();
loop {
  tokio::select! {
      command = receiver.recv() => {
          let command = match command {
              None => break,
              Some(s) => s
          };
              //println!("new command to send: {}", command);
          let size = u32_to_u8_array(command.len() as u32);
          let msg: &[u8] = &[&size[0..4], &command.as_bytes()].concat();
          match stream.write_all(msg).await {
              Ok(_) => {}
              Err(_) => panic!("error sending via socket"),
          }
      }
      _ = end_receiver.recv() => {
          println!("godot sender task ended");
          break;
      }
  }
}
```
  Executing commands in RAE
  
  In RAE, the goal of the engine is to find methods to refine a task. Once the methods has been found, it will be executed. The body of a method is an operationnal model that contains richer control structures than descriptive models. To execute a command in RAE. There is two functions:
- (rae-exec-platform <label> <params>): sends the command to the platform and returns the pid of the command.
- (rae-await <pid-command>): Check updates of the status of the action. Returns true if the action is a success, and nil if the action is a failure. (Note: rae-await should be renamed to avoid confusion with await). Here is an example of construct to execute a command.
```
(rae-await (rae-exec-command pick robot0))
```
  How to define a platform in RAE
  
  RAE needs a platform to execute commands and get the new state resulting from the action. To define a Platform, the trait RAEInterface needs to be implemented. This trait is composed of the following methods:
- init(&mut self, state: RAEState, status: ActionsProgress): Called during initialisation steps of RAE. In gives Arc references to the platform, so it can use it directly to update state and action status. (Note: This function may change)
- exec_command(&self, args: &[LValue], command_id: usize) -> Result<LValue, LError> : Executes a command on the platform. It receives the keys of the command via the args, and the local command_id.
- cancel_command(&self, args: &[LValue]) -> Result<LValue, LError> : Cancel the command wich command_id is supposed to be wrapped inside args. The command_id is supposed to be the internal one (In godot, two command_id exists. One that is used by RAE, and the other one inside Godot Engine. Be careful while using command_id. Assure yourself to work with the right ones.) (Note: Not yet used, supposed to work in godot at least )
- get_state(&self, args: &[LValue]) -> Result<LValue, LError>: Get the whole state of the platform. In godot implementation, args are used to get only part of the state. You can pass the arguments static or dynamic. (Note: The field inner_world is supposed to be used only by RAE)
- get_state_variable(&self, args: &[LValue]) -> Result<LValue, LError>: Get the value of a state variable. The key is contained inside args. Here is an example
```
(rae-get-state-variable robot.velocity robot0)
;return the velocity of the robot as a float
```
- get_status(&self, args: &[LValue]) -> Result<LValue, LError>: Return the status list of all the actions if args is empty, or a specific status if args contains the id of an action.
- launch_platform(&mut self, args: &[LValue]) -> Result<LValue, LError>: Launch the platform, i.e starts the process and open the communication with the process.
- start_platform(&self, args: &[LValue]) -> Result<LValue, LError>: Start the platform. The implementation of this method suppose that it will start the process and it will be fully operationnal to then open a communication with RAE.
- open_com(&mut self, args: &[LValue]) -> Result<LValue, LError>: Open the communication with the platform. In the godot implementation of this trait, it opens a tcp connection.
- get_action_status(&self, action_id: &usize) -> Status: Get the status of an action.
- set_status(&self, action_id: usize, status: Status): Set the status of an action.
- domain(&self) -> &'static str: Provides the a lisp expression that enable RAE to load the domain. We propose two ways.
  - The first one is to declare the domain as an str that will be compile in the binary.
  - The other one is to write the domain in a file, and load it with the command (read <name-file.lisp>).
  Action Status update and check

RAE Description Language (RAEDL)

This language is built on top of the Scheme language we developped. It is used to define an environment in which RAE can execute tasks and methods. Several elements can be defined:

Describe the environment.

Primitive actions: Primitive actions are defined with a list a symbol. The first symbol is the label of the command, and the rest the labels of the parameters. Parameters are not typed.

(defaction pick ?r)
;defines the action pick that take the parameter ?r

This function creates a lambda that will be stored in the environment with this form:

(lambda (?r) (rae-exec-command (quote pick) ?r))

Tasks: Tasks are abstract objects that needs to be refined in methods in function of the context of execution. A task is defined by a list of symbols corresponding to the label of the task and the labels of the parameters.

(def-task t_navigate_to ?r ?x ?y)
;transformed into a lambda into RAE enviroment.
(lambda (?r ?x ?y) (rae-exec-command (quote navigate_to) ?r ?x ?y))

Methods: Way of refining a task. A method can have the same number or more parameters than the task it refines. If it has more parameters, it needs to define a way to enumerate the list of the set of applicable parameters to the method.

;define a method body
(def-method m_navigate_to '((:task t_navigate_to)(:params ?r ?x ?y)(:body (begin
        (rae-await (navigate_to ?r ?x ?y))
        (rae-await (navigate_to ?r (+ ?x 1) (+ ?y 1)))))))
;define the way RAE will enumerate applicabale sets of parameters for the method.        
(def-method-parameters m_navigate_to '(() ( _ nil)))

;What is defined in RAE environment
-body: (lambda (?r ?x ?y)
        (begin (rae-await (navigate_to ?r ?x ?y))
                (rae-await (navigate_to ?r (+ ?x 1) (+ ?y 1)))))
 -parameters:
 (begin 
         (define eval_params
          (lambda args 
                  (let ((params (car args)))
                           (if (not (null? params))
                            (if (eval (cons (lambda _ nil) params))
                                     (cons params (eval_params (cdr args)))
                              (eval_params (cdr args))) nil))))
                       (eval_params (enumerate)))

State-function: A state function returns the value of fact at a given time. We define a state function by a list of symbols. The first is the label of the state function, the rest the labels of the parameters.

(def-state-function robot.coordinates ?r)
;defines the state function that will return the coordinates of a robot.
(lambda (?r) (rae-get-state-variable (quote robot.coordinates) ?r))

Lambdas: Add a function that will be used in RAE (for example when a part of the code needs to be used several time)

(def-lambda '(go_random (lambda (?r ?l ?u)
                            (let ((x (rand-int-in-range ?l ?u))
                                  (y (rand-int-in-range ?l ?u)))
                                  (rae-await (navigate_to ?r x y))))))

Initial facts: Set initial facts in RAE. Those facts will be stored in the inner world part of the state.

(def-initial-state '((robots . ())(machines . ())(packages . ())))
;example of initial facts that can be defined.

RAE primitives

rae-await: Used in synergy with rae-exec-command to monitor the status of an action.
rae-exec-command: Exec on the platform a command, and returns the id of the action to monitor it.
assert: Add/update a fact in the state.
retract: Delete a fact in the state.
rae-get-state: Return a map of the state.
rea-get-state-variable: Return the value of aa state variable.
rae-get-methods: Return the applicable methods of a task
rae-get-best-method: Return the best applicable method.
rae-cancel-command: Used in synergy with rae-exec-command to cancel a command on the platform.

Using RAE

How to launch RAE.

To launch RAE, you need to use the project https://github.com/Yirmandias/FactBase. Clone the project and run cargo runIt will automatically build and run the right target. Once the REPL is launched, you can use the following commands to monitor, launch rae and trigger tasks.

(rae-get-env):returns the environment of RAE.
(rae-get-state): returns the whole state of RAE. Contains only initial facts if rae is not launched yet.
(rae-get-status): returns the list of status of all actions that have been triggered.
(rae-launch): launch rae. It will also launch the platform.
(rae-trigger-task <label> <params>): trigger a task with instantiated parameters. Launch before triggering tasks.
(rae-trigger-event): trigger an event. Not yet fully defined.

What is still to be done

Check proper tail recursion: A task that is called recursively will provoke in the end stack overflow. In the same way, the function expand provokes on windows stack overflow on too large codes.
Implement agenda for methods: For the moment, we execute methods, without retry mechanism. We need to store instances of methods that have been already tried. When a method fails, we need to try other methods while there is still untried.
Implement enumeration of applicable methods: For the moment, we can only define methods with the same parameters as the task. We need to enumerate instances of methods that are applicable and then choose the best one.
Create jobshop problem

Future work for RAE V2.

Generation of chronicles/ppdl problems/hddl problems from operationnal models to call a planner online (aries/fape)
STN network for actions.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly