RT-BDI: A Real-Time BDI model

Currently, distributed cyber-physical systems (CPS) rely upon embedded real-time systems, which can guarantee compliance with time constraints. CPS are increasingly required to act and interact with one another in dynamic environments. In the last decades, the Belief-Desire-Intention (BDI) architecture has proven to be ideal for developing agents with flexible behavior. However, current BDI models can only reason about time and not in time. This lack prevents BDI agents from being adopted in designing CPS, and particularly in safety-critical applications. This paper proposes a revision of the BDI model by integrating real-time mechanisms into the reasoning cycle of the agent. By doing so, the BDI agent can make decisions and execute plans ensuring compliance with strict timing constraints also in dynamic environments, where unpredictable events may occur.

Video presentation: https://youtu.be/X6S74JVsFOU

1. [1] [email protected], University of Trento, Trento, Italy
[2] [email protected], University of Trento, Trento, Italy
[3] [email protected], Sant’Anna School of Advanced Studies, Pisa, Italy
[4] [email protected], University of Applied Sciences and Arts of Western Switzerland, Sierre, Switzerland
RT-BDI: A Real-Time BDI model
18th International Conference on Practical Applications of Agents
and Multi-Agent Systems
Francesco Alzetta
[1], Paolo Giorgini
[2], Mauro Marinoni
[3], Davide Calvaresi
[4]

2. /21
Motivations
•Traffic management (air and ground)
•UAVs
•Swarm robotics
•Manufacturing
•E-healthcare
02

3. /21
Motivations
•Traffic management (air and ground)
•UAVs
•Swarm robotics
•Manufacturing
•E-healthcare
•Realtime systems
•Highly dynamic environments
02

4. /21
The approach
State-of-art approach
03
Hybrid control architecture

5. /21
The approach
State-of-art approach
03
Hybrid control architecture LAAS architecture (Alami et al., 1998)

6. /21
The approach
State-of-art approach
03
Hybrid control architecture LAAS architecture (Alami et al., 1998) SIMBA architecture (Julian et al., 2002)

7. /21
The approach
The proposed approach
04
Integrated architecture

8. /21
The approach
The proposed approach
04
ARTS execution cycle (Vikhorev et al., 2009)
Integrated architecture

9. /21
The approach
The proposed approach
05
Integrated architecture

10. /21
The approach
The proposed approach
05
Integrated architecture
real-time

11. /21
The approach
The proposed approach
05
Integrated architecture
real-time

12. /21
The approach
The proposed approach
05
Integrated architecture
real-time

13. /21
The approach
The proposed approach
05
Integrated architecture
real-time

14. /21
RT-BDI model
06
a = { B, D, P, ϕA, ϕI }

15. /21
RT-BDI model
06
a = { B, D, P, ϕA, ϕI }

16. /21
RT-BDI model
06
a = { B, D, P, ϕA, ϕI }

17. /21
RT-BDI model
06
a = { B, D, P, ϕA, ϕI }

18. /21
RT-BDI model
06
a = { B, D, P, ϕA, ϕI }

19. /21
RT-BDI model
06
a = { B, D, P, ϕA, ϕI }

20. /21
RT-BDI model
07

21. /21
RT-BDI model
07
B = { b1, … , bn }, where b = { p(t1, … , tk) }

22. /21
RT-BDI model
07
B = { b1, … , bn }, where b = { p(t1, … , tk) }
D = { d1, … , dn }, where d = { b, prec, pr }
•b = b ∈ B ∪ B
•prec = ∧β∈ B U B β
•pr = [0, 1]

23. /21
RT-BDI model
07
B = { b1, … , bn }, where b = { p(t1, … , tk) }
D = { d1, … , dn }, where d = { b, prec, pr }
P = { p1, … , pn }, where p = { d, pref, prec, cont,body }
•d ∈ D
•pref = [0, 1]
•prec = ∧β∈ B U B β
•cont = ∧β∈ B U B β
•body = { α 1, … , α n }, α ∈ {internal goal, RT task}

24. /21
RT-BDI model
Action
08

25. /21
RT-BDI model
Action
body = { α 1, … , α n }, α ∈ {internal goal, RT task}
08

26. /21
RT-BDI model
Action
body = { α 1, … , α n }, α ∈ {internal goal, RT task}
When selected by the agent, a desire d becomes a goal. 
08

27. /21
RT-BDI model
Action
body = { α 1, … , α n }, α ∈ {internal goal, RT task}
When selected by the agent, a desire d becomes a goal. 
•external goals => desires activated by a triggering event

