Vol-3197/paper1
Jump to navigation
Jump to search
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| id | Vol-3197/paper1 |
| wikidataid | →Q117338227 |
| title | Towards Legally and Ethically Correct Online HTN Planning for Data Transfer |
| pdfUrl | https://ceur-ws.org/Vol-3197/paper1.pdf |
| dblpUrl | https://dblp.org/rec/conf/nmr/HayashiS22 |
| volume | Vol-3197→Vol-3197 |
| session | → |
Towards Legally and Ethically Correct Online HTN Planning for Data Transfer
Towards Legally and Ethically Correct Online HTN Planning
for Data Transfer
Hisashi Hayashi1,* , Ken Satoh2
1
Advanced Institute of Industrial Technology, 1-10-40 Higashi-Ooi, Shinagawa-ku, Tokyo, 140-0011, Japan
2
National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan
Abstract
Data transfer among servers is crucial for distributed data mining because many databases are distributed around the world.
However, as data privacy is becoming more legally and ethically protected, it is necessary to abide by the laws and respect the
ethical guidelines when transferring and utilizing data. Because information affecting legal/ethical decision making is often
distributed, the data-transfer plan must be updated online when new information is obtained while transferring data among
servers. In this study, we propose a dynamic hierarchical task network (HTN) planning method that considers legal and
ethical norms while planning multihop data transfers and data analyses/transformations. In our knowledge representation,
we show that data-transfer tasks can be represented by the task-decomposition rules of total-order HTN planning. We also
show that legal norms can be expressed as the preconditions of tasks and actions, and ethical norms can be expressed as the
costs of tasks and actions where legal norms cannot be violated, but ethical norms can be violated if necessary following the
ethical theory of utilitarianism. In the middle of the plan execution, the online planner dynamically updates the plan based
on new information obtained in accordance with laws and ethical guidelines.
Keywords
Data Transfer, Legal and Ethical Norms, Online HTN Planning, Logic Programming, Application of Knowledge Representation
1. Introduction ning. In other words, the data-transfer plan must be
dynamically checked and updated if necessary, even in
Because data privacy is respected worldwide, many laws the middle of the plan execution when new information
and ethical guidelines governing the transfer and usage is found on distributed servers, which may affect the
of collected data have been established. Some data can validity of the plan.
only be transferred within a country or a company. Some In this paper, we present a new knowledge represen-
data can only be used for specific purposes. tation for dynamic HTN planning on transferring and
Because the laws and ethical guidelines for collected utilizing distributed data considering legal and ethical
data are complicated and different in each country, some norms. We use an extended algorithm of Dynagent [7]
researches have been conducted on the automated com- which is an online total-order HTN planner. Total-order
pliance check of norms in data transfers. In [1, 2, 3, 4, 5], HTN planning algorithms [7, 8, 9, 10, 11] are simple, easy
the policy presentation of European general data protec- to use, and used for representing the domain control
tion regulation (GDPR) is studied to automate compliance heuristics by task-decomposition rules.
checks. In our knowledge representation, we show that
Planning for data transfer in accordance with legal/eth- data-transfer tasks can be represented by the task-
ical norms is a new field of research. In the studies of decomposition rules of total-order HTN planning. We
[5, 6], data-transfer planners and legal/ethical checkers also show that legal norms can be expressed as the pre-
are separate. These are good frameworks considering conditions of tasks and actions, and ethical norms can
that the logic of legal/ethical checkers is complicated and be expressed as the costs of tasks and actions where le-
should be separated from the logic of planning. However, gal norms cannot be violated, but ethical norms can be
dynamic replanning was not achieved in these studies. violated if necessary following the ethical theory of utili-
Considering real international data transfers among tarianism. Using this knowledge and an online planning
distributed servers, dynamic replanning is crucial be- algorithm, the plan of data transfer and utilization is
cause the latest information necessary for planning is dynamically adapted to the new information obtained
also distributed and not available when initially plan- at local servers, abiding by the laws and following the
ethical guidelines.
NMR 2022: 20th International Workshop on Non-Monotonic Reasoning,
We assume that the data-transfer planners and
August 07–09, 2022, Haifa, Israel
*
Corresponding author. legal/ethical checkers are separate as in [5, 6]. We fo-
" hayashi-hisashi@aiit.ac.jp (H. Hayashi); ksatoh@nii.ac.jp cus on planning and replanning rather than legal/ethical
(K. Satoh) checks. Because we use an online planning algorithm,
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0). the validity of the plan is checked and the plan is updated
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
4
�in the middle of the execution with the help of external Carlo tree search, which is often used for game tree
legal and ethical checkers. search. This technique is known to be effective when
The rest of this paper is organized as follows: In Sec- the search space is very large, such as in chess or Go.
tion 2, related work is discussed. In Section 3, the algo- This planner can also represent complicated control pro-
rithm of online HTN planning is explained. In Section 4, cesses such as “if-then” and “repetition” as in standard
the system architecture of the planning agent with exter- procedural programming languages.
nal legal and ethical checkers is presented. In Section 5, In the studies [5, 6], the knowledge representation for
the problem of data transfer and utilization is defined. In data-transfer planning is expressed by logic programs
Section 6, the knowledge representation method to solve that represent the simplified version [23] of the event
the problem is shown as a case study based on a specific calculus [24]. These planners are implemented by the
scenario. In Section 7, the knowledge representation pre- answer set programming (ASP [25]) solver, which makes
sented in the case study is discussed. In Section 8, the stable models through forward reasoning. However, they
paper is summarized. are not online planners. The idea of using the simplified
version of the event calculus for planning was first in-
troduced in [26]. A planner based on the event-calculus
2. Related Work was implemented in [27] using the Prolog programming
language.
HTN planners create plans by decomposing abstract tasks
In [28, 29], event calculus is used for representing
into more concrete subtasks. The first HTN planners
causalities in computational ethics. Another work on
were created in the late 1970s [12, 13]. Other previous
ethical principles on planning is found in [30].
HTN planners were created around 1990 [14, 15].
The most popular and well-established HTN planner
is simple hierarchical ordered planner (SHOP) [8], which 3. Online HTN Planning
is a simple forward-chaining total-order planner. This
forward-chaining planner decomposes the subtasks in In this section, we define the syntax and sketch of the
the same order of execution. Domain control heuristics algorithm of online total-order forward-chaining HTN
can be expressed easily by the task-decomposition rules planning based on the algorithm of Dynagent [7]. Dyna-
(methods) in a manner similar to the Horn clauses of gent [7] is similar to SHOP [8]. However, in contrast to
the Prolog programming language, which are used for SHOP, Dynagent is an online planner.
goal/literal decomposition.
SHOP is still standard in HTN planning. For example, 3.1. Syntax
HDDL [16] was used in the HTN planning track of the in-
ternational planning competition held in 2020, however, In this subsection, we define the syntax of the belief and
a translator from HDDL to (J)SHOP2 [17] was provided. planning knowledge that are used by the planner. Because
(Note that SHOP2 is a partial-order-planner version of we implemented the algorithm in Prolog, the syntax fol-
SHOP, and that JSHOP2 is the Java version of SHOP2.) lows its representation.
SHOP-like total-order HTN planners are still being stud- In the following definition, fluents (predicates whose
ied to improve computational efficiency [9, 10, 11]. truth value can change) and belief rules (corresponding
Dynagent [7] is a simple SHOP-like total-order to Horn clauses in Prolog) are defined using constants,
forward-chaining HTN planner. In contrast to SHOP, variables, functions (=function symbols), and predi-
Dynagent is an online HTN planner. When the current cates (=predicate symbols). As in Prolog, constants, func-
assumption is updated, the Dynagent planner modifies tions, and predicates, are represented by alphanumeric
the plan, even in the middle of plan execution. Dynagent characters starting with a lowercase alphabet and Vari-
was applied to real robot manipulation, such as online ables are represented by alphanumeric characters starting
path planning [18] and online pick-and-place planning with an uppercase alphabet or “_”.
(arm manipulation) [19, 20]. In this study, we adopted
Definition 1. A term is one of the following: a constant,
and slightly modified the online HTN planning algorithm
a variable, or a complex term. A complex term is of the
of Dynagent.
following form: F(T1 , · · · , Tn ) where 𝑛 ≥ 0, F is an n-ary
Another interesting online forward-chaining HTN-
function, and each Ti (1 ≤ 𝑖 ≤ 𝑛) is a term. A fluent is of
like planning is also studied in [21, 22]. This online plan-
the following form: P(T1 , · · · , Tn ) where 𝑛 ≥ 0, P is an
ner never backtracks and cannot change the plan in the
n-ary predicate, and each Ti (1 ≤ 𝑖 ≤ 𝑛) is a term. When
middle of execution. However, it delays the subtask de-
P is a 0-ary predicate, the fluent P() can be abbreviated to
composition until it becomes necessary and changes the
P. A fluent is either derived or primitive.
way to decompose the subtasks according to the current
situation. Interestingly, this planner conducts Monte
5
� In the following definition, belief rules are defined in The planning agent has belief and planning knowl-
the same way as in Prolog. Fluents are used to represent edge, which are used for planning. Furthermore, belief
the states. represents the current state, whereas planning knowl-
edge represents the effects of actions and the methods to
Definition 2. A belief rule is of the following form: decompose tasks into subtasks.
belief(F, [F1 , · · · , Fn ])1 where 𝑛 ≥ 0, F is a derived
fluent called the head, each Fi (1 ≤ 𝑖 ≤ 𝑛) is a fluent, Definition 6. Belief is of the following form: ⟨D, S⟩
and the set of fluents F1 , · · · , Fn is called the body. When where D is a set of dynamic fluents, and S is a set of belief
𝑛 > 0, F is a derived fluent. When 𝑛 = 0, the belief rules.
rule belief(F, []) can be expressed as belief(F) and F Planning knowledge is of the following form:
is called a fact. The belief rule belief(F, [F1 , · · · , Fn ]) ⟨AR, TDR, COST⟩ where AR is a set of action rules, TDR
defines the fluent G if F is unifiable with G. Fluent F is is a set of task-decomposition rules, and COST is a set of
regarded as dynamic iff it is declared as dy(F). The belief the cost of each task.
rule belief(F) can be asserted to or retracted from the
belief after observation or action execution iff F is dynamic.
3.2. Semantics
We define the syntax of tasks, actions, and (total-order)
Standard semantics of a plan can be used if all the tasks
plans as follows: task symbols are represented by alphanu-
in the plan are actions. See the simplified version [23] of
meric characters starting with a lowercase alphabet.
the event calculus for example.
Definition 3. A task is of the following form:
T(X1 , · · · , Xn ) where 𝑛 ≥ 0, T is an n-ary task symbol, 3.3. Sketch of the Algorithm
and each Xi (1 ≤ 𝑖 ≤ 𝑛) is a term. When T is a 0-ary task
symbol, the task T() can be abbreviated to T. A task is In this subsection, we show the sketch of the algorithm
either abstract or primitive. An action is a primitive we used in this study. We used the algorithm of Dy-
task. The cost C of the task T, where 𝐶 is a number (real nagent, which is defined in detail in [7]. However, the
number or integer), is represented as cost(T, C). replanning method after cost updates is not shown in [7].
A plan is a list of tasks of the following form: We modified the algorithm to handle cost updates, which
[T1 , · · · , Tn ] where 𝑛 ≥ 0 and each Ti (1 ≤ 𝑖 ≤ 𝑛) is crucial for reflecting ethical norms in plan selection.
is a task, which is called the i-th element of the plan. The Because the algorithm is implemented in Prolog, it can
cost of the plan [T , · · · , T ] is the sum of each cost of T handle rules of predicate logic by unification.
1 n i
(1 ≤ 𝑖 ≤ 𝑛).
3.3.1. Initial Planning
To represent the effect of an action, we use the follow-
ing action rules. The planning agent has the belief and planning knowl-
edge defined in the previous subsection. Belief repre-
Definition 4. An action rule is of the following form: sents the current state (the truth value of each fluent) of
𝑎𝑐𝑡𝑖𝑜𝑛(A, C, E), where A is an action, C is a list of flu- the world, which the planning agent believes. Planning
ents called preconditions, E is a list of effects, an ef- knowledge includes action rules, task-decomposition
fect is either of the following forms: initiates(F) or rules, and cost information of tasks.
terminates(F), and F is a fluent. The planner recursively decomposes the task into sub-
tasks that become primitive tasks (= actions) before exe-
Intuitively, in the aforementioned definition, cution. The HTN planning algorithm is forward-chaining
initiates(F) (or terminates(F)) represents that the and the task decomposition is conducted in the same or-
truth value of F becomes true (respectively, false) after der as task execution. As shown in Figure 1, when taskA
the action execution, if all the preconditions hold. in a plan is decomposed, all the previous tasks before
To represent a method to decompose a task into sub- taskA are primitive. Therefore, it is easy to evaluate the
tasks, we use the following task-decomposition rules. truth value of fluents in the state shortly before task ex-
Note that task decomposition rules are called methods in ecution. The preconditions (precond2 and precond3) of
SHOP [8]. the task decomposition, which are added to the precondi-
Definition 5. A task-decomposition rule is of the fol- tions of the first subtask (taskA1), must be satisfied before
lowing form: ℎ𝑡𝑛(H, C, B) where H is an abstract task the task execution.
called the head, C is a list of fluents called precondi- In general, there are several ways to decompose a task.
tions, and B is a plan called the body. For example, in the case of the data transfer problem,
there are several routes for data transfer. When decom-
1
This syntax reflects our implementation in Prolog. This belief rule posing a task in a plan, multiple plans are created using
can be understood as F ⇐ F1 , · · · , Fn .
6
�Figure 1: Task Decomposition
Figure 4: Switching to an Alternative Plan
Figure 2: Multiple Subplans
is violated, the plan becomes invalid. Then, the invalid
plan is removed from the frontiers of the or-search tree.
multiple task-decomposition rules. For example, in Fig- As shown in Figure 4, if the current plan becomes invalid,
ure 2, the task t3 in a plan is decomposed into three the planning agent changes the current plan to the plan
subplans [a1, a2, a3, a4], [b1, b2], and [c1]. Therefore, with the next-lowest cost, and continues the best-first
the search space of HTN planning is an or-search-tree of search using the frontiers of valid plans.
plans.
When each task has the cost information, the best-first 3.3.3. Replanning after Belief Addition
search can be conducted. In the algorithm of Dynagent,
to conduct the best-first search, the planning agent main- When evaluating a precondition of a task in a plan in the
tains frontiers (alternative plans) in the or-search-tree planning algorithm of Dynagent, if the precondition is
of plans, sorts the plans in ascending order of cost, and a dynamic fluent, the planning agent records the plan
decomposes the first abstract task in the plan with the separately from the frontiers even if the fluent is false.
lowest cost. If the cost of a task is always lower than or During the plan execution, if the belief is updated and the
equal to the cost of its primitive subplans (subplans that precondition becomes true, the recorded plan is asserted
have only actions), the first found plan has the lowest to the frontiers as a new valid plan. Because the plans
cost. in frontiers are always sorted, if the new plan has the
lowest cost, the planning agent stops the current plan
3.3.2. Replanning after Belief Deletion execution, switches to the new plan, and continues the
best-first search, which may lead to a better plan.
In the planning algorithm of Dynagent, each precondi-
tion (a dynamic fluent) of a task in a plan is recorded 3.3.4. Replanning after Cost Update
in association with the task in the plan if its truth value
is subject to change. As shown in Figure 3, this fluent In the planning algorithm of Dynagent, replanning after
recorded as a precondition of a task serves as a protected a cost update is not explicitly shown. However, this is cru-
link which must be true before the execution of the task. cial in our planning with an ethical checker because the
Following a belief update, if the protected link in a plan costs of unethical actions are dynamically set higher after
the ethical check. Therefore, we added a new replanning
procedure to the algorithm.
Following the cost update of an action (or a task), we
reevaluate the cost of each plan in the frontiers and sort
the plans in ascending order of cost. When the current
plan becomes less attractive in terms of costs after the
g update, the planning agent stops the plan execution,
changes the plan, and continues the best-first search,
Figure 3: Protected Link which may lead to a better plan.
7
�Figure 5: Plan Update after Action Execution
Figure 7: System Architecture
for planning and replanning in the online HTN planner.
In addition, the online planning agent has an event
Figure 6: Replan after Action Failure handler that inputs a task or a belief/cost update request
to the online HTN planner when receiving an event from
an external world observer that obtains new information.
Given a task or a belief/cost update request, the planner
3.3.5. Replanning after Action Execution
starts planning or replanning.
Dynagent is an online planner that updates each plan Note that the user interface that receives a command
after execution of each action. It maintains all the al- from the user can be regarded as a world observer. An
ternative plans so that any plan can be started from the example of the event handler is explained in [18].
current state. The online planning agent also has an action executor
As shown in Figure 5, when the execution of an action that receives an action execution command from the
succeeds, if the executed action is unifiable with the first online HTN planner and controls the external controller
action in a plan, it is removed from the plan. Sometimes to execute the action.
an action execution in a plan invalidates other alternative To utilize external legal and ethical checkers, we need
plans. Therefore, protected links are checked and invalid a norm check requester that inputs the next action to the
alternative plans are removed after a successful action legal and ethical checkers. Because we need to check the
execution. legal and ethical norms before executing an action, the
As shown in Figure 6, when the execution of an action action executor sends the next action to this norm check
fails, if the executed action is unifiable with the first requester.
action in a plan, the plan is removed from the alternative If the next action is not changed after checking the
plans recorded in the frontiers. In this case, the planning legal and ethical norms, the action executor executes the
agent stops the plan execution and restarts the best-first action as usual. If there is a legal or ethical problem, the
search using the valid plans in the frontiers until it finds belief update requester or the cost update requester sends
the plan. the belief update request or the cost update request to
the online HTN planner, which triggers replanning.
In this study, we only designed and implemented the
4. Online HTN Planning Agent knowledge (belief and planning knowledge) and the al-
Architecture with External gorithm of the online planning agent. In the future, we
would consider to connect the planning agent to the legal
Legal and Ethical Checkers and ethical checkers.
In Figure 7, we show the overall system architecture of
our online HTN planning agent with external legal and 5. Problem
ethical checkers.
In this study, we focused on the knowledge represen- In this section, we define the planning problem of legally
tation of beliefs and planning knowledge, which is used and ethically correct data transfer and utilization.
8
� 6.1.1. Node Connection
In Figure 8, there are seven nodes that represent servers.
The arcs that connect nodes represent the network lines.
These network connections are represented as follows:
belief(arc(node1,node2)). belief(arc(node1,node4)).
belief(arc(node1,node6)). belief(arc(node2,node3)).
belief(arc(node3,node4)). belief(arc(node3,node5)).
belief(arc(node4,node7)). belief(arc(node5,node7)).
belief(arc(node6,node7)).
Figure 8: Connection of Servers To represent that each network connection is bidirec-
tional, we define the “connected” predicate as follows:
belief(connected(Node1,Node2),[arc(Node1,Node2)]).
belief(connected(Node1,Node2),[arc(Node2,Node1)]).
Nodes (servers) are connected by arcs (network lines).
The data stored in the database at a node can be retrieved The efficiency of data transfer changes according to
from the same node. Data at a node can be transferred the line and time.
to an adjacent node that is connected by an arc. An ana-
lyzer at a node can analyze data for a specific purpose 6.1.2. Location of Database and Retrieved Data
at the same node. Analysis output is also data and can
be transferred to an adjacent node connected by an arc. There is a database at node2 that contains data about the
There are legal and ethical norms for data trans- habits and behaviors of people, which are represented as
fers. Some data can only be transferred within specific follows:
countries. Some data can only be transferred within a belief(dbAt(dataHabit,node2)).
company. Some data can only be analyzed for specific belief(dbAt(dataBehavior,node2)).
purposes. Legal norms must be satisfied. Ethical norms
should be respected if possible. The location of the retrieved data from the database is
The objective is to deliver the analysis output of speci- subject to change, which is represented as follows:
fied data to a specified node for a specific purpose. belief(dataAt(_,_)).
6. Case Study 6.1.3. Location of Analyzers
In this section, we consider a specific network and data There are three analyzers of data on the habits and be-
transfer to study the feasibility of our dynamic HTN haviors of people. The analyzer at node6 is used for op-
planning framework for the planning problem of legally timization. The analyzer at node4 is used for marketing.
and ethically correct data transfer and utilization . Another analyzer at node4 is used for advertising. This
Figure 8 shows the whole network to be considered can be represented as follows:
as a test case. This example is adopted and modified belief(analyzableAt(dataHabit,marketing,node4)).
from the example written in [5]. In the following subsec- belief(analyzableAt(dataBehavior,marketing,node4)).
belief(analyzableAt(dataHabit,advertising,node4)).
tions, we explain the details of Figure 8 while showing belief(analyzableAt(dataBehavior,advertising,node4)).
how to express the domain knowledge, actions, and task belief(analyzableAt(dataHabit,optimizing,node6)).
belief(analyzableAt(dataBehavior,optimizing,node6)).
decomposition rules.
6.1.4. Allowed Purposes for Data Analysis
6.1. Domain Knowledge
Initially, we assumed that all data were allowed to be
In this subsection, we show how to represent the domain analyzed for any purpose. However, this assumption
knowledge that is used as a belief by the planning agent. is subject to change and may be corrected by the legal
This domain knowledge includes node connection, loca- checker. This is represented as follows:
tion of database, location of analyzers, allowed purposes
for data analysis, region of nodes, allowed regions for dy(allowedPurpose(_,_)).
belief(allowedPurpose(dataHabit,marketing)).
data transfer and analysis, owners of nodes, and allowed belief(allowedPurpose(dataHabit,advertising)).
companies for data transfer. belief(allowedPurpose(dataHabit,optimizing)).
belief(allowedPurpose(dataBehavior,marketing)).
belief(allowedPurpose(dataBehavior,advertising)).
belief(allowedPurpose(dataBehavior,optimizing)).
9
�6.1.5. Regions of Nodes belief(allowedCompany(analysisOutput(
dataBehavior,advertising),companyA)).
The region (country) of each node can be represented as belief(allowedCompany(analysisOutput(
dataHabit,optimizing),companyA)).
follows: belief(allowedCompany(analysisOutput(
dataBehavior,optimizing),companyA)).
belief(nodeRegion(node1,countryX)).
The case of companyB is expressed in the same way.
belief(nodeRegion(node2,countryY)).
belief(nodeRegion(node3,countryY)).
belief(nodeRegion(node4,countryY)).
belief(nodeRegion(node5,countryY)).
belief(nodeRegion(node6,countryX)). 6.2. Actions
belief(nodeRegion(node7,countryY)).
The agent can execute three actions (primitive tasks): one
6.1.6. Allowed Regions for Data Transfer and action is to retrieve the specified data from a database,
Analysis another action is to transfer the specified data to the
specified adjacent node, and the other action is to analyze
Initially, we assumed that all data were allowed to be the specified data for the specified purpose.
transferred in any region. However, this assumption
is subject to change and may be corrected by the legal
6.2.1. Data Retrieval from DB
checker. Note that the analyzed data are also data. This
can be represented for the case of countryX as follows: The action getDataFromDB retrieves the specified data from
the DB at a node and store it at the same node. Subse-
dy(allowedRegion(_,_)).
belief(allowedRegion(dataHabit,countryX)). quently, the data can be transferred to another node or
belief(allowedRegion(dataBehavior,countryX)). analyzed for a specific purpose.
belief(allowedRegion(analysisOutput(
dataHabit,marketing),countryX)).
action(getDataFromDB(Data,Node),[
belief(allowedRegion(analysisOutput(
dbAt(Data,Node)
dataBehavior,marketing),countryX)).
],[
belief(allowedRegion(analysisOutput(
initiates(dataAt(Data,Node))
dataHabit,advertising),countryX)).
]).
belief(allowedRegion(analysisOutput(
dataBehavior,advertising),countryX)).
belief(allowedRegion(analysisOutput( The aforementioned rule specifies that the precondi-
dataHabit,optimizing),countryX)).
belief(allowedRegion(analysisOutput( tion of the action is that the database of Data is at Node, and
dataBehavior,optimizing),countryX). that it initiates dataAt(Data,Node).
The case of countryY is expressed in the same way.
6.2.2. Data Transfer to an Adjacent Node
6.1.7. Owners of Nodes The action transfer transfers the specified data to the spec-
ified adjacent node.
The owner (company) of each node can be represented
as follows: action(transfer(Data,NodeFrom,NodeTo),[
dataAt(Data,NodeFrom),
connected(NodeFrom,NodeTo),
belief(nodeOwnedBy(node1,companyA)).
allowedTransfer(Data,NodeTo)
belief(nodeOwnedBy(node2,companyA)).
],[
belief(nodeOwnedBy(node3,companyA)).
initiates(dataAt(Data,NodeTo)),
belief(nodeOwnedBy(node4,companyA)).
terminates(dataAt(Data,NodeFrom))
belief(nodeOwnedBy(node5,companyA)).
]).
belief(nodeOwnedBy(node6,companyB)).
belief(nodeOwnedBy(node7,companyB)).
The aforementioned rule specifies that the pre-
6.1.8. Allowed Companies for Data Transfer conditions of the action are dataAt(Data,NodeFrom),
connected(NodeFrom,NodeTo), and allowedTransfer(Data,NodeTo).
Initially, we assumed that all data were allowed to be It also specifies that the effects of the action are to initiate
transferred in any company. However, this assumption dataAt(Data,NodeTo) and to terminate dataAt(Data,NodeFrom).
is subject to change and may be corrected by the legal The last precondition is defined as follows:
checker. Note that the analyzed data are also data. This
can be expressed for the case of companyA as follows: belief(allowedTransfer(Data,Node),[
nodeRegion(Node,Region),
allowedRegion(Data,Region),
dy(allowedCompany(_,_)). nodeOwnedBy(Node,Company),
belief(allowedCompany(dataHabit,companyA)). allowedCompany(Data,Company)
belief(allowedCompany(dataBehavior,companyA)). ]).
belief(allowedCompany(analysisOutput(
dataHabit,marketing),companyA)).
belief(allowedCompany(analysisOutput( This indicates that the transfer of Data to Node is allowed
dataBehavior,marketing),companyA)).
belief(allowedCompany(analysisOutput(
if the node is in an allowed region and is owned by an
dataHabit,advertising),companyA)). allowed company.
10
�6.2.3. Data Analysis 6.3.2. Delivery of Analytics
The action analyze analyzes the specified data at the spec- The task deliverAnalytics is the top-level task for obtaining
ified node for the specified purpose. The data must be the specified data from a DB at a node and delivering the
at the same location as the analyzer and the purpose of analysis output for a specific purpose to the recipient at
the data analysis must be allowed. The analysis output another node.
is obtained as new data after the data analysis,
htn(deliverAnalytics(Data,NodeFrom,NodeTo,Purpose),[
and the original data is erased. dbAt(Data,NodeFrom)
],[
action(analyze(Data,Node,Purpose),[ getDataFromDB(Data,NodeFrom),
analyzableAt(Data,Purpose,Node), multiStepTransfer(Data,NodeFrom,NodeAnalysis),
allowedPurpose(Data,Purpose), analyze(Data,NodeAnalysis,Purpose),
dataAt(Data,Node) multiStepTransfer(analysisOutput(Data,Purpose),
],[ NodeAnalysis,NodeTo)
initiates(dataAt(analysisOutput(Data,Purpose),Node)), ]).
terminates(dataAt(Data,Node))
]).
This rule specifies that to deliver the analysis result
The aforementioned rule specifies that the precondi- of Data for Purpose to the destination (NodeTo), the agent ob-
tions of the action are Data analyzable at Node for Purpose, tains Data from the DB at NodeFrom, transfers the data to
NodeAnalysis via multiple steps, analyzes the data for the
Data is allowed for Purpose, and Data is at Node. It also
specifies that the effects of the action are to initiate purpose, and transfer the analysis output to the destina-
dataAt(analysisOutput(Data,Purpose),Node), and to terminate
tion via multiple steps.
dataAt(Data,Node).
6.4. Costs of Tasks and Actions
6.3. Task Decomposition We set a specific value for each task and cost. The cost
The agent needs two abstract tasks to recursively decom- information is used for planning. The best-first search
pose to primitive tasks (actions) before execution. One will always find the lowest-cost plan if the cost of each
task is for transferring the specified data to the specified abstract task is less than or equal to the total cost of its
node via multiple nodes. The other task is the top-level primitive subtasks (actions), which we obtain by task
task for delivering the analysis output of the data for the decomposition.
specific purpose to the specified node.
6.4.1. Static Cost
6.3.1. Multi-Step Transfer We assume that the costs of abstract tasks are static and
The task multiStepTransfer is a compound task for transfer- set at the minimum value of 1.
ring data to another node via multiple nodes. This task is cost(deliverAnalysis(_,_,_,_),1).
recursively decomposed until the decomposed subtasks cost(multiStepTransfer(_,_,_),1).
include only the transfer actions.
Furthermore, we assume the costs of the getDataFromDB
htn(multiStepTransfer(Data,Node,Node),[ action and analyze action are static and the values are set
dataAt(Data,Node)
],[]). at 1.
htn(multiStepTransfer(Data,NodeFrom,NodeTo),[ cost(getDataFromDB(_,_),1).
dataAt(Data,NodeFrom), cost(analyze(_,_,_),1).
connected(NodeFrom,Node)
],[
transfer(Data,NodeFrom,Node), 6.4.2. Dynamic Cost
multiStepTransfer(Data,Node,NodeTo)
]).
The data transfer costs are subject to change. We assume
that the agent is aware that the line between node2 and
The first rule specifies that no action is required
node3 and the line between node3 and node5 are normally
for the transfer task multiStepTransfer(Data,Node,Node) when
slow. The data transfer costs become double if these lines
Data is already at the destination (dataAt(Data,Node)).
are used. These costs are set at 2.
The second rule specifies that when the data is at
NodeFrom and Node is an adjacent node, the transfer task cost(transfer(_,node2,node3),2).
multiStepTransfer(Data,NodeFrom,NodeTo) can be executed by
cost(transfer(_,node3,node5),2).
cost(transfer(_,node3,node2),2).
first transferring Data to the adjacent Node, then transfer- cost(transfer(_,node5,node3),2).
ring Data to the destination NodeTo via multiple steps.
The data transfer costs of the other lines are set at 1.
This cost information is expressed in the same way.
11
�6.5. Specific Task for Case Study 6.7. Dynamic Replanning after Legal
The specific task we consider in this case study is Check
deliverAnalytics(dataHabit, node2,node5,marketing) . As shown We assume that dataHabit has been retrieved from the
in Figure 9, the objective of this task is to deliver the anal- database at node2. The next action is to transfer the data
ysis output of dataHabit, which is stored in the database at to node1. Then, the legal checker indicates that it is illegal
node2, to node5. The purposed of the analysis is marketing. to transfer dataHabit to countryX. Subsequently, the agent
removes the following from its belief:
belief(allowedRegion(dataHabit,countryX)).
Because the precondition of the next action becomes
false, the planner modifies the plan as follows:
1. transfer(dataHabit,node2,node3)
2. transfer(dataHabit,node3,node4)
3. analyze(dataHabit,node4,marketing)
4. transfer(analysisOutput(dataHabit,marketing),node4,node7)
5. transfer(analysisOutput(dataHabit,marketing),node7,node5)
Figure 9: Given Task The modified plan is shown in Figure 11. We
can confirm that dataHabit is transferred only within
countryY, rather than via countryX. This indicates that
the legal norm is satisfied. Note that the action
6.6. Initial Planning getDataFromDB(dataHabit,node2) is erased from the plan be-
Considering the task, the planner creates the initial plan cause it has been executed.
as follows:
1. getDataFromDB(dataHabit,node2)
2. transfer(dataHabit,node2,node1)
3. transfer(dataHabit,node1,node4)
4. analyze(dataHabit,node4,marketing)
5. transfer(analysisOutput(dataHabit,marketing),node4,node7)
6. transfer(analysisOutput(dataHabit,marketing),node7,node5)
As shown in Figure 10, according to the aforemen-
tioned plan, dataHabit is retrieved from the database at
node2, transferred from node2 to node4 via node1, and ana-
lyzed for the purpose of marketing at node4. The analyzed
output is transferred from node4 to node5 via node3.
There are two data-transfer routes from node2 to node4. Figure 11: Legally Modified Plan
Similarly, there are two data-transfer routes from node4 to
node5. The planner selects the route with the lowest cost
using the best-first search. Note that the data-transfer
cost from node2 to node3 is set higher because the transfer 6.8. Dynamic Replanning after Ethical
speed is slow. Check
We assume that dataHabit has been analyzed at node4 for
the purpose of marketing. The next action is to transfer
the analysis output to node7. We assume that the ethical
checker indicates that it is not ethical to transfer the anal-
ysis output to companyB. Then, the agent takes the position
of utilitarianism and updates the cost of the next action
as follows:
cost(transfer(analysisOutput(dataHabit,marketing),node4,node7),
10).
The cost of the next action is now set at 10. Because
Figure 10: Initial Plan the cost of the next action has become much higher, the
planner dynamically modifies the plan as follows:
12
�1. transfer(analysisOutput(dataHabit,marketing),node4,node3) analysisOutput(dataHabit,marketing) was planned to be trans-
2. transfer(analysisOutput(dataHabit,marketing),node3,node5)
ferred to companyB, which is against the ethical norm.
When the dynamic replanning algorithm was applied
The modified plan is shown in Figure 12. In the
after legal check, dataHabit was planned to be transferred
modified plan, we can confirm that the analysis output
only within countryY. Therefore, the legal norm was com-
(analysisOutput(dataHabit,marketing)) is transferred within
plied with. However, analysisOutput(dataHabit,marketing)
companyA, rather than via companyB. This indicates that the
was still planned to be transferred to companyB, which is
ethical norm is respected, although it is not illegal to
against the ethical norm.
transfer it via companyB. Note that the planning agent does
When the dynamic replanning algorithm was ap-
not abandon the plan to transfer the analysis output via
plied both after legal check and ethical check, dataHabit
companyB. It is maintained as an alternative plan and will
was planned to be transferred only within countryY, and
be used only if there are no other options.
analysisOutput(dataHabit,marketing) was planned to be trans-
ferred only within companyA. Therefore, not only the legal
norm was complied with but also the ethical norm was
respected.
7. Discussion
From the case study, we can understand that the legal
norm of an action can be expressed as the precondition
of the action. This indicates that the illegal action cannot
be executed because its legal norm (precondition) is not
satisfied.
Figure 12: Ethically Modified Plan By contrast, the ethical norm of an action can be ex-
pressed as the cost of the action. The higher the cost
is, the more unethical the action is. Even if an action
is unethical, it is still legal to execute the action. If the
6.9. Evaluation on Computation Time planner can find the lower-cost plan, the agent can avoid
We implemented the planning agent, belief, and planning unethical action execution if possible. However, unethi-
knowledge in SWI Prolog for Windows 64-bit, version cal actions can still be executed if there is no other option.
8.2.4, which was installed on the Windows 10 Home PC Even in that case, it is possible to stop the action exe-
equipped with Intel(R) Core(TM) i7-1065G7 CPU and cution when its cost is too high, which means that the
the 32GB of RAM. We measured the CPU times for ini- action is too unethical.
tial planning, dynamic replanning after legal check, and Ethical norms of action can be expressed as the soft
dynamic replanning after ethical check five times each, constraints of the precondition, which should be satisfied
and the average CPU times were 0.003, 0.006, and 0.003 if possible but are not required. However, many planners
seconds, respectively. do not support soft constraints. Therefore, it is easier to
Therefore, this planner is adequate for practical use express ethical norms of action as the costs of the actions.
for the test case scenario in this study. In future, we It is not always possible to collect all the necessary
would like to evaluate the scalability for different types information at the time of initial planning, especially
and sizes of networks. One way to tackle the scalability when the latest information is distributed across multi-
problem is to use stratified multi-agent HTN planning ple servers. In the case study scenario in this paper, the
techniques [31, 32] where the parent agent first tries to planning agent obtains new information regarding the
find a rough data transfer route between the regions, and next action shortly before its execution. Legal and ethical
then its child agent tries to finds a detailed data transfer norms are checked at this time. Therefore, it is important
route inside the current region. to dynamically check and update the plan while execut-
ing it. Therefore, an online planning algorithm is used in
this paper.
6.10. Evaluation on Compliance with
Legal and Ethical Norms
In the test case scenario, in initial planning, nei-
8. Conclusion
ther legal norms nor ethical norms were ignored. We have shown how to represent knowledge about legal
In other words, dataHabit was planned to be trans- and ethical norms using an online total-order forward-
ferred to countryX, which is against the legal norm, and chaining HTN planning algorithm in the domain of data
13
�transfer and utilization in multiagent systems. The pre- 2021. https://www.cse.unsw.edu.au/~cme2021/
condition of an action was used for its legal check, how- CME2021_paper_Satoh.pdf (Accessed on 07 Feb.
ever, the cost of an action was used for its ethical check. 2022).
Dynamic adaptation to legal/ethical norms was achieved [7] H. Hayashi, S. Tokura, T. Hasegawa, F. Ozaki, Dyna-
by dynamic replanning after legal/ethical check. These gent: An incremental forward-chaining HTN plan-
techniques are extremely important when the latest in- ning agent in dynamic domains, in: Declarative
formation, which may affect legal/ethical norms, is dis- Agent Languages and Technologies III, number 3904
tributed across multiple servers. Experiment results con- in LNAI, Springer, 2006, pp. 171–187.
firmed that this planner is adequate for practical use in [8] D. Nau, Y. Cao, A. Lotem, H. Mũnoz-Avila, SHOP:
terms of computation time in our case study. simple hierarchical ordered planner, in: Interna-
Furthermore, we have designed a system architecture tional Joint Conference on Artificial Intelligence,
that combines the online planning agent with external 1999, pp. 968–975.
legal and ethical checkers. External legal and ethical [9] G. Behnke, D. Höller, S. Biundo, totSAT — totally-
checkers will be useful when the laws and ethical guide- ordered hierarchical planning through SAT, in:
lines are complicated. In the future, we would consider International Conference on Autonomous Agents
implementing the overall system. In addition, we would and Multiagent Systems, 2018, pp. 6110–6118.
consider designing an explainable dynamic planner that [10] M. C. Magnaguagno, F. Meneguzzi, L. Silva, Hyper-
can explain the reason for plan modification to the users TensioN: A three-stage compiler for planning, in:
in terms of legal and ethical norms. 10th International Planning Competition: Planner
and Domain Abstracts – Hierarchical Task Network
Planning Track, 2021, pp. 5–8.
Acknowledgments [11] D. Schreiber, Lilotane: A lifted sat-based approach
to hierarchical planning, Journal of Artificial Intel-
This work was supported by JST, AIP Trilateral AI Re-
ligence Research 70 (2021) 1117–1181.
search, Grant No. JPMJCR20G4 and JSPS KAKENHI,
[12] E. Sacerdoti, A Structure for Plans and Behavior,
Grant No. JP19H05470 and JP21K12144.
Elsevier, 1977.
[13] A. Tate, Generating project networks, in: Interna-
References tional Joint Conference on Artificial Intelligence,
1977, pp. 888–893.
[1] Agarwal, S. Steyskal, F. Antunovic, S. Kirrane, Leg- [14] D. Wilkins, Practical Planning, Morgan Kaufmann,
islative compliance assessment: Framework, model 1988.
and GDPR instantiation, in: Annual Privacy Forum, [15] K. Currie, A. Tate, O-plan: The open planning
2018, pp. 131–149. architecture, Artificial Intelligence 52 (1991) 49–86.
[2] M. Palmirani, M. Martoni, A. Rossi, C. Bartolini, [16] D. Höller, G. Behnke, P. Bercher, S. Biundo, H. Fior-
L. Robaldo, Legal ontology for modelling GDPR ino, D. Pellier, R. Alford, HDDL: An extension to
concepts and norms, Legal Knowledge and Infor- PDDL for expressing hierarchical planning prob-
mation Systems (2018) 91–100. lems, in: AAAI Conference on Artificial Intelli-
[3] M. D. Vos, S. Kirrane, J. Padget, K. Satoh, ODRL pol- gence, 2020, pp. 9883–9891.
icy modelling and compliance checking, in: Inter- [17] D. Nau, H. Mũnoz-Avila, Y. Cao, A. Lotem,
national Joint Conference on Rules and Reasoning, S. Mitchell, Total-order planning with partially or-
2019, pp. 36–51. dered subtasks, in: International Joint Conference
[4] P. A. Bonatti, S. Kirrane, I. M. Petrova, L. Sauro, on Artificial Intelligence, 2001, p. 425–430.
Machine understandable policies and GDPR com- [18] H. Hayashi, S. Tokura, F. Ozaki, M. Doi, Background
pliance checking, KI - Künstliche Intelligenz 34 sensing control for planning agents working in the
(2020) 303–315. real world, International Journal of Intelligent In-
[5] Y. Taheri, G. Bourgne, J.-G. Ganascia, A compli- formation and Database Systems 3 (2009) 483–501.
ance mechanism for planning in privacy domain [19] H. Hayashi, H. Ogawa, N. Matsuhira, HTN plan-
using policies, in: International Workshop on Juris- ning for pick-and-place manipulation, in: Interna-
informatics, JSAI International Symposia on AI, tional Conference on Agents and Artificial Intelli-
2021. gence, 2013, pp. 383–388.
[6] K. Satoh, J.-G. Ganascia, G. Bourgne, A. Paschke, [20] H. Hayashi, H. Ogawa, N. Matsuhira, Comparing
Overview of RECOMP project, in: Interna- repair-task-allocation strategies in MAS, in: In-
tional Workshop on Computational Machine ternational Conference on Agents and Artificial
Ethics, International Conference on Principles Intelligence, 2015, pp. 17–27.
of Knowledge Representation and Reasoning, [21] S. Patra, M. Ghallab, D. Nau, P. Traverso, Acting and
14
� planning using operational models, in: AAAI Con-
ference on Artificial Intelligence, 2019, pp. 7691–
7698.
[22] S. Patra, J. Mason, A. Kumar, M. Ghallab,
P. Traverso, D. Nau, Integrating acting, planning,
and learning in hierarchical operational models, in:
International Conference on Automated Planning
and Scheduling, 2020, pp. 478–487.
[23] M. Shanahan, Prediction is deduction but explana-
tion is abduction, in: International Joint Conference
on Artificial Intelligence, 1989, pp. 1055–1060.
[24] R. Kowalski, M. Sergot, A logic-based calculus of
events, New Generation Computing 4 (1985) 67–95.
[25] V. Lifschitz, Answer Set Programming, Springer,
2019.
[26] R. Miller, Notes on deductive and abductive plan-
ning in the event calculus, in: AISB Workshop on
Practical Reasoning and Rationality, 1997.
[27] M. Shanahan, An abductive event calculus planner,
The Journal of Logic Programming 44 (2000) 207–
239.
[28] F. Berreby, G. Bourgne, J.-G. Ganascia, A declarative
modular framework for representing and applying
ethical principles, in: International Conference on
Autonomous Agents and Multiagent Systems, 2017,
p. 96–104.
[29] F. Berreby, G. Bourgne, J.-G. Ganascia, Event-
based and scenario-based causality for computa-
tional ethics, in: International Conference on Au-
tonomous Agents and Multiagent Systems, 2018,
pp. 147–155.
[30] F. Lindner, R. Mattmüller, B. Nebel, Evaluation of
the moral permissibility of action plans, Artificial
Intelligence 287 (2020) 1–14.
[31] H. Hayashi, Stratified multi-agent htn planning
in dynamic environments, in: KES International
Symposium on Agent and Multi-Agent Systems:
Technologies and Applications, 2007, pp. 189–198.
[32] H. Hayashi, Towards real-world htn planning
agents, in: Knowledge Processing and Decision
Making in Agent-Based Systems, 2009, pp. 13–41.
15
