Too much effort is being invested in the automated planning field, but this area has been focusing more on improving the performance of search algorithms in an abstract space than on applying automated planning in practice. Among several challenges, online replanning is an open issue. This paper presents PNRD/iPNRD integration in Blocks World Domain in order to create an adaptive control of a robotic arm and passive agents. The procedure is composed of building a Petri space, PNRD, and iPNRD model for each agent, and by integrating their information so that the robotic arm may autonomously order the blocks to the desired final global state, stored previously in each block's RFID tag; comparing logical and physical information, generating a sequence of movements, and executing related actions. Some issues arise because of the dispersed information, physical-logical interface and its constraints, requiring the detection of non-conformant results, optimally solve and realize the required sorting given its partial observability, and sequential movement of one block each time. The feedback from PNRD/iPNRD models with physical positioning can certify the required initial, intermediate and final condition and also check for exceptions, resulting in an adaptive robotic control. This didact example points out where this approach can work with automated planning for a more complex system.
than on improving its models’ predictive capabilities. Planning is easily
formalized, whereas acting is not. There is a clear frontier between planning and
performing, but the borderline between acting and performing is more blurred.
In addition, automated plans are usually a simple packaged input–output
function, although actor’s deliberation functions are difficult to integrate to open and
dynamic environments. Such changes on focus entail two interconnected
principles: a hierarchical structure to integrate the actor’s deliberation function, and
the continual online planning and reasoning throughout the acting process. [
PNRD/iPNRD
PNRD
Each RFID tag can be abstractly identified by a single token on PNRD and
each reader can represent a Petri net (PN) transition. Originally, PNRD was
developed for the identification and monitoring of passive agents, such as
commercial items, parts, logistics units, and physical products. The process that an
object must follow is associated with its behavioral model through Petri net data
structure. Thus, PNRD is a formal data structure grounded in elementary Petri
net which stores Petri net equation parts in RFID components: tag and reader
[
Operationally, along the physical distributed RFID readers, tag data can represent a single marking, and this marking is automated updated during the tag data capture following the matrix equation.
It is possible to evaluate in real time whether the next calculated marking is suitable or not. In this sense, a suitable marking should respect the tag-token bi-univocal unique relationship, it means, each tagged object cannot have any negative component in its marking. Thus, the PNRD exception can assist Edge Computing to solve some issues locally.
A conflict in the PNRD approach arises when the same reader/antenna is
related to more than one transition for the same tag identification and previous
marking. In this case, it is necessary to apply a decision algorithm to define
which transition should be chosen based on additional data or software based on
specific cases [
In the process in question, raw material (p0) is sent to a workstation (p1), and,
after it, the machined part p2 pass throught a specific test p3. If the test approves
the part, it goes to the stock p4. If it is rejected, the piece goes for recycling p5.
If the part does not meet the test, it goes to the rework queue p6, and through a
new machining process and it returns to the beginning of the machined system.
Although t0 and t6 are related to Reader1/Antenna1, both have distinct
previous marking (p1 and p6, respectively), what doesn’t generate a conflict. The
Fig. 2 correspondently adjacent matrix A is presented as following.
PNRD exception can be shown as follow. Initially a part which is a raw with
a given RFID tag. This tag is at p0, corresponds to the initial marking m0 =
[
As the active agents are normally embed with a micro controller, it becomes
impracticable to associate their identification with only one RFID tag, as it is
more reasonable to place an RFID reader in agents similar to mobile robots. The
use of tags to identify strategic points and places of interest within the course
of agents is capable of changing the behavior of these agents. In addition, the
use of passive tags in remote locations to identify locations along tracks without
network and eletric infrastructure, and in environments with sparse power points
proves to be adequate, and technically and economically feasible. Thus, to fit the
PNRD approach in the control and monitoring of active agents, it is necessary
to inverse the storage locations of the components of the Petri net equation. This
approach was called inverted PNRD or iPNRD and it was presented by [
To illustrate the iPNRD, a search and rescue problem, which has been simplified and dealt with on mobile robot stands, is presented in Fig. 3 here are three distinct agents or mobile robots, namely AerialBot, Groundbot and Walker. These refer to aerial robots (a platform capable of filming the workbench), search and rescue robots, and robots emulating users, respectively.
Each agent has different inputs and outputs. In the case of AerialBot, it has
access to images from a camera (view) and the exchange of TCP / IP messages.
The outputs correspond to the movement of motors and the TCP/IP messages.
For Groundbot the inputs refer to contact sensor, ultrasonic sensor and RFID
reader with iPNRD software, in addition to receiving TCP / IP type messages.
The outputs are TPCP / IP messages, motors and data recording in RFID tags
arranged along the workbench. Walker has contact sensors, ultrasonic sensors
and RFID reader with iPNRD as input, as well as motors, access to benchtop
RFID tags and an emergency light to indicate any type of problem (physical
failure or when it is lost). Corresponded Walker iPNRD is shown at Fig. 4.
The adjacency matrix A of Petri net of Figure 4 is as follows:
iPNRD data storages firing vector in tag can also hold the history composed by
the agents Id, timestamps and additional information. This historical data
facilitates the tracking and tracing of Walkers by the Groundbots. This information
is helpful in order to directed search to the region most likely to find the victim,
– States:
– p0: Walker at Petropolis Entrance
– p1: Walker at First Region
– p2: Walker at Second Region
– p3: Walker at Third region
– p4: Walker Teresopolis Entrance
– Transitions and tags:
– t0: Tag 1 at Petropolis Entrance
– t1: Tag 2 at "Castelo do Açu"
– t2: Tag 3 at "Pedra do Sino"
– t3: Tag 4 at Teresopolis Exit
– t4: Tag 1 at Petropolis Exit
– t5: Tag 2 at "Castelo do Açu"
– t6: Tag 3 at "Pedra do Sino"
– t7: Tag 4 at Teresopolis Entrance
reducing search time and, consequently, increasing the chances of rescue.
The route has 4 tags, the first one in the Petrópolis entrance/ exit, the
second dividing the trail into first to second regions, the third spliting the second
to third region, and the last one at the Teresópolis exit/ entrance of the trail.
Note that each tag has a set of transition it is related to depending on what
is the direction of the trail (from Petrópolis to Teresópolis or vice-versa). The
Walker agent w1 is at w01 = [
Fig.5 summarizes how the terms of Petri net matrix equation are associated with the RFID components in both approaches. 2.3
Both PNRD and iPNRD are able to structure the communication between
several agents of a system that makes use of RFID devices, however, until now only
stand alone aplication was presented. Could their integration assist automated
planning adoption in industry? To answer this question it is necessary to show
how PNRD and PNRD can be integrated in an automated planning domain. In
this direction, this paper presents the integration of PNRD and iPNRD related
with Blocks Worlds of 3 components.
Block World in Practice The blocks world is one of the most famous
planning domains in artificial intelligence [
Blocks world planning has been shown to be a difficult problem for finding an
optimal plan, as it is NP-hard in the worst case [
The Blocks World restrictions, actions and possible configurations can be modeled through different paradigms, such as propositional logic, full state space representation or tree expansion. As this domain is didactic in order to present physical informational integration using PNRD/iPNRD, these models have full state representation due to the small quantity of elements, thus the optimal solution can be found using simple graph search algorithms, whose time complexity order is polynomial.
This means that planning for sorting execution is simply about searching through
different PNs to generate the robot driving sequence. The search algorithm of
choice is the BFS (breadth-first search), that will expand all places following a
FIFO (First In First Out) list, this algorithm being optimal for uniform cost arcs
[
Using a heuristic search might give significantly better results for bigger state spaces. If a different paradigm was used, such as tree expansion, the BFS has completeness assurance, but this paradigm is better suited to deal with bigger state spaces, meaning that a heuristic search would outperform the non-informed BFS.
According to [
Sorting can be very challenging depending on the level of automation [
The block PNRD models the relationship of itself with the environment. Depending on arm physical movement, it is possible to identify what block is under another (with a movement from the top to the bottom of a column), or, otherwise, what block is over another (with a movement from the bottom to the top), what is implemented in this work. So, their PNRD model represents which element the referred block stays atop. As an example, block A PNRD model can have three distinct states, A over B (AB), A over C (AC), or A on the table (AT ) and it is presented in Fig. 7. The PNRD topology is composed of 3 places and 6 transitions for each one of the three blocks. An additional information is demanded, each block must inform its expected final state. 3.2
The iPNRD represents the active agent perspective on the world, and as there is only one robot arm, its iPNRD model also represents the whole Blocks World disposition state space. For three blocks, it is possible to represent the logical macro state as shown in Fig. 8, that is the blocks relative positions with 13 distinct states and 30 transitions. As informed in subsection 2.3, there is no logical distinction between A_B_C and C_A_B, but only the reference physical dispositions shown in Fig. 8 are treated in this paper. Each transition refers to a movement of a block, for instance, miX2Y means movement number i of block X to position Y (on table – T or another block). Place identification is following the notation described at subsection 2.2. Through this iPNRD model it is possible to navigate from a state to another, identifying the necessary intermediate states and transitions. Searching in the iPNRD model is similar to a macro state planning, or a discrete state control, which can reach the final state from the initial by firing a correct sequence of transitions. This planning is of higher level because it does not relate directly to the robot kinematic sequence. The movement sequence is generated by searching on the physical level, the Petri Space. 3.3
All blocks PNRD representation must be coherent with the arm iPNRD model and with the Petri Space from the physical system. Places and transitions are related to the other models directly and these relationships can be expressed through tables. It is mandatory to inspect whether the physical arrangement is equivalent to the PNRD and iPNRD representation regarding the initial state. As this case study has a simple model and the whole state space is modeled in a PN, the optimal solution can be found using graph search algorithms. For a more complex model this solution requires a different approach, as an example automated planner integration with iPNRD model.
The proposed method to identify the position of each block on the physical domain is by using the RFID reader placed in the robot grappler. As all the blocks have RFID tags, which gives them an individual unique identity, the reconnaissance of each block and its corresponded position is feasible during a sweep operation.
All blocks identification from PNRD habilitates the identification of iPNRD initial and final state. This means that the blocks current position is identified by tag reading, and this information can be confronted with block’s own state from its PNRD ; and the final state by reading in each block additional data. Summarizing, Petri state (blocks position perceived by robot), and PNRD data are mapped to iPNRD state as presented by Table 1, after a robot sweep operation.
Exception can occur in two ways. In the PNRD level if and only if the Petri state set is distinct from PNRD state set, this means some block(s) was moved from their initial position, as Petri state set has priority over PNRD state set. Consequently the PNRD states must be updated following the physical disposing. Constraints in this exception arise from the restrictions of the physical world and the proposed Blocks World restrictions. There are thirteen different logical dispositions in the iPNRD for three distinct PNRD places for each block. As the mapping is a bijective function with three inputs, having three possible values each, most permutations are invalid having no real transfer to an iPNRD state. The same occurs on the physical layer to iPNRD or PNRD, mathematically many configurations exist, but the physical model constraints the possible configurations.
Another exception can be raised from PNRD desirable state set. There is 13 iPNRD states with specific PNRD state set, for instance, A_B_C = AT ,BT ,CT . If the desirable final state set does not belongs to Table 1 PNRD set, it means that the final state set is unreachable and inconsistency, as example AB, BA, CA, where A is over B, Bis over A and C is over A, what is physically unfeasible. This mapping is bijective, so it admits an inverse. Transitions in iPNRD convert to a sequence of Petri State transition.
A movement command (transition in the Petri State) is converted into a command signal for the robot driver system. This relation is also bijective, however, for the physical robot, the mapping between the path and the static position has an n : 1 relationship, meaning that multiple commands can reach the final position. This paper deals with this issue storing in advance each movement sequence and relating them with a correspondent Petri state transition. 3.4
The first process to solve the Block world consists on recognizing the initial and objective states. Then a sorting engine based on the iPNRD model uses the robotic arm to act, following the Petri state transition movement. The sorting engine is a multi-process composed of solving for the optimal action plan given the original and final global states, respecting the model constraints. This process consists of searching in the iPNRD model for the least amount of transitions. Then it is necessary to map the physical level, in which each transition has an initial and final position. The next step is to search for the least amount of robot movements in the physical model. Afterwards it is necessary to concatenate the actions and to translate them into robot driver command, moving the blocks in the physical world. This multi-process sorting is described in the next section.
After the definition of iPNRD objective and its correspondent iPNRD transitions, it is necessary to generate Petri state sub-goals, meaning, the required initial and final physical place that each involved block must be moved in order to complete a iPNRD transition. Each transition in the iPNRD maps to an unique sequence of Petri Space transitions, as is in Fig. 9. These movements must be concatenated in order to reach the desirable final set, so it is necessary to connect the final place of a sub-goal to the initial in the consequent one. The final step is to convert a Petri space transition to a robot command. The simplest way to perform this task is composed of mapping these transitions into a more easily readable order, converting the concatenated transitions into an driving order string, then it is processed by the robot driver. The robot driver converts the string orders into joint angles and grappler movement by commanding the servomotors.
The implemented solution involves a PC, an Arduino mega microcontroller, RFID components, robotic arm and the three tagged blocks. This interfacing can be done by a range of methods, like serial protocols or intranet. In this paper the means for transmission are the RFID sensor for interfacing the blocks to the microcontroller and serial bus to communicate the microcontroller to the computer. For motor command the microcontroller sends processed signals to move the robot. The system could be adapted to be processed in a monolithic manner or to be further distributed among other agents.
The main idea of the adaptive control is presented in Fig. 10, which shows an PNRD/iPNRD feedback depending on whether there is exception in the process. The sorting process finishes when all steps have been fulfilled correctly. This system can operate independent of supervision, unless an exception that disables the process achievability happens. An example of disabling occurrence is sensorial malfunctioning.
The adaptive control flow starts with an external command to start the operation, such as a supervisor sending a job request.
The system performs a sweep to locate the blocks using the arm and mounted
RFID reader. This sweep starts at C1_4 Petri state and always follows a fixed transition sequence {T 4 ! T 24 ! T 25 ! T 1 ! T 18 ! T 10 ! T 26 ! T 27 ! T 7 toT 20 ! T 16 ! T 28 ! T 29 ! T 13 ! T 23}. The adaptive control algorithm performs the physical inspection reading each discrete position in a column from below to the top, as informed in section 3.1. When the first column is done the next occupied position will be the highest in the second column, then the robot will descend to the lowest point and will perform the scan upward. When all three columns are done the system will process the PNRD data. Then, through the use of Table 1, initial and objective iPNRD states (macro states) are generated by PNRD and Petri space information. A BFS search is performed to find the optimal route in the iPNRD model. In each iPNRD transition a sub-goal search is done to find the set of movements in the Petri space transitions. The movements are concatenated and converted into a string to be fed to the microcontroller robot arm driver. The robotic arm motors respond and the system actuates the blocks until the final command.
A simplified sweep is done to verify if the current state is equal to the desired one through Petri state position, PNRD updates the block next state, as iPNRD changes the system state. In this step, it is verified if the final movement was possible to be executed. If not, it means that another block was moved without robotic assistance to that position, and it raises another exception type. The system verifies whether the process was finished. If not, it goes to the next subgoal.
This adaptive control works by searching in the iPNRD model, called macro states, to generate a global plan. Each iPNRD transition maps to an initial and final state in the Petri Space for movement, defining a sequence of sub-goal action.
In order to concatenate the generated movements and act correctly, some special cares are necessary. The first step is to have a reference position to begin and end the actuation. The next required step is to concatenate the final state to the initial state for the different sub-goal. This is necessary because the robot needs to materially move the block to perform the tasks. It is also fundamental to open and close the robot grappler at the right moments, so that instruction must be included in the command string.
The feedback of final condition is necessary to perceive intermediate exceptions. There can be many different types of exceptions through the process of solving the system, assuming every model and table was created correctly. Exceptions in the system identification might mean that a block is missing or an RFID element is malfunctioning. This return permits that the system self regulates and accuse anomalies. It is fundamental to emphasize that the system is partially observable, meaning that some external actions and singularities cannot be perceived immediately, sometimes only after a sorting requisition is finished, other during the beginning of another job. One methodology to analyze irregularities, their causes and origin, is viable through the circumstances of exception. This can be accomplished using methods that involve failure mode analysis and statistics to infer about possible faults.
In the case that the process is successfully finished it is necessary to update PNRD data. This is done by moving into the blocks position and sending new data to be stored in the tag according to the job last performed. In order to actuate correctly the system needs geometrical references so that the arm and blocks can be positioned right. These markings are absolutely necessary if the system has a pick-and-place approach, doing work without trajectory feedback. In a model that includes more sensors and auxiliary systems for dynamics the layout can be more flexible.
Other very important aspects are the mechanical and electronic projects. The system has to be designed to handle the mechanical load and operate in the specified work space. In the block world explored here, it was simple to build an adequate robot for the task, so it was not necessary to make studies and formulate deeper about dimensions, stress, controls, power and their material tools and needs. A small arm was projected and built using additive manufacturing and common servomotors, and a simple microcontroller is used to operate the arm and manage data coming from the RFID reader and computer. In a more demanding situation studying those requirements is fundamental to use a suitable robot and components. 4.1
This example has BA_C initial state (Fig. 11) and BAC as final state (Fig. 12). First, the system must be booted by a supervisor, then it will proceed to sweep through the discrete positions identifying the blocks by their unique ids and get their desired PNRD state. The robot will execute this process as described in section 4.1. The initial identified Petri Space is {C1_1, C1_2, C3_1}. Through Table 1 it is possible to find the current iPNRD state as BA_C. The current PNRD state can be checked to conclude about changes in the expected state. The data about the blocks desired position is previously added in the PNRD, and it is collected during the initial sweep. Thus desired PNRD set is {AC, BA, CT }, Table 1 correlates this with BAC iPNRD state.
Fig. 12. Final state representation.
The next step is to feed the initial and objective macro states to the sorting engine as {BA_C, BAC}, in order to determine the course of action in the iPNRD state space.
The result of a BFS search algorithm (planner) is the subobjective progression and transition firing sequence. In this case, the best path to reach the objective state is, in order, through A_B_C, AC_B and finally to BAC. These macrotransitions must relate to Petri State transitions in order to actuate on the material world.
To move, the robot must leave a reference initial position, defined as C2_4, to the initial position of the first subobjective with the gripper open. The first subobjective is to change from iPNRD state BA_C to A_B_C, which translates into moving block B from C1_2 to C2_1. To move from C2_4 to C1_2 Petri Space transitions T 19 and T 2 must be fired in sequence. The next step is to grip the block. This action is provided in the database, because logically the block has to be caught and moved. In sequence, transitions T 3, T 18 and T 10 must occur. Reaching its final position the arm can open. This ends the movement sequence to reach the first subobjective.
Now, to start the second subobjective, it is necessary to move from the current position to the next initial position. The next block that will be moved is block A. The planner identifies that it must concatenate the movement sequence and the subobjective now is to move from C2_1 to C1_1 with an open arm. Then another search is performed to change the iPNRD from A_B_C to AC_B. To perform this shift the planner must move block A from C1_1 to C3_2. In this example the last subobjective consists of moving AC_B to BAC. When sorting is complete the gripper must return to C2_4, ending the adaptive control. The robot driver just interprets the received string and executes it. For each Petri Space transition there is a corresponding robot configuration. To reach the desired position each servomotor must be in a specified angle. If the position C2_2 is requested, a robot with 6 controlled joints (motors) must command each one to be in a pre specified angle. This can represented as the sextuple where is the desired servomotor angle, as an example {90, 120, 60, 40, 170, 20} in degrees. Final steps are a certification sweep and PNRD rewrite. If the resulting iPNRD macro state is equal to the desired, the goal was performed successfully, else an exception occurred. If successful, each blocks PNRD must be updated by rewriting its tag’s data. 5
This paper presented how PNRD and iPNRD integration can be applied in an adaptive control. It also shows that it is feasible to integrate this solution with automated planners. However, for more complex system (as example 10 blocks) iPNRD model is not able to represent all blocks state space, and it must be simplified based on automated planning results. In each operation it is indispensable to rectify the model. In special on the physical level, the adequate fit for positions and trajectory, with uncertainty and precision levels inside a certain tolerance are essential. To build the models correctly and to realize the system it is fundamental to, in each step, certify that what was built is accurate and done right. But when dealing with automatic model generators and bigger systems this problem gets harder, and it must be investigated.
Partial observability is another issue, because it makes exception detection much harder and limits the sweeps average speed. By including more sensors partial observability issues could be greatly reduced. Building auxiliary systems that make exceptions harder to happen or faster to detect could increase system performance.
There are dynamical and geometrical issues regarding the blocks disposition and manipulation. In order to successfully realize the actuation and sensing the system must be precise or robust, meaning that motors torque, potency and control, vibration analysis, sensor signal studies and physical references to assure the fidelity of the driver system motion might be required. Using any form of position sensors to fully monitor the grid would make the moving processes faster. Adding other sensors the data could be compared to whatever additional information lies inside the tags. Vision systems could make the methods more flexible and be auxiliary in the movement planner. A more profound study and building improved hardware could make the system faster and more reliable. The RFID system generates a complementary data structure locally, and, in case of network issues, it could assist robot movement independently, acting as Edge Computing application. This aspect must be studied straight forward. Other means for improvement are making the machines and objectives more flexible and having multiple agents. The system could support many different objective states or perform partial satisfaction on conflicting jobs. The system could work on parallel or concurrent robots that share a common work space, having distributed tasks and logic but keeping consistent. To work based on a reference clock would be great for timing activities. These changes could be further improved by using model paradigms better suited for state space expansion but it would require more computational power and the use of more sophisticated techniques. A very important addition to the system is FMEA (Failure Mode and Effect Analysis) for determining exception cause. A more powerful sensory system coupled with tools for inference and statistical analysis could provide useful data for concluding about the original problems.
PNRD/iPNRD must be formaly defined for concepts, operations and analysis. 6
This work is supported by CNPq, CAPES, FAPEMIG, UFU. This paper is dedicated to prof. Dr. José Reinaldo Silva (PMR/USP).