◦e.g., a change in the belief-set or a request made by another agent

08

28. /21
RT-BDI model
Action
body = { α 1, … , α n }, α ∈ {internal goal, RT task}
When selected by the agent, a desire d becomes a goal. 
•external goals => desires activated by a triggering event

◦e.g., a change in the belief-set or a request made by another agent

•internal goals => desires activated by an intention

◦requires the instantiation of a sub-plan

◦are not subject to preconditions
08

29. /21
RT-BDI model
Action
body = { α 1, … , α n }, α ∈ {internal goal, RT task}
A RT task can either be periodic or aperiodic.
•periodic tasks => a (potentially infinite) sequence of regular activations 















•aperiodic tasks => their activations are irregularly interleaved
9

30. /21
RT-BDI model
10
B = { b1, … , bn }, where b = { p(t1, … , tk) }
D = { d1, … , dn }, where d = { b, prec, pr }
P = { p1, … , pn }, where p = { d, pref, prec, cont,body }

31. /21
RT-BDI model
10
B = { b1, … , bn }, where b = { p(t1, … , tk) }
D = { d1, … , dn }, where d = { b, prec, pr }
P = { p1, … , pn }, where p = { d, pref, prec, cont,body }
ϕA : B x G → P

32. /21
RT-BDI model
About intentions
•Task-level reasoning
•Intentions carried on “simultaneously”
•still guaranteeing the respect of real-time constraints
11

33. /21
RT-BDI model
About intentions
•still guaranteeing the respect of real-time constraints
•How?
•Schedulability analysis
•We exploited the Earliest Deadline First schedulability analysis
12

34. /21
RT-BDI model
Earliest Deadline First schedulability analysis
•Every periodic task is characterised by a computational time C and a period T
•A set of periodic tasks is schedulable with EDF i(#
•Bandwidth reservation mechanism to deal with aperiodic tasks
•Constant Bandwidth Server (CBS) mechanism
•A CBS is a periodic task
•Is characterized by a budget Q and a period T
•The budget is made available to the aperiodic tasks assigned to that server
13

35. /21
RT-BDI model
About intentions
•If the agent’s scheduler uses EDF, then C3/T3 + C11/T11 + C1/T1 + C1/T1 ≤ 1
•n
•Intentions’ interleaving cannot exceed the threshold
14

36. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
15

37. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
15
max C/T(I1) = max (0.2, 0.13, 0.1, 0.375) = 0.375

38. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
15
max C/T(I1) = max (0.2, 0.13, 0.1, 0.375) = 0.375
max C/T(I2) = max (0.2, 0.17, 0.18, 0.25, 0.2) = 0.25

39. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
15
max C/T(I1) = max (0.2, 0.13, 0.1, 0.375) = 0.375
max C/T(I2) = max (0.2, 0.17, 0.18, 0.25, 0.2) = 0.25
max C/T(I3) = max (0.1) = 0.1

40. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
15
max C/T(I1) = max (0.2, 0.13, 0.1, 0.375) = 0.375
max C/T(I2) = max (0.2, 0.17, 0.18, 0.25, 0.2) = 0.25
max C/T(I3) = max (0.1) = 0.1
=> max C/T = 0.375 + 0.25 + 0.1 = 0.725

41. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
15
max C/T(I1) = max (0.2, 0.13, 0.1, 0.375) = 0.375
max C/T(I2) = max (0.2, 0.17, 0.18, 0.25, 0.2) = 0.25
max C/T(I3) = max (0.1) = 0.1
=> max C/T = 0.375 + 0.25 + 0.1 = 0.725

42. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
15
max C/T(I1) = max (0.2, 0.13, 0.1, 0.375) = 0.375
max C/T(I2) = max (0.2, 0.17, 0.18, 0.25, 0.2) = 0.25
max C/T(I3) = max (0.1) = 0.1
=> max C/T = 0.375 + 0.25 + 0.1 = 0.725
max C/T(I4) = max (0.1, 0.4, 0.18, 0.4, 0.25) = 0.4

43. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
15
max C/T(I1) = max (0.2, 0.13, 0.1, 0.375) = 0.375
max C/T(I2) = max (0.2, 0.17, 0.18, 0.25, 0.2) = 0.25
max C/T(I3) = max (0.1) = 0.1
=> max C/T = 0.375 + 0.25 + 0.1 = 0.725
max C/T(I4) = max (0.1, 0.4, 0.18, 0.4, 0.25) = 0.4

44. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
15
max C/T(I1) = max (0.2, 0.13, 0.1, 0.375) = 0.375
max C/T(I2) = max (0.2, 0.17, 0.18, 0.25, 0.2) = 0.25
max C/T(I3) = max (0.1) = 0.1
=> max C/T = 0.375 + 0.25 + 0.1 = 0.725
max C/T(I4) = max (0.1, 0.4, 0.18, 0.4, 0.25) = 0.4
0.725 + 0.4 > 1

45. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
15
max C/T(I1) = max (0.2, 0.13, 0.1, 0.375) = 0.375
max C/T(I2) = max (0.2, 0.17, 0.18, 0.25, 0.2) = 0.25
max C/T(I3) = max (0.1) = 0.1
=> max C/T = 0.375 + 0.25 + 0.1 = 0.725
max C/T(I4) = max (0.1, 0.4, 0.18, 0.4, 0.25) = 0.4
0.725 + 0.4 > 1

46. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
16

47. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
16
•Pessimistic approach, but

48. /21
RT-BDI model
About intentions
•Intentions’ interleaving cannot exceed the threshold
=> worst case among all the tasks belonging to the intention
16
•Pessimistic approach, but
•It guarantees robustness against any deadline miss

49. /21
RT-BDI model
17
B = { b1, … , bn }, where b = { p(t1, … , tk) }
D = { d1, … , dn }, where d = { b, prec, pr }
P = { p1, … , pn }, where p = { d, pref, prec, cont,body }
ϕA : B x G → P
ϕA definition

50. /21
RT-BDI model
17
B = { b1, … , bn }, where b = { p(t1, … , tk) }
D = { d1, … , dn }, where d = { b, prec, pr }
P = { p1, … , pn }, where p = { d, pref, prec, cont,body }
ϕA : B x G → P
1.Try to schedule (commit to) an applicable plan for each active goal.

ϕA definition

51. /21
RT-BDI model
17
B = { b1, … , bn }, where b = { p(t1, … , tk) }
D = { d1, … , dn }, where d = { b, prec, pr }
P = { p1, … , pn }, where p = { d, pref, prec, cont,body }
ϕA : B x G → P
1.Try to schedule (commit to) an applicable plan for each active goal.

2.If (1) is not possible, drop the plans for the goals having less priority.

ϕA definition

52. /21
RT-BDI model
17
B = { b1, … , bn }, where b = { p(t1, … , tk) }
D = { d1, … , dn }, where d = { b, prec, pr }
P = { p1, … , pn }, where p = { d, pref, prec, cont,body }
ϕA : B x G → P
1.Try to schedule (commit to) an applicable plan for each active goal.

2.If (1) is not possible, drop the plans for the goals having less priority.

3.Among plans for goals with same priority, prioritize those that are most preferred by the agent.
ϕA definition

53. /21
RT-BDI model
18
B = { b1, … , bn }, where b = { p(t1, … , tk) }
D = { d1, … , dn }, where d = { b, prec, pr }
P = { p1, … , pn }, where p = { d, pref, prec, cont,body }
ϕA : B x G → P

54. /21
RT-BDI model
18
B = { b1, … , bn }, where b = { p(t1, … , tk) }
D = { d1, … , dn }, where d = { b, prec, pr }
P = { p1, … , pn }, where p = { d, pref, prec, cont,body }
ϕA : B x G → P
ϕI : I → I
EDF scheduling algorithm

55. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First

56. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1

57. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2

58. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3

59. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1

60. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2

61. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2 3

62. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2 34

63. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2 34 5

64. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2 34 5 6

65. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2 34 5 6 1

66. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2 34 5 6 12

67. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2 34 5 6 1 32

68. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2 34 5 6 1 4 32

69. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2 34 5 6 1 4 32 5

70. /21
RT-BDI model
19
First-Come-First-Served
Task activation comparison
Round robin Earliest Deadline First
1 2 3 1 2 34 5 6 1 4 32 5 6

71. /21
Future work
•A more accurate evaluation of the intentions
•An intention could maybe have been scheduled with the right interleaving
•RT constraints met at the goal level
•To allow desires such as “accomplish a goal g in at maximum t time”
•Extension of the model from single to multi-agent settings.
20

72. /21
Conclusion
•Integration of RT mechanisms into the BDI reasoning cycle
•RT scheduler involved in two distinct phases:
•schedulability analysis to establish the feasibility of intentions
•scheduling algorithm providing the execution order of the tasks
=> Agent able to evaluate if a potential intention can be executed without
impacting on the temporal guarantees of the other active intentions.
21

73. Thank you