# E-PDDL: A Standardized Way of Defining Epistemic Planning Problems

Francesco Fabiano
DMIF Department
University of Udine, Italy
<EMAIL_ADDRESS>&Biplav Srivastava
AI Institute
University of South Carolina, Columbia, USA
<EMAIL_ADDRESS>&Marianna Bergamaschi Ganapini
Philosophy Department
Union College, NY, USA
<EMAIL_ADDRESS>Jonathan Lenchner  Lior Horesh  Francesca Rossi
Thomas J. Watson Research Center, Yorktown Heights, NY USA
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

> _Epistemic Planning_ (EP) refers to an automated planning setting where the
> agent reasons in the space of knowledge states and tries to find a plan to
> reach a desirable state from the current state. Its general form, the
> _Multi-agent Epistemic Planning_ (MEP) problem involves multiple agents who
> need to reason about both the state of the world and the information flow
> between agents. In a MEP problem, multiple approaches have been developed
> recently with varying restrictions, such as considering only the concept of
> _knowledge_ while not allowing the idea of _belief_ , or not allowing for
> “complex” modal operators such as those needed to handle _dynamic common
> knowledge_. While the diversity of approaches has led to a deeper
> understanding of the problem space, the lack of a standardized way to
> specify MEP problems independently of solution approaches has created
> difficulties in comparing performance of planners, identifying promising
> techniques, exploring new strategies like ensemble methods, and making it
> easy for new researchers to contribute to this research area. To address the
> situation, we propose a unified way of specifying EP problems - the
> Epistemic Planning Domain Definition Language, E-PDDL. We show that E-PPDL
> can be supported by leading MEP planners and provide corresponding parser
> code that translates EP problems specified in E-PDDL into (M)EP problems
> that can be handled by several planners. This work is also useful in
> building more general epistemic planning environments where we envision a
> meta-cognitive module that takes a planning problem in E-PDDL, identifies
> and assesses some of its features, and autonomously decides which planner is
> the best one to solve it.

## Motivation

Multi-agent scenarios are ubiquitous in everyday life. We often need to make
decisions based on information on the problem to be solved and on our
knowledge, or belief, about the preferences and actions of other agents
involved in, or impacted by, the decision. It is therefore an epistemic
reasoning task to make decisions in this scenarios.

Often such decision involve creating a plan, that is, a sequence of actions
that, when executed, will lead to a desired goal state. The research area of
_Multi-agent Epistemic Planning_ (MEP) attempts to build artificial agents
that can build such plans. MEP is a generalization of the concept of
_Epistemic Planning_ (EP), which refers to a single agent setting that reasons
about knowledge and beliefs. In the MEP scenario, agents also reason about the
information that other agents have of each other, and how such information
flows between agents.

Several approaches to develop epistemic solvers/planners have been made across
the community, see for example (?; ?; ?). While these solvers may have
different restrictions, considering only the concept of _knowledge_ while not
allowing the idea of _belief_ , or not allowing for _dynamic common knowledge_
, all of them share the same goal: to plan while considering the information
flows between the agents.

While the diversification of approaches in solving this problem certainly
brings benefits to the entire community, with many specialized efficient
planners that are suitable for specific scenarios, the lack of a standardized
way to define input problems in multi-agent epistemic planning has led to the
creation of ad-hoc languages that can become an obstacle when comparing,
combining (i.e., ensemble), or testing different planners. We believe that a
unified way of expressing MEP problems would provide researchers with a faster
and less error-prone way of defining standardized benchmarks and would also
relieve them from the burden of having to learn a new language each time they
need to make use of a different tool. Moreover, it would allow for easy
transfer of techniques and results between different planning scenarios and
planner methodologies.

In this paper we therefore propose the Epistemic Planning Domain Definition
Language (E-PDDL), a unified way of defining epistemic problems that,
similarly to the well-known language PDDL for classical planning, could be
regarded as the standard language to be used to express MEP problems. Being
able to define MEP problems in E-PPDL and then to map them into specific
languages for existing planners provides also the necessary environment for a
real-time choice of the best planner for a given MEP problem. Indeed, this
work is part of a larger effort that aims to equip artificial agents with
meta-cognitive capabilities that, given internal values, resources, and
criteria, can identify some of the problem features and assess what skills are
required to best solve it. In the context of this paper, this would mean to be
able to select the most suitable planner for a MEP problem. This is greatly
facilitated if there is a way to map the input problem specification into the
language required by each specific planner.

In the rest of the paper, we first give necessary background about EP and MEP
with a running example. We then introduce the E-PDDL language and its key
features, and we show how it encompasses current MEP formalisms. Next, we
highlight implementation details in the parser and conclude.

## Background

Recently the concept of Artificial Intelligence has gained a lot of momentum
both inside and outside the computer science research community. We are, in
fact, witnessing an increasing number of autonomous tools that help users in
tasks that range from the trivial and ordinary to the complex and very
specialized. In particular, the area of automated planning, that has always
been widely employed especially at the industrial level, has been constantly
pushed towards improvement. Nowadays planners and schedulers are able to solve
complex tasks in very short times while also accounting for factors such as
incomplete knowledge, non-determinism, fault occurrences and so on (?; ?; ?).

However, the main focus of these research efforts has been about reasoning
within single agent domains. This type of setting mainly requires the agent to
characterize her knowledge about the world and understand in which way she can
manipulate it in order to achieve a particular goal. But, while the single-
agent setting can be satisfactory in many scenarios, multi-agent planning can
be adopted to characterize a wider spectrum of real-world situations. It is
therefore natural that, thanks to the increasing interest in the area and the
more powerful hardware support, the planning problem is now also broadly
studied in the context of multiple agents.

### Multi-Agent Epistemic Planning

Nevertheless, the presence of numerous agents in the planning setting poses a
number of challenges: among which is to study the information flows that
occurs between the agents. The area of planning that reasons in an
environments where these streams of “knowledge” need to be considered is known
as _Epistemic Multi-Agent Planning_ , or simply MEP (see (?; ?) for a more
detailed introduction to the topic). MEP derives from the well-known research
area of _Dynamic Epistemic Logic_ which uses logic to formalize and reason and
reason on both the state of the world and on the _information change_ in
dynamic domains. To be more concrete, as stated in (?), “ _information_ is
something that is relative to a subject who has a certain perspective on the
world, called an _agent_ , and that is meaningful as a whole, not just loose
bits and pieces. This makes us call it _knowledge_ and, to a lesser extent,
_belief_.” In what follows, for brevity, we use the term “knowledge” to
encapsulate both the notions of an agent’s knowledge and beliefs with respect
to some information. The concepts of knowledge and beliefs are captured by the
same modal operator in Dynamic Epistemic Logic and their difference resides in
structural properties that the epistemic states respect (see (?) for more
details). This means that thanks to epistemic planners we are able to reasons
on domains where the actions of the agents affect, and are affected, by the
state of the world and the knowledge of the agents (about both the world and
the others’ knowledge).

As already mentioned, MEP is concerned with information change and inherits
concepts from Dynamic Epistemic Logic (DEL). In particular, the language of
well-formed DEL formulae used to express agents’ knowledge, is defined as
follows:

$\varphi::=\mathsf{f}\mid\neg\varphi\mid\varphi\wedge\psi\mid\textbf{B}_{\mathsf{i}}\varphi\mid\textbf{C}_{\mathsf{\alpha}}\varphi,$

where $\mathsf{f}$ is a propositional atom called a _fluent_ , $\mathsf{i}$ is
an agent that belongs to the set of agents $\mathcal{AG}$ s.t.
$|\mathcal{AG}|\geq 1$, $\varphi$ and $\psi$ are belief formulae and
$\emptyset\neq\alpha\subseteq\mathcal{AG}$. A _fluent formula_ is a DEL
formula with no occurrences of modal operators. A _belief formula_ is
recursively defined as follows:

  * •

A fluent formula is a belief formula;

  * •

If $\varphi$ is a belief formula and $\mathsf{i}\in\mathcal{AG}$, then
$\textbf{B}_{\mathsf{i}}{\varphi}$ (“$\mathsf{i}$ knows/believes that
$\varphi$”) is a belief formula where the modal operator
$\textbf{B}_{\mathsf{}}$ captures the concept of _knowledge_ ;

  * •

If $\varphi_{1},\varphi_{2}$ and $\varphi_{3}$ are belief formulae, then
$\neg\varphi_{3}$ and $\varphi_{1}\,\mathtt{op}\,\varphi_{2}$ are belief
formulae, where $\mathtt{op}\in\\{\wedge,\vee,\Rightarrow\\}$;

  * •

If $\varphi$ is a belief formula and
$\emptyset\neq\alpha\subseteq\mathcal{AG}$ then
$\textbf{C}_{\mathsf{\alpha}}\varphi$ is a belief formula where
$\textbf{C}_{\mathsf{\alpha}}$ captures the _Common knowledge_ of the set of
agents $\alpha$.

The formula $\textbf{C}_{\mathsf{\alpha}}\varphi$ translates intuitively into
the conjunction of the following belief formulae:

  * •

every agent in $\alpha$ knows $\varphi$;

  * •

every agent in $\alpha$ knows that every agent in $\alpha$ knows $\varphi$;

  * •

and so on _ad infinitum_.

The semantics of DEL formulae is traditionally expressed using _pointed Kripke
structures_ (?). We refer the interested reader to (?; ?; ?) for a
comprehensive introduction to how Kripke structures or similar formalisms are
used to capture the idea of an epistemic state and how the concept of
entailment is defined.

In this paper, we will make use of the Coin in the Box domain (Example 1),
first introduced in (?), as a running example. In particular, we will present
a three agent instance of this epistemic domain that will allow us to better
illustrate some of the concepts we will later introduce.

######  Example 1 (Coin in the Box).

Three agents, $\mathsf{A}$, $\mathsf{B}$, and $\mathsf{C}$, are in a room
where in the middle there is a box containing a coin. In the initial state it
is known that:

  * •

none of the agents know whether the coin lies heads or tails up;

  * •

the box is locked and one needs a key to open it;

  * •

some agents (usually only $\mathsf{A}$) have the key to the box;

  * •

in order to learn whether the coin lies heads or tails up, an agent can peek
into the box, but this requires the box to be open; and

  * •

agents can be either attentive or not towards the box.

Agents can perform the following actions, which have a straightforward
meaning:

  * •

_Opening_ the box;

  * •

_Peeking_ into the box;

  * •

_Signaling_ another agent;

  * •

_Distracting_ another agent; and

  * •

_Announcing_ the coin position.

### Action Languages

The field of planning has seen many representations. For example, in classical
planning, there was STRIPS (?), Action Description Language (ADL) (?) and SAS+
(?) before Planning Domain Description Language (PDDL) (?; ?) standardized the
notations. Nowadays, planners routinely use PDDL for problem specification
even if they may convert to other representations later for solving efficiency
(?). PDDL envisages two files, a domain description file which specifies
information independent of a problem like predicates and actions, and a
problem description file which specifies the initial and goal states. PDDL
provides a relaxed specification of the output plan – it is a series of time
steps, each of which can have one or more instantiated actions with
concurrency semantics. Specification of the correctness of plans was
formalized much later when tools like VAL were created (?).

In PDDL, a planning environment is described in terms of objects in the world,
predicates that describe relations that hold between these objects, and
actions that bring change to the world by manipulating relations. A problem is
characterized by an initial state, together with a goal state that the agent
wants to transition to, both states specified as configurations of objects.
When planning is used for epistemic reasoning, the objects in the problem can
be physical (real world objects) as well as abstract (knowledge and beliefs).

#### Epistemic Action Languages

We briefly present the action languages adopted by two different epistemic
solvers: RP-MEP (?) and EFP (?). We chose these solvers as, in is our opinion,
they represent the state of the art epistemic planners. The former, RP-MEP,
adopts a conversion to classical planning in order to tackle epistemic
reasoning while the latter, EFP, comprehensively reasons on full-fledged
epistemic states. While the two planners are able to solve the same families
of domains, important differences in their solving strategies make certain
problem instances more suited to one approach rather than the other. For a
detailed comparison of the solvers refer to (?; ?). The main objective of this
paper is to present a unified way of providing problem specification for the
epistemic planning community so that the planners, starting from the two
considered here, can be easily tested, confronted or even combined.

_PDKB-PDDL_ Let us start by presenting the main characteristics of the action
language PDKB-PDDL adopted by the solver RP-MEP (?; ?). This action language
clearly stems from PDDL, the de-facto standard for single-agent action
languages, and allows one to express formulae that contain the modal operator
$\textbf{B}_{\mathsf{}}$. While this language seems to represent a version of
PDDL that is suitable for epistemic reasoning, there are some limitations that
render PDKB-PDDL not general enough for this purpose. In fact, while this
language inherits the files schema from PDDL, also allowing for parametric
action definitions, the epistemic components of the actions’ description are
tailored for the RP-MEP solving process. This makes PDKB-PDDL not flexible
enough to be adopted as an input specification language for other planners
(EFP). In particular, what makes this language not suitable for every
epistemic approach is that, in order to have a valid PDKB-PDDL domain, each
action must specify the entirety of its effects explicitly. While this is a
common procedure in other types of reasoning in epistemic planning, the need
for explicit effects specification brings some limitations. To be more
concrete, each action in PDKB-PDDL needs to define not only how the action
itself modifies the world but also how the knowledge of the agents are
updated—that is, the belief update of each action needs to be explicit. This
requirement is limiting because epistemic planners (EFP) may reason through
implicit knowledge update111The distinction between explicit and implicit
knowledge update derives from the fact that RP-MEP grounds the problem while
EFP reasons directly on epistemic states. and therefore “automatically” derive
how the the agents change their knowledge after an action execution. While
having explicit updates allows one to freely characterize each action’s
effects (in Example 1 it would be possible to define a new action in which an
agent opens the box but will believe that the coin is tails up), we feel that
leaving such detail as input is partially in contrast with the idea of
autonomous epistemic reasoning. Furthermore, it is easy for the user to
inadvertently omit or mis-characterize “intricate” knowledge relations that
should instead be handled by the autonomous solving process. For example, in
writing the effects _peeking_ of Example 1 the effect “the agent who peeked
inside the box knows that the attentive agents know that he knows the coin
position but the attentive agents themselves do not know the position of the
coin” may be misrepresented. This chain of knowledge is derived by partial
observability (explained in the following paragraph) and, as well as other
complex knowledge structures, may be easily mis-characterized given its
complex and not intuitive nature.

_$m\mathcal{A}^{\rho}$_ We can now introduce $m\mathcal{A}^{\rho}$, the
language used to describe inputs for EFP (?). This language is an evolution of
$m\mathcal{A}+$ first introduced in (?). Unlike PDKB-PDDL,
$m\mathcal{A}^{\rho}$ does not take inspiration from PDDL and introduces an
ad-hoc syntax to define epistemic problems. This syntax, illustrated in detail
in (?; ?), describes an input problem through a single file that specifies
initial and goal states (or rather the belief formulae that identify such
states) along with the actions making each file a problem instance. Moreover,
unlike the input language of RP-MEP, $m\mathcal{A}^{\rho}$ defines only
implicit effects and by associating each action with the agents’ observability
relations (which agent is aware of the action’s occurrence and/or effects) and
with a “type” (world-altering, sensing and announcement) is able to derive the
complete knowledge update. In particular, in (?), each action execution act
associates each agent $\mathsf{ag}$ to one of the following observibility
relations:

  * •

_fully observant_ if $\mathsf{ag}$ knows about the execution of act and about
its effects on the world (any attentive agent that witnessed the opening of
the box in Example 1);

  * •

_partially observant_ if $\mathsf{ag}$ knows about the execution of act but
she does not know how act affected the world (any attentive agent that sees
another agent _peeking_ inside the box in Example 1); and

  * •

_oblivious_ if $\mathsf{ag}$ does not know about the execution of act (any
non-attentive agent during the execution of any action in Example 1).

Moreover, as noted before, each action is associated with one of the following
“types”:

  * •

_World-altering_ (or _ontic_) action, used to modify certain properties
(fluents) of the world, the action of _opening_ of Example 1.

  * •

_Sensing_ action: used by an agent to refine her beliefs about the world, the
action of _peeking_.

  * •

_Announcement_ action: used by an agent to affect the beliefs of other agents
in Example 1 the action of _announcing_.

While this language is able to characterize implicit knowledge updates (from
which the explicit effects can be derived), it lacks the structure of PDDL and
relies on a custom syntax that may pose an obstacle to any researcher that is
trying to approach the area of epistemic planning. Moreover, another problem
of $m\mathcal{A}^{\rho}$ is the lack of parametric actions that, in several
cases, forces the user to repeat the definition of the same action, with small
variations, over and over.

## E-PDDL

In what follows we present E-PDDL making use of the Coin in the Box domain
(Example 1) to better explain some of the features. Let us remark that the
syntax has been chosen with the objective of minimizing the difference with
standard PDDL while providing a general epistemic input language. We will
start by showing the syntax of the problem-_domain_ —that contains the general
settings of the problem—and then we will illustrate how a problem-_instance_
—that contains specific objects, initial conditions and goals—is
characterized. In particular in Listings 1 we present the characterization of
the Example 1 problem-_domain_ and in Listings 2 we present a simple problem-
_instance_ where it is known that agent $\mathsf{a}$ has the key and the goal
is for $\mathsf{a}$ to know the coin position. Before proceeding with the
description of the E-PDDL syntax we need to introduce the meaning of the
operator “$\mathtt{[\mathsf{i}]}$” where $\mathsf{i}\in\mathcal{AG}$. This
operator captures the modal operator $\textbf{B}_{\mathsf{\mathsf{i}}}$. For
example in Line 13 of Listings 1 the formula $\mathtt{[?\mathsf{i}](has\\_key\
?\mathsf{i})}$ reads “agent $\mathsf{i}$ knows
$\mathtt{has\\_key\\_\mathsf{i}}$” where $\mathsf{i}\in\mathcal{AG}$ and the
fluent $\mathtt{has\\_key\\_\mathsf{i}}$ encodes the fact that $\mathsf{i}$
has the key. When the operator is of the form “[$\alpha$]” where
$\alpha\subseteq\mathcal{AG}$ and $|\alpha|\geq 2$ then it captures the idea
of common knowledge.

### Problem _Domain_

First of all let us note that in Listings 1 the actions $\mathtt{signal}$ and
$\mathtt{distract}$ are omitted to avoid clutter. In fact, these actions are
world-altering and, therefore, share a similar structure with the action
$\mathtt{open}$.

Following the PDDL syntax (?) we start the problem-_domain_ definition by
defining the name and the requirements of the problem (Lines 1 and 2-3 of
Listings 1, respectively). We included a new requirement called
$\mathtt{:mep}$ to identify the need for E-PDDL. In Lines 5-8 are introduced
the predicates following the PDDL standard. A small variation is the _object-
type_ $\mathtt{agent}$ that does not need to be defined and is used to define
variables that capture the acting agents.

From Line 10 to Line 19 the action $\mathtt{open}$ is introduced. The action’s
definition starts with its _name_ (Line 10) and its _type_ (Line 11). The
concept of action type is inherited from $m\mathcal{A}^{\rho}$ and for now is
restricted to be one among ontic, sensing or announcement since these are the
accepted variations of an action in the MEP community. This concept allows to
apply the right transition function in the context of implicit knowledge
update. We plan, for the future, to include custom action types through the
definition of custom event models (see (?) for a better introduction on this
topic). Since such feature needs to be also implemented in the epistemic
planners, we leave this contribution as a future work. Next, in Line 12 and
Line 13, respectively, the action’s _parameters_ and _preconditions_ are
defined. The parameters have the same role that they have in PDDL, that is
they are used to associate the variables of the action’s definition with an
_object type_. Similarly, also the field preconditions—identified by any
belief formula—follow the standard PDDL meaning. Following the preconditions
the action specify the _effects_. The effects, contrarily from the
preconditions, cannot contain arbitrary belief formulae. In fact, depending on
the action type, only fluents or special fluent formulae are allowed. In
particular, ontic actions allow for conjunctions of fluents while epistemic
actions (sensing and announcements) can only consider single fluents as
effects. These limitations, inherited by $m\mathcal{A}^{\rho}$, are necessary
for planners that reason on epistemic transition functions. We address the
reader to (?) for a more detailed description of the motivations behind these
limitations. Finally, the last field of the action $\mathtt{open}$ is about
the _observer_ s. This field is used to indicate which agents are fully
observant, knows about the execution and the effects of the action. Knowing
which agent is observant is once again useful to derive how the knowledge of
the agents is updated after the action is been executed. To better
characterize the set of observant agents we introduced the operator
$\mathtt{diff}$ that allow to “isolate” the executor of the action (since the
executor needs to be observant and should not depend on other factors). For
example, the condition in Lines 15-17 reads as: “the agent $\mathsf{i}$, the
executor, is fully observant” (Line 15) and “for every agent $\mathsf{j}$
$\neq$ $\mathsf{i}$ if $\mathsf{j}$ $\mathtt{is\ looking}$ then $\mathsf{j}$
is fully observant” (Lines 16-17). The same schema is used to define partial
observers, the ones that are aware of the action execution but do not know the
results of such action, with the field _p_observers_ ; an example of partial
observability is at Line 27.

⬇

1(define (domain coininthebox)

2 (:requirements :strips

3 :negative-preconditions :mep)

4

5 (:predicates (opened)

6 (has_key ?i - agent)

7 (looking ?i - agent)

8 (tail))

9

10 (:action open

11 :act_type ontic

12 :parameters (?i - agent)

13 :precondition ([?i](has_key ?i))

14 :effect (opened)

15 :observers (and (?i)

16 (forall(diff(?j-agent)(?i))

17 (when(looking ?j) (?j))))

18 )

19

20 (:action peek

21 :act_type sensing

22 :parameters (?i - agent)

23 :precondition (and ([?i](opened))

24 ([?i](looking ?i)))

25 :effect (tail)

26 :observers (?i)

27 :p_observers (forall(diff(?j-agent)(?i))

28 (when(looking ?j) (?j)))

29 )

30

31 (:action announce

32 :act_type announcement

33 :parameters (?i - agent)

34 :precondition ([?i](tail))

35 :effect (tail)

36 :observers (and (?i)

37 (forall(diff(?j-agent)(?i))

38 (when(looking ?j) (?j))))

39 )

40)

Listing 1: E-PDDL Coin in the Box problem-_domain_.

The introduced fields are tailored for implicit knowledge update but in
Section “From Implicit to Explicit Knowledge Update” we will explain how, with
the presented syntax, it is possible to generate a valid input also for those
planners that need the effects of the action to be completely explicit.

### Problem _Instance_

In Listings 2 we present an example of an E-PDDL problem-_instance_. In Line 1
and in Line 2 the problem-_instance_ name ($\mathtt{toyinstance}$) and the
related problem-_domain_ name are defined, respectively.

Next, in Line 3, the _object type_ $\mathtt{agent}$ values are defined. In
this particular instance we defined three agents $\mathsf{a}$, $\mathsf{b}$
and $\mathsf{c}$ as in Example 1.

Following, in Line 4, the $\mathtt{depth}$ is specified. The concept of depth
of a belief formula is used to identify the number of _nested_ epistemic
operators. For example, given two agents $\mathsf{i}$ and $\mathsf{j}$ the
belief formula $\textbf{B}_{\mathsf{i}}\varphi$ has depth 1 while
$\textbf{B}_{\mathsf{i}}\textbf{C}_{\mathsf{i,j}}\varphi$ has depth 2. This
field is introduced to accommodate the need for certain planners, RP-MEP, to
limit the depth of the belief formulae. In fact RP-MEP relies on grounding the
formulae into classical planning “facts” and without bound on these formulae
could be infinite. On the other hand, the limit on depth is ignored by the
planners, EFP, that reason directly on epistemic states.

Lines 5-12 present the belief formulae that describe the initial state. The
formulae are considered to be in conjunction with each other. The _initial
conditions_ only require to specify when a fluent is true and consider false
whichever fluent is not specified (Line 5). Moreover the initial conditions
are also used to specify what is known in the initial state (Line 6-12). While
the belief formulae in this field can be of any type, let us remark that in
(?) it is demonstrated that to create a finite number of epistemic states from
a set of formulae, this set must respect a finitary S5 logic and therefore the
knowledge must be expressed in terms of common knowledge. This means that if
the initial conditions do not comply with a finitary S5 logic the planners
that construct the initial epistemic state from the given specification may
not work.

Finally in Line 13 the conjunction of belief formulae that represent the goals
is defined. Here, to respect Example 1, only the goal that reads “$\mathsf{a}$
knows that the coin is tails up” is written.

⬇

1(define (problem toyinstance)

2 (:domain coininthebox)

3 (:agent a b c)

4 (:depth 2)

5 (:init (tails) (has_key a) (looking a)

6 ([a b c](has_key a))

7 ([a b c](not (has_key b)))

8 ([a b c](not (has_key c))))

9 ([a b c](not (opened)))

10 ([a b c](looking a))

11 ([a b c](not (looking b)))

12 ([a b c](not (looking c))))

13 (:goal ([a](tails)))

14)\end{lstlisting}

15%\end{minipage}

16%(:depth 1) ; Only used by System 1 planner

17

18\subsection{\impltoexpl}\label{subsec:expl}

19Since we tailored E-PDDL syntax to represent actions with implicit \knobel
update we need to explain how E-PDDL itself is a suitable language also for
those planner, \eg \rpmep, that need the \knobel update to be explicit.

20That is, we need a standard way of deriving the explicit agents’ \knobel
update from an E-PDDL action description.

21While deriving explicit \knobel update is not a method that is embedded in
the language itself in what follows we propose the strategy that we adopted in
our implemented parser (presented in the following Section).

22

23The strategy that we adopted in our parser is based
on~\cite{baral2015action} transition function where the idea of agents’
observability is used to derive consistent agents’ \knobel about the actions
effects and/or execution.

24In what follows we present a \emph{\knobel derivation schema} that, starting
from the agents’ observability, is able to generate the explicit \knobel
update related to a single action. These updates generate all the \knobel-
chains of finite length $\ell$ where $\ell \in \\{0,\dots,\mathtt{d}\\}$ and
$\mathtt{d}$ is the value assigned to the field \codetext{:depth} in the
\probinst (in Listings~\ref{lst:instance} $\mathtt{d} = 2$).

25Namely we will have all the following chains:

26\begin{itemize}

27 \item a fully observant knows the action’s effect ($\ell = 1$);

28 \item a fully observant knows that another fully observant knows the
action’s effect ($\ell = 2$);

29 \item a fully observant knows the chains of length 2 ($\ell = 3$);

30 \item and so on until we have that $\ell = \mathtt{d}$.

31\end{itemize}

32

33\noindent Moreover, when partially observant agents are defined we also need
to take into consideration their perspective on the \knobel update.

34To do that we will need to automatically generate the following \knobel-
chains (still limited by the given depth):

35\begin{itemize}

36 \item a partially observant knows that any chain of fully observant agents
knows the action’s effect ($\ell = 2$); and

37 \item any chain, with $\ell \leq \mathtt{d}-2$, of fully/partially
observant knows the chain of \knobel presented in the previous point.

38\end{itemize}

39In order to better integrate explicit \knobel update we decided to
incorporate E-PDDL with an extra, non-mandatory field for the actions’
specification.

40This field, identified by \codetext{:exp\_effect} can be used to the
identify the explicit \knobel update of the action by using an arbitrary
belief formula.

41Let us note that when this field is defined it will completely override the
automatically derived \knobel update for the planners that make use of
explicit \knobel update, \eg \rpmep.

42On the other hand, planners that make use of a full fledged epistemic
transition function, \eg \EFP, will ignore the \codetext{:exp\_effect} field.

Listing 2: E-PDDL Coin in the Box problem-_instance_.

## An E-PDDL Parser

In this Section we will present the implementation of an E-PDDL parser. This
parser is able to take E-PDDL problem-_domain_ and problem-_instance_ files
and automatically generate corresponding inputs for the solvers RP-MEP and
EFP. That is, the main objective of our parser is to generate a PDKB-PDDL and
a $m\mathcal{A}^{\rho}$ description of the given input. While this is just a
first step of the integration of E-PDDL in the epistemic planning community,
thanks to our parser RP-MEP and EFP can already exploit the newly presented
syntax. Moreover, this parser allows to better compare and/or even combine the
two approaches. Therefore, the presented approach may help in building a more
general epistemic planning environment where, thanks also to a meta-cognitive
reasoning module, takes a planning problem in E-PDDL, identifies and assesses
some of its features, and autonomously decides which planner is the best one
to solve it.

The parser source code, along with some examples and a small guide on how to
use the code itself, is available at the following url:
https://github.com/FrancescoFabiano/E-PDDL. Our E-PDDL parser is written in
Python3 (?) and inherits its basic structure from an open source PDDL parser
(?).

As already said the objective of the parser is to “transform” an E-PDDL input
into files that can be directly used as input for either RP-MEP or EFP. The
idea is to provide the researchers with a tool that generates an output that
can be directly used by the two above-mentioned planners.

While elaborating upon the details of the code will be tedious and not
informative we decide to show the result of the parsing process. In Listings 3
and 4 show the problem-_domain_ and the problem-_instance_ (partial) input
files for the planner RP-MEP resulted by calling the parser on the Coin in the
Box instance described in Listings 1 and 2. Listings 5, on the other hand,
presents (part of) the encoding of the same problem for the planner
$m\mathcal{A}^{\rho}$. Let us remark that Listings 3 and 4 follow the syntax
of PDKB-PDDL while Listings 5 respects the syntax of $m\mathcal{A}^{\rho}$.

⬇

1(define (domain coininthebox)

2 (:agents a b c)

3 (:constants)

4 (:types)

5 (:predicates (opened) (has_key ?i - agent)

6 (looking ?i - agent) (tails))

7

8 (action: open

9 :parameters (?i - agent)

10 :derive (looking $agent$)

11 :precondition ([?i](has_key ?i))

12 :effects (and (opened))

13 )

14

15 (action: peek

16 :parameters (?i - agent)

17 :derive (never)

18 :precondition (and ([?i](opened))

19 ([?i](looking ?i)))

20 :effects (and [?i](tails)

21 (forall (?j - agent)

22 (when (looking ?j)

23 [?j][?i](or(tails)(!tails)))))

24 )

25

26 (action: announce

27 :parameters (?i - agent)

28 :derive (looking $agent$)

29 :precondition ([?i](tails))

30 :effects (and (tails))

31 )

32)

Listing 3: PDKB-PDDL Coin in the Box problem-_domain_ generated through the
parsing process of Listings 1.

In Lines 10 and 28 of Listings 3 we can see how, thanks to the PDKB-PDDL field
$\mathtt{:derive-condition}$ (shorten to $\mathtt{:derive}$), we are able to
define which agents are aware of an action’s execution and its effects. This
special field automatically expand the knowledge update for RP-MEP. This
conversion (that only allows belief formulae of depth up to 2 as indicated by
Line 4 of Listings 2) correctly captures the idea that fully observant agents
are aware of the actions’ effects and also know that the other fully
observants know these effects.

On the other hand, to express the complete knowledge update of the action
$\mathtt{peek}$ we need to account also for partial observability. In Lines
20-23 the effects of the action are written so that the acting agent, agent
$\mathsf{i}$, knows that the coin is tails up. The other agents, which are
partially observant, only knows that $\mathsf{i}$ knows the coin position but
they do not the position themselves. Given that the max depth of the formulae
is set to 2 these effects suffice in capturing the behavior of
$\mathtt{peek}$. Let us remark that the syntax presented in Lines 20-23 of
Listings 3 is not fully compatible with PDKB-PDDL but nicely captures the idea
we are trying to express. Partial observability, while supported by the
parser, is not yet fully supported during the conversion to PDKB-PDDL and is
currently under development.

⬇

1(define (problem pb1)

2 (:domain coininthebox)

3 (:depth 2)

4 (:projection )

5 (:task valid_generation)

6 (:init-type complete)

7

8 (:init

9 (tails)

10 (has_key a)

11 (looking a)

12

13 ;Length 1

14 (forall ?ag1 - agent

15 [?ag1](has_key a))

16

17 ;Length 2

18 (forall ?ag1 - agent

19 (forall ?ag2 - agent

20 [?ag2][?ag1](has_key a)))

21

22 )

23

24 (:goal

25 [a](tails)

26 )

27)

Listing 4: PDKB-PDDL Coin in the Box problem-_instance_ generated through the
parsing process of Listings 2.

While Listings 4 has some extra fields w.r.t. to Listings 2 that are used by
RP-MEP to set some internal parameters the only notable difference is the
conversion of the common knowledge operator, not supported by RP-MEP, into
chain of belief formulae. These chains, bounded by the depth limit (that is
our case is set to two), are the chains of knowledge that are used to define
the common knowledge operator. The conversion, if applied for example to Line
6 of Listings 2 “$\mathtt{[\mathsf{a\ b\ c}](has\\_key\ \mathsf{a})}$”,
generates all the belief formulae where:  every agent in
$\\{\mathsf{a};\mathsf{b};\mathsf{c}\\}$ knows $\mathtt{has\\_key\
\mathsf{a}}$ ($\ell=1$); and  every agent in
$\\{\mathsf{a};\mathsf{b};\mathsf{c}\\}$ knows that every agent in
$\\{\mathsf{a};\mathsf{b};\mathsf{c}\\}$ knows $\mathtt{has\\_key\
\mathsf{a}}$ ($\ell=2$).

⬇

1fluent has_key_a, has_key_b, .., tails;

2

3action open_a, open_b, .., announce_c;

4

5agent a, b, c;

6

7executable open_a if B(a,has_key_a);

8open_a causes opened;

9b observes open_a if look_b;

10c observes open_a if look_c;

11a observes open_a;

12

13executable peek_a if B(a,opened),B(a,look_a)

14peek_a determines tails if look_a;

15a observes peek_a;

16b aware_of peek_a if look_b;

17c aware_of peek_a if look_c;

18

19executable announce_a if B(a,tails);

20announce_a announces tails;

21b observes announce_a if look_b;

22c observes announce_a if look_c;

23a observes announce_a;

24

25initially tails, has_key_a, look_a;

26initially -look_b, -look_c, …;

27

28

29initially C([a,b,c],look_a);

30initially C([a,b,c],has_key_a);

31initially C([a,b,c],-opened);

32…

33initially C([a,b,c],-has_key_c);

34

35goal B(a,tails);

Listing 5: $m\mathcal{A}^{\rho}$ Coin in the Box problem generated through the
parsing process of Listings 1 and 2.

Finally, in Listings 5, we show a partial results of the conversion of E-PDDL
into $m\mathcal{A}^{\rho}$. Since $m\mathcal{A}^{\rho}$ does not allow to use
variables and types to define the problem specification the parser grounds the
instance of E-PDDL and use the result to generate the input for EFP. In
particular, this grounded instance contains grounded fluents,
$\mathtt{has\\_key\\_a}$, $\mathtt{has\\_key\\_b}$ and
$\mathtt{has\\_key\\_c}$, and grounded actions, $\mathtt{open\\_a}$. The
grounded actions are instantiated versions of the ones declared in E-PDDL
where each variable is associated with one of its possible values. Other small
syntactical changes are then applied, ontic actions are associated with
keyword $\mathtt{causes}$ and partial observability is identified by the
keyword $\mathtt{aware\\_of}$.

## Conclusion

In this paper, we proposed E-PDDL, an Epistemic Planning Domain Definition
Language, that represents a unified way to specify _Multi-agent Epistemic
Planning_ (MEP) problems. We show that E-PDDL can unify and support leading
MEP planners, and provide a parser code to the community that is able to
generate input specification for two state of the art epistemic reasoners.
Defining a unified language is the first step towards defining common
benchmarks and evaluation metrics for all the MEP community. Moreover, since
the new language follows the well-know language PDDL, E-PDDL may also serve as
a gateway for researchers already involved in the area of planing that want to
investigate the branch of epistemic reasoning. Finally defining a unified way
of specifying the input for different epistemic solvers can help in designing
a general purpose epistemic solver that is automatically able to select the
best solving strategy, between existing planners, starting from the problem
definition that can now be “understood” by every considered approach. We leave
the design of such architecture as future work.

While E-PDDL is able to capture most of the features that can be found in an
epistemic domain the language only considers three types of actions: ontic,
sensing and announcement. We plan to expand the language syntax so that is
able to accept custom action definitions, specified with a custom event model.
Nonetheless, before introducing such feature we must ensure compatibility with
the considered epistemic solvers. For RP-MEP the conversion to explicit
knowledge update is handled directly by the parser and, therefore, custom
actions definition would only generate different chains of belief formulae. On
the other hand, EFP relies on an epistemic transition function that expects
the actions to be ontic, sensing or announcement and it would not be able to
handle custom action types. That is why before expanding E-PDDL we need to
implement in EFP the possibility of using custom action definitions.

Finally we plan to refine the parser code to better integrate the concept of
partial observability and to be more flexible in the definition of the
formulae.

## References

  * [Baral et al. 2015] Baral, C.; Gelfond, G.; Pontelli, E.; and Son, T. C.  2015\.  An action language for multi-agent domains: Foundations.  CoRR abs/1511.01960.
  * [Bäckström 1995] Bäckström, C.  1995\.  Expressive equivalence of planning formalisms.  Artificial Intelligence 76(1):17–34.  Planning and Scheduling.
  * [Bolander 2017] Bolander, T.  2017\.  A gentle introduction to epistemic planning: The del approach.  arXiv preprint arXiv:1703.02192.
  * [Fabiano et al. 2019] Fabiano, F.; Riouak, I.; Dovier, A.; and Pontelli, E.  2019\.  Non-well-founded set based multi-agent epistemic action language.  In Proceedings of the 34th Italian Conference on Computational Logic, 242–259.
  * [Fabiano et al. 2020] Fabiano, F.; Burigana, A.; Dovier, A.; and Pontelli, E.  2020\.  EFP 2.0: A multi-agent epistemic solver with multiple e-state representations.  In Proceedings of the 30th International Conference on Automated Planning and Scheduling, 101–109.
  * [Fagin and Halpern 1994] Fagin, R., and Halpern, J. Y.  1994\.  Reasoning about knowledge and probability.  Journal of the ACM (JACM) 41(2):340–367.
  * [Fikes and Nilsson 1971] Fikes, R. E., and Nilsson, N. J.  1971\.  Strips: A new approach to the application of theorem proving to problem solving.  In Proceedings of the 2nd International Joint Conference on Artificial Intelligence, IJCAI’71, 608–620.  San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.
  * [Fox and Long 2003] Fox, M., and Long, D.  2003\.  Pddl2.1: An extension to pddl for expressing temporal planning domains.  Journal of Artificial Intelligence Research 20:61–124.
  * [Gerbrandy and Groeneveld 1997] Gerbrandy, J., and Groeneveld, W.  1997\.  Reasoning about information change.  Journal of Logic, Language and Information 6(2):147–169.
  * [Helmert 2006] Helmert, M.  2006\.  The fast downward planning system.  Journal of Artificial Intelligence Research 26:191–246.
  * [Helmert 2009] Helmert, M.  2009\.  Concise finite-domain representations for pddl planning tasks.  Artif. Intell. 173(5–6):503–535.
  * [Howey and Long 2003] Howey, R., and Long, D.  2003\.  Val’s progress: The automatic validation tool for pddl2.1 used in the international planning competition.  In ICAPS 2003 workshop on ”The Competition: Impact, Organization, Evaluation, Benchmarks”, Trento, Italy.
  * [Kripke 1963] Kripke, S. A.  1963\.  Semantical considerations on modal logic.  Acta Philosophica Fennica 16(1963):83–94.
  * [Le et al. 2018] Le, T.; Fabiano, F.; Son, T. C.; and Pontelli, E.  2018\.  EFP and PG-EFP: Epistemic forward search planners in multi-agent domains.  In Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, 161–170.  Delft, The Netherlands: AAAI Press.
  * [Lipovetzky and Geffner 2017] Lipovetzky, N., and Geffner, H.  2017\.  Best-first width search: Exploration and exploitation in classical planning.  In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 3590–3596.
  * [Magnaguagno et al. 2020] Magnaguagno, M.; Felipe, M.; Behery, M. A.; and Corfman, B.  2020\.  PDDL-parser.  https://github.com/pucrs-automated-planning/pddl-parser.
  * [McDermott et al. 1998] McDermott, D.; Ghallab, M.; Knoblock, C.; Wilkins, D.; Barrett, A.; Christianson, D.; Friedman, M.; Kwok, C.; Golden, K.; Penberthy, S.; Smith, D.; Sun, Y.; and Weld, D.  1998\.  PDDL - the planning domain definition language.  Technical report, Technical Report.
  * [Muise et al. 2015] Muise, C. J.; Belle, V.; Felli, P.; McIlraith, S. A.; Miller, T.; Pearce, A. R.; and Sonenberg, L.  2015\.  Planning over multi-agent epistemic states: A classical planning approach.  In Proc. of AAAI, 3327–3334.
  * [Pednault 1994] Pednault, E. P. D.  1994\.  ADL and the State-Transition Model of Action.  Journal of Logic and Computation 4(5):467–512.
  * [Queen’s Mu Lab 2020] Queen’s Mu Lab.  2020\.  PDKB-planning.  https://github.com/QuMuLab/pdkb-planning.
  * [Richter and Westphal 2010] Richter, S., and Westphal, M.  2010\.  The lama planner: Guiding cost-based anytime planning with landmarks.  Journal of Artificial Intelligence Research 39:127–177.
  * [Son et al. 2014] Son, T. C.; Pontelli, E.; Baral, C.; and Gelfond, G.  2014\.  Finitary s5-theories.  In European Workshop on Logics in Artificial Intelligence, 239–252.  Springer.
  * [Van Ditmarsch, van Der Hoek, and Kooi 2007] Van Ditmarsch, H.; van Der Hoek, W.; and Kooi, B.  2007\.  Dynamic epistemic logic, volume 337.  Springer Science & Business Media.
  * [Van Rossum and Drake 2009] Van Rossum, G., and Drake, F. L.  2009\.  Python 3 Reference Manual.  Scotts Valley, CA: CreateSpace.


∎

11institutetext: A. Ghani* 22institutetext: Department of Computer Science &
Software Engineering
International Islamic University Islamabad, Pakistan
Tel.: +92-51-9019725
22email<EMAIL_ADDRESS>33institutetext: H. Rahman 44institutetext:
University of Malakand, Pakistan 55institutetext: M. Merabti 66institutetext:
University of Sharjah, Sharjah, UAE 77institutetext: D. Llewellyn-Jones
88institutetext: University of Cambridge, United Kingdom 99institutetext: S.
Sudirman 1010institutetext: Liverpool John Moores University United Kingdom

# Structuring Communities for Sharing Human Digital Memories in a Social P2P
Network

Haseeb Ur Rahman  Madjid Merabti  David Llewellyn-Jones  Sud Sudirman  Anwar
Ghani

(Received: date / Accepted: date)

###### Abstract

A community is sub-network inside P2P networks that partition the network into
groups of similar peers to improve performance by reducing network traffic and
high search query success rate. Large communities are common in online social
networks than traditional file-sharing P2P networks because many people
capture huge amounts of data through their lives. This increases the number of
hosts bearing similar data in the network and hence increases the size of
communities. This article presents a Memory Thread-based Communities for our
Entity-based social P2P network that partition the network into groups of
peers sharing data belonging to an entity–person, place, object or interest,
having its own digital memory or be a part another memory. These connected
peers having further similarities by organizing the network using linear
orderings. A Memory-Thread is the collection of digital memories having a
common reference key and organized according to some form of correlation. The
simulation results show an increase in network performance for the proposed
scheme along with a decrease in network overhead and higher query success rate
compared to other similar schemes. The network maintains its performance even
while the network traffic and size increase.

###### Keywords:

Peer-to-Peer (P2P) NetworksMemory for Life SystemsOnline Social NetworksSocial
P2P NetworksCommunity-based P2P NetworksHuman Digital Memories

##  1 Introduction

Human mind stores information in an encoded form tpds01 ; tpds02 . This is a
biological event, and the encoding process is carried out through various
signals generated in the brain. The signals are generated as a result of human
perceptions and experiences of its surroundings, through their senses, in the
form of objects, places, people, events, emotions and so on. These stimuli
such as people, places, etc. are the cues to store and recall human memories.
The cues are also interconnected, such that one cue can lead to the storage or
recall of a different memory. For example, while people can generally
intentionally recall specific memories about friends, family, places, events,
and so on, seeing a related scene will often result in the (involuntary)
recollection of other memories h01 . An example might be the revisiting of a
location a second time reminding us of the friends with whom together we
visited the place before. The relationships between memories can, therefore,
be important for their recollection, and we use this fact to organize human
life digital memories in the form of Memory Threads. This leads on to the
organization of our digital memories into Memory-thread Based Communities
(MTC).

The decrease in the cost of personal devices such as mobile phones, digital
cameras and so on has allowed people to capture and store their life memories
in a digital form far more easily than ever before. Each digital memory is
collected by someone at a time, place or an event and involving different
people, objects and so on. We consider these real-world objects, interests,
places, and people and refer to them as Entities. An entity also represents a
co-relation between these digital memories. For example, a person would
represent a connection between all the digital memories in the form of
pictures, audio captures, videos, and so on, which are captured, collected or
stored by that person or for them throughout their life at different times,
places, events and so on. We believe that the correlations of these digital
memories can allow them to be organized in a meaningful way. Organized digital
memories help in presenting the purpose of the data for which the memories
were captured and recalling them in future in an intended way.

An entity can be considered to be anything which has its own digital memories
captured or stored by itself or can form part of the digital memories of
others. Entities present within a set of memories can be identified by various
tools such as a ‘Memory for Life’ (M4L) system tpds03 . An M4L system can
analyze and annotate data, and detect entities which exist as part of it. For
example, indoor or outdoor images, people, places, objects in an image and so
on might all be considered as entities. Information about entities is often
stored in the form of metadata which can further be used to organize the
original data.

In order to take advantage of the connections between digital memories, this
article proposes the use of memory threads to organize sets of digital
memories. A memory thread is formed for an entity that represents the events
or sequence of events that occurred for that entity. Digital memories in a
memory thread are selected according to a selection criterion, which is
usually the existence of the entity. They can then be organized according to
an indexing criterion. The digital memories in a memory thread are organized
in a way that expresses information about the entity. Multiple indexing
criteria can be used to organize the digital memories into a multi-dimensional
space such that applying a single or combination of criteria can retrieve the
required digital memory or memories. For example, the time or period within a
person’s life that memory was captured might constitute a criterion for
storing and recalling that person’s memories. In this example, the person, as
an entity, is the selection criterion and the age of the person constitutes
the indexing criterion. Almost every digital memory is stored with the time at
which the digital memories were captured. Therefore, we can organize digital
memories based on the history of the entity they relate to, which is likely to
be useful since history is one of the ways to express information about
objects, places and so on. If we organize digital memories according to the
history of an object, it naturally forms a linearly structured memory thread.

In our previous work tpds04 , different challenges has been identified for
sharing human digital memories such as network structure, data privacy,
searching, etc. tpds31 ; tpds32 ; tpds33  and have proposed an Entity-Based
Social Peer-to-Peer (P2P) Network (ESP2PN) tpds05  where the communities are
formed according to entities in digital memories h10 . This operates on the
analyzed and annotated digital memories captured by memory for life system. We
have assumed the digital memories of each person are stored on and shared
through their own peer or personal social network h09 . Considering the
importance of the underlying network structure can have a significant effect
on the performance of the network tpds25 ; tpds26 ; tpds27 ; tpds28 ; tpds29 ,
a Memory Thread-based Communities approach has been proposed to address this
issue. An MTC reflects memory threads in a similar way to the method we use to
structure peers in these memory thread-based Communities. An MTC is formed by
peers that share data for an entity such that each peer in it connects
according to the position defined, based on the digital memories it shares, by
the indexing criterion. Memory thread-based communities, therefore, bring
together similar peers together, with closeness also being related to the
ordering of the indexing criteria. For example, if a person is sharing the
digital memories of his school years good places for them to initially connect
to are the peers storing digital memories relating to the same School and
period, which are likely to be those belonging to classmates. We believe that
structuring the community according to certain criteria gives topological
awareness to a peer for routing search queries tpds26 ; tpds34 , which will
result in improving the efficiency of search. It also makes these communities
more scalable because a peer connects only to a few neighboring peers – those
that are most similar based on the criteria – as part of a larger community.
Moreover, the indexing criteria will give certain information to a user for
browsing the social P2P network.

The general contribution of the this article can be listed as follows:

  1. 1.

Human digital memories exists with certain patterns that allows them to be
organized meaningfully. The first contribution is to proposed a novel Memory-
thread based communities that are organized according to the patterns in the
digital memories.

  2. 2.

To present Memory Thread-based Communities for Entity-based social P2P network
that partition the network into groups of peers sharing data belonging to an
entity to handle the challenge of reducing the number of hosts bearing similar
data as well as reduce the size of the community. As a result large
communities are organized meaningfully according to a common reference key and
a correlation among them.

  3. 3.

To improve the network performance by decreasing the network overhead and
increasing the query success rate compared to other similar schemes.

  4. 4.

To maintain the network and its performance irrespective of the increase in
network traffic and size of the network.

  5. 5.

To maintain scalability of services irrespective of the networks size and
traffic

In the remainder of this paper, we will elaborate on these ideas further.
Section 2 describes existing work and the arguments as to why existing
architectures are not suitable in our case. Section 3 explains the idea of
memory threads, its types and how they can be used to organize digital
memories. Section 4 explains how the communities are formed according to
memory threads. Here we explain how various types of memory thread can be
reflected in the structure of the network and the joining of a peer to a
memory thread-based community. We provide details of our simulated memory
thread-based community system and compare it with some of the existing file
sharing P2P networks aimed at tackling similar digital memory storage issues.
The results are explained in Section 5. The article has been concluded in
Section 6 with a look at future work.

##  2 Related Work

Methods for organizing digital memories using computing devices have been
considered since the birth of the computer, starting with Vannevar Bush in
1945 tpds06  in his famous article “As We, May Think” in the form of a machine
called the Memex. According to Bush, “A memex is a device in which individual
stores all his books, records, and communications, and which is mechanized so
that it may be consulted with exceeding speed and flexibility. It is an
enlarged intimate supplement to his memory”. At the push of a button, all the
data of a person should be retrieved by the machine in a short time . Gorden
Bell’s MyLifeBits tpds07  aimed to provide a realization of the Memex
utilizing the tools, increased processing capabilities and relatively-speaking
large digital storage capacities that have become available more recently. The
software of MyLifeBits has the ability to store images, links, text, videos,
etc. in a database and allows manual annotation of the material. The area has
subsequently been further extended to collecting digital memories and various
tools and techniques have been developed for this e.g. Eyetape. Jim Gemmell et
al. tpds08  describe the four principles that were applied when designing
MyLifeBits. First, “strict hierarchy should not be imposed on data
organization”. Second, “many visualizations of their life bits were desirable
to help understand what they would be looking at”. Third, “the value of non-
text media is dependent on annotations”. Fourth, “authoring tools create two-
way links to media that they included with new media”. Several other areas
were identified and a single platform was required to develop tools and
techniques for collecting, storing, organizing, sharing and generating
meaningful information from digital memories. In this effort, developing an
M4L system was accepted as a third grand challenge (GC3) by the Engineering
and Physical Science Council (EPSRC) tpds09  in the UK in the year 2008 tpds10
. Azizan et al. tpds11  are currently working on a prototype of a Human Life
Memory system for collecting, storing and organizing different life events,
and for identifying interesting events referred to as “Serendipitous Moments”,
as well as discussing sharing via P2P networks. In our previous work, we
described the challenges for sharing human life digital memories tpds04  and
proposed an Entity-based social P2P network tpds05  based on the challenges
for sharing memories. To share digital memories, it is important to properly
organize the network so that data of the entities is not lost. The following
are a few approaches which use the data contents to organize and search peers
and data in the network.

Unstructured P2P networks h02 ; tpds12 ; tpds31 ; tpds32 ; tpds33 ; tpds34 ,
also called pure P2P networks, connect peers in a ’random’ manner. Each peer
has equal responsibility for routing messages and providing services. Since
there is no central system that controls and manages the network, it is the
responsibility of each peer to keep a record of its neighbor peers and
resources. Random walk h08  and Flooding are the most commonly used searching
techniques in unstructured networks tpds13 ; tpds32 ; tpds34 . Unstructured
networks are less scalable, produce high network overhead and have lower
search precision (due to queries being directed to irrelevant peers) compared
to their structured counterparts tpds14 ; tpds15 ; h11 ; h12 . Search
precision also depends upon the number of hops a query travels. If the number
of hops a query travels is higher, then the successful query rate increases
while at the same time generating more network overhead and vice versa.

Upadrashta et al. tpds16  utilize the in-network experience of a peer. Peers
analyze queries and find the interest of a peer from the search queries that
are received from other peers. In this way, every peer keeps (stores)
information about other peers, leading to the formation of virtual
communities. Upon the arrival of a search query, it has been analyzed and then
forwarded to peers with similar interests reflected in the search query. An
inexperienced peer has less knowledge, making it harder for it to find content
stored by others, which can be a problem for newly joined peers. In Semantic
Overlay Networks (SON) tpds17 , peers that are semantically similar are
grouped into a single cluster. Maze tpds18  is a centralized online social P2P
network, which allows people to share their resources, friends list and
status. The server is responsible for connecting peers and issuing tickets to
peers for security. However, the network cannot operate without the server due
to the crucial role it plays in providing connectivity and security. In a
similar approach proposed by Modarresi et al. tpds19 , a group of peers with
similar interests are gathered in a community. Data lookup in Interest-Based
Communities (IBC) is performed by sending queries only to members with similar
interests. Community-based approaches group similar peers together which allow
peers that do not have the required data to be avoided during the search. Such
a community certainly brings similar peers together but does not provide any
information about the status, characteristics or ‘personality’ of entities.
Within these communities, there is no further structure imposed, and peers
will connect with other peers without consideration for any other similarity
criteria. The exact location of data is therefore not known in advance. When a
peer searches for some particular item of data, it sends queries to all
members – or up to a certain number of hops – within a community. However,
sending queries to all peers creates overhead since peers that have no
relevant data will also receive these queries. Lowering the number of hops
inside the community reduces the overhead, but decreases the chance of finding
the required data.

In IBCs, data is shared according to the interest of the host. If the interest
of the host changes then there is the possibility that their associated peer
will leave the community and the data being shared by the peer will not be
accessible anymore. Contrary to IBCs, we consider the actual data being shared
by the host for creating communities and connecting peers inside each
community; because as long as the data is available for sharing, it will be
accessible in the same community. We also believe that our memory thread-based
communities will be more stable due to the entities in our Entity-based social
P2P network.

##  3 Memory Threads

Various hardware and software tools, such as Memory for Life systems tpds20 ,
are able to analyse and meaningfully define memories in a digital form. Some
systems where automatic analysis by a tool is difficult, also allow manual
annotations to be made. MyLifeBits provides a good example of this case tpds08
. We refer to the tagged information stored in the form of metadata (either by
hardware, software or manually) with a digital memory as a memory key. As
described above, people remember their memories based on some reference, such
as person, place, event etc. which we call entities, which is then used for
recollection. The memory key(s), in the form of entities in data, contain such
reference(s) to a digital memory that can be used to recall it is called a
reference key. A single or combination of such memory keys forms a reference
key. A digital memory must have at least one reference key. A reference key
for a piece of data can either be set by the owner or user of the data
explicitly, or obtained from a data analysis and annotation tool such as an
M4L system.

We will explore this idea more comprehensively using an illustrative example
(adapted from a real scenario) based on the picture of the Eiffel Tower shown
in Fig. 1 tpds21 . This picture was captured by Jim and Emmy Humberd in March
1989 using a digital camera in cloudy weather during the when it was
refurbished for its 100th anniversary. In this example the type of data
(picture), date (March 1989), device (camera), name of entity (Eiffel Tower),
weather (cloudy), photographer (Emmy Humberd) and event (2nd year of 100th
anniversary) are all memory keys. Reference keys to the memory in Fig. 1, in
the form of the names of the entities involved, can be set as “Eiffel Tower”
and the photographers. The digital memory not only belongs to the Eiffel Tower
but also forms part of the digital memories of the photographers.

Similar digital memories have a common reference key and can be recalled using
the same reference. Digital memories of similar references can be put together
and are organized according to certain criteria to form a memory thread. In
other words, a memory thread is the collection of memories which has a common
reference key and is organized by a criterion which structures them in a
specific order. The order of the digital memories in a memory thread should be
established so that they can be traced by moving from one memory item to
another. A memory thread should also be in a form that provides information
about the entity for which the memory thread has been formed. For example,
time, which is further considered as history of an entity to form memory
thread, is often used as a reference to digital memories since it allows their
memories to be recollected based on when an event took place.

Figure 1: A digital memory and its associated memory keys.

###  3.1 Selection & Indexing Criteria

To form a memory thread, certain criteria are used to select the relevant
digital memories that it will be made up of. As we discusses above, there are
two types of criteria used to form a thread: selection criteria and indexing
criteria. The selection criteria select those digital memories that have a
similar reference key as used by people to recall their memories. The indexing
criterion organizes the digital memories into a given order. It’s, therefore
important that every digital memory should have at least one memory key which
can be used as an indexing criterion. For example, to form a memory thread for
the Eiffel Tower, the selection criterion would be the name of the entity
itself (i.e. the Eiffel Tower). However, as a selection criterion this will be
invariant across all of the memories, and therefore wouldn’t generally be
appropriate as an indexing criterion as well (although there are certain
situations where this is not the case, such as where the selection criterion
takes the form of a continuous range of values). A separate indexing criterion
is therefore needed, examples of which could be time, temperature, or any
other total ordering. If time is the indexing criteria for the Eiffel Tower
thread, then the thread will be formed as the digital memories of the
structure at different times, for example relative to its construction in
1889. A memory thread of the Eiffel Tower is illustrated in Fig. 2, where each
point represents a digital memory along with the time a digital memory is
captured. In this example, the memory thread gives us information about the
history of the entity. Yet there is no single memory key that allows
organizing all types of digital memories under a single criterion, which is
why it is not possible to present a specific structure for memory threads: the
structure will change according to the indexing criterion that organizes the
data. For example, as considered in the above example time can be a memory key
for organizing digital memories of the Eiffel Tower. If digital memories for
the Eiffel Tower are organized according to time then it will form a linearly
structured memory thread, but the structure of the memory thread would be
different if we were to choose location as an indexing criterion.

Figure 2: A virtual memory thread based on entity (selection criterion) and
time (indexing criterion)

A memory thread is formed for every entity, which has its own digital memories
or is a part of the memories of another entity. A memory thread stretches over
many digital memories that relate to a single entity. At a certain place in a
memory thread, where the digital memories of different entities have a common
reference key, different threads will overlap with one another. We call the
overlapping points of different threads networking points, shown in Fig. 3 as
circled areas. A memory thread can have a single or many overlapping points.
For example, many people, store the digital memories of their visit to the
Eiffel Tower as a part of their memory threads. Each of them has their own
memory threads, but at the Eiffel Tower their memory threads overlap with each
other which become a networking point for them. The networking points connect
different memory threads and form a network of memory threads. The networking
points allow access to the memory threads of other entities. In our social
life, we also have networking points. For example, a conversation becomes
friendlier when two people have visited the same place or they belong to the
same profession.

Figure 3: A network of extant memory threads

###  3.2 Extant and Virtual Memory threads

As defined above, some entities – such as humans – are capable of capturing,
storing and maintaining their memory threads using a device such as a
computer, mobile phone etc. Such a memory thread would be called an Extant
Memory Thread (EMT). The memory thread of an entity whose memories are part of
the extant memory threads of other entities, but where the entity cannot
itself capture, store or maintain memories, is called a Virtual Memory Thread
(VMT). A virtual memory thread is formed at the networking points of the EMTs
as shown in Fig. 3, because these will be the memories which belong to/involve
those entities which either do not own or cannot store, capture or maintain
their memories. This can be counter-intuitive, since we wouldn’t normally
refer to memories of entities that are not capable of having memories.
However, in our case it’s convenient to project memories onto inanimate
objects for the purposes of generalization and improving the effectiveness of
the network. Each entity can then find the memories of other entities by
following its extant memory threads to a networking point that can lead to the
virtual memory threads of the entities it is interested in. Fig. 4 illustrates
a selection of EMTs connected by VMTs.

Figure 4: A network of EMTs (solid lines) connected by VMTs (dashed lines)

##  4 The Proposed: Memory Thread-Based P2P Communities

A detailed discussions on Memory Thread-based P2P community, How EMT and VMT
based communities are formed in MTCs, structure of an MTCs and how peer join
the communities are given further below.

###  4.1 Memory Thread-based P2P Communities

The network structure of our Memory Thread-based P2P Communities for Entity-
based social Peer-to-Peer (P2P) networks tpds05  is based on the idea of
memory threads described in the previous section. In our approach, we maintain
memory threads for each entity across the network. A memory thread is
reflected in the network structure in order to organize the peers in the form
of a Memory Thread-based Community (MTC). A peer in an MTC represents a
digital memory in a memory thread formed in the network. Since, a peer can
store many digital memories either for a single or many entities, which allows
it to become a member of one or more than one MTCs. Similar to memory threads,
a selection criterion, which is an entity, is used to form an MTC and an
indexing criterion defines a structure or an order for the community. In our
network, a reference key for a digital memory can be set in a number of ways.
It can be set by the owner of the data explicitly, set automatically by an M4L
system, or obtained by aggregating search queries received for a single or a
group of memory keys. As described earlier, an entity can have an extant
memory thread or a virtual memory thread; these are also used to organize
peers in our network. An extant memory thread is maintained on a single peer
and a virtual memory thread across the network. In other words, a virtual
memory thread spans many extant memory threads stored at different peers,
which allows to connect peers in network in the form of MTCs.

###  4.2 Types of Communities

Communities has been classified into two categories and briefly explained in
the following sub section.

####  4.2.1 Extant Memory Threads based Communities

A community of peers of Extant Memory Thread (EMT) is formed by or for an
entity from its digital memories. As people prefer to be the sole owner of
their own data, therefore, an EMT is stored on a single peer or in the
personal social P2P network of an entity because data in an EMT contains only
a user’s own captured digital memories. To create an extant memory thread, an
entity specifies selection and indexing criteria and simply binds their
existing digital memories to the thread (or adds them to the thread when a new
digital memory is captured) on his own peer or personal social P2P network.
Note that entities can have a single or more extant memory threads and that a
digital memory can be part more than one extant memory thread at a time (but
must be part of at least one). Other peers in the network join an EMT either
by invitation or as members in a virtual memory thread. An EMT is simply a
memory thread stored on a single peer to which other peers in the network are
attached.

####  4.2.2 Virtual Memory Threads based communities

Creating a P2P community of Virtual Memory Thread (VMT) is less straight
forward, due to its decentralized nature. As we discussed above, there are
entities that cannot capture, store or maintain their own digital memories and
their ‘memories’ therefore all – by necessity – form part of the digital
memories of other entities. Also, for entities which can capture or store
their memories there are nonetheless some digital memories that relate to them
but are not owned by them and cannot therefore become a part of their EMTs.
Such digital memories will be part of EMTs of other entities and could
possibly be stored at more than one peer. A VMT connects those peers in a
community that store data belonging to a single entity. Memory thread-based
communities are actually formed using VMTs. The following paragraphs describe
the process of forming and joining a VMT in the network.

To form a virtual memory thread, a peer broadcasts a request for the digital
memories of an entity. The request contains the selection criterion for the
memory thread. Those peers that have data matching the criteria of the thread
reply with a notification highlighting the availability of such data. The
reply message contains information about the stored data in their EMT which
can become a part of the VMT. The sender receives the replies from all the
peers and starts a new thread-based community by making a list of those peers
which claim to have relevant data. A suitable indexing criterion is then
applied to these digital memories to structure the list of peers. The list
contains the addresses of the peers structured according to the indexing
criteria. The list is sent to all peers that replied with relevant data and
the peers become a part of the newly formed VMT.

###  4.3 Joining Memory Thread-Based Community

A memory thread-based community is formed by connecting those peers which have
common reference keys for similar digital memories. Peers in the MTC are
arranged according to the indexing criterion in a specific order as described
above, and this ordering also defines the structure of the community. New
peers can join an existing community, as soon as they are discovered or new
digital memories are added by entities in the network.

If a peer wants to join a memory thread, it follows the indexing criteria to
find its place in the thread. A peer finds the first peer by broadcasting in
the network as described earlier; once found it connects with it. Each peer in
the thread retains information about its neighbor peers either side in this
thread. A new peer can therefore find its location in the thread by
sequentially sending messages to each peer along the thread. When a peer finds
its suitable location in the thread, it then stores its two or three hop
neighbors on both sides in the thread. The purpose of connecting with two or
three hop neighbours instead of one is to avoid partitioning occurring in the
event that a peer leaves the network unexpectedly. In this case the next hop
neighbour will be connected which will avoid the thread becoming split. There
will be no dedicated peer responsible for maintaining a memory thread; if any
peer – whether the peer that started the thread or one that joined later –
leaves a thread, it will not disconnect the thread since each peer has equal
responsibilities in maintaining the thread.

###  4.4 The Structure of Memory Thread-Based Communities

The purpose of memory thread-based communities is to organize the network
properly. For this purpose, a characteristic of an entity, stored in the form
of metadata, can be used to form a memory thread in order to organize the
community for an entity. To structure our network for achieving good network
performance, we consider the use of the history of an entity to organize its
digital memories within the network. One important reason for choosing this as
an indexing criterion is that the time at which a digital memory is captured
is usually stored with the memory, and is therefore widely available. For this
indexing criterion the peers in our network will be organized linearly such
that each peer stores the address of its immediate one and two hop neighbors,
as shown in Fig. 5.

Figure 5: Memory thread-based community with 2-hop connection.

In our network, two important scenarios have been considered that have an
effect on the average path length and robustness of the network. First, a
single peer may store files that result in its appearing multiple times and at
different places in a single memory thread. These types of peers can provide
shortcuts while routing through the network. In the second scenario, multiple
peers store duplicate files. The indexing criteria place all of these multiple
files into a single location within the memory thread. So if any peer fails or
leaves the network then another peer storing the same (or a very similar) file
will remain available, thereby increasing the robustness of the network.

Figure 6: Memory thread-based community peers having multiple files.

Fig. 6 shows how peers can store many digital memories about an entity and
appear multiple times in a memory thread; peers drawn with the same colour
represent different files on the same physical device. Each peer keeps a
sorted list of neighbours according to the indexing criterion. Whenever a
query is received at one of these peers, it can be forwarded according to the
list in order to avoid the extra peers that would otherwise lie in the memory
thread between the two pieces of data stored on the same node.

Fig. 7 shows peers that have duplicate files, represented by the colour of the
peer. When a peer joins an MTC, it finds its location in the thread and
attaches to it. Those peers which have duplicate files will have the same
locations in the thread. When there is more than one such peer they form a
sub-community and select one peer as a representative for the sub-community.
The representative takes part actively in the thread. The other peers in the
sub-community are connected to the representative as well as to the peers on
the both sides of the representative, so that if the representative leaves the
network another peer can take its place. The non-representative peers do not
take an active role in the thread until they become the representative.

Figure 7: Memory thread-based community with duplicate digital memories.

The following figures, Fig. 8 and Fig. 9, show a snapshot of our MTCs, for the
simulated network that we will discuss in Section 5, generated by Pajek [22].
Fig. 8 shows all the peers in a circular form. The edges in the diagram
indicate shorts paths running across the circle of peers. Fig. 9 is the
network diagram of the peers in Fig. 8, without imposing any circular
arrangement.

Figure 8: Memory thread-based community showing short paths Figure 9: Network
of peers of the Memory thread-based community

##  5 Simulation Results

In this section we describe our simulated MTC network and compare it to
existing methods. In particular we compare it in terms of performance to
interest-based communities (IBC) and unstructured networks. The simulator has
been adapted from that of Modarresi et al. tpds23  and is used for simulating
social networks and semantic social networks.

###  5.1 Simulation setup

The simulation environment was set according to the static input parameters so
that the network structure follows a power law distribution. This is to
reflect the behaviour expected of an online social network tpds24 . The total
number of interest-based communities in the simulation was set to seven and
sub-communities are linearly distributed in each community. Each peer is a
member of three communities at a time and files are distributed linearly
throughout the network. Each peer has an upper limit set for the number of
connections it can support, determined by a neighbour distribution function
that obeys a power law distribution with scale value greater than two. Network
connections are bi-directional and the simulation time is 5000 simulation
seconds. Peers in the unstructured network are connected randomly by selecting
a peer and connecting it with a random number of peers until it reaches its
upper limit of connections. The files are also distributed randomly. The graph
density is calculated according to the formula $(2\times E)/(V\times(V-1))$
where E is total number of edges and V is total number of vertices. For each
of the above networks this is shown in Fig. 10.

Figure 10: Graph density of the networks

Flooding has been used as the search technique for all of the networks and the
maximum number of hops a query can travels is capped at three. The total
number of connections in each network is approximately the same, as given by
the graph density in Fig. 10. All results are given as the average value over
fifteen experimental runs. The outputs measured are the rate of successful
queries, the resulting network overhead and the number of hops a query travels
if successful.

To measure the output, the input conditions varied to test the performance of
the network are the following.

  1. 1.

Query distribution: Queries in the network are created according to a linear
distribution function. The distribution function which is used to distribute
the events, and to send new queries in the network within the 5000s time limit
is:

$T_{n+1}=T_{n}+(b\pm m)$ (1)

where Tn is the time of the last event, Tn+1 the time of the next event to be
set, b is a base value for the average delay and m is a modifier. The base b
for the function takes the values 200s, 100s, 60s, 40s, 30s, 25s, 20s and 15s
and the modifier m takes the value 40s. The base value represents the time
interval between sending new queries in the network. The modifier value is
used by the distribution function to vary the interval. This affects the
amount of traffic in the network: the lower the base value, the greater the
network traffic and vice versa. By changing network traffic, we test the
successful queries in the network and the amount of overhead created. For
these runs the network size is set at a constant 5000 peers.

  2. 2.

Number of peers: The number of peers in the network has also been varied to
test the performance of the network with different node densities. The traffic
in the network is generated according to the linear distribution
$T_{n+1}=Tn+(b\pm m)$ as before, but this time with a constant base value b of
100 and constant modifier m of 40 throughout all experiments. The successful
queries in the network and the level of overhead created were recorded while
increasing the network size, which ranges from 2000 to 20000 peers.

###  5.2 Results and comparison

The figures given below demonstrate the results obtained from our simulation.
Fig. 11 and Fig. 12 show the rate of the successful queries sent in the
network in the context of increasing network traffic and size.

Figure 11: Percentage successful queries as a result of increasing network
size Figure 12: Successful queries as a result of increase in network traffic

The unstructured network returns approximately 75% successful queries out of
the total queries sent in the network in both cases (i.e. for increasing
network size and increasing network traffic). The success rate for IBCs is
approximately 90% of total queries sent in the network which is 20% higher
than for the unstructured network. The MTCs have approximately 95% successful
queries out of the total queries sent in the network, which represents a
26.67% increase compared to the unstructured network and a 5.6% increase
compared to the IBCs. In order to better understand the effect on the network
performance as a result of changes in size and network traffic, we calculated
the Standard Deviation (SD) values for the rate of successful queries.
Standard deviation indicates the variation of values from the mean value. The
higher the value obtained from the SD, the higher the chances that a network
is more affected by the size of and traffic in the network, which may make the
network unstable during adverse conditions. The percentage values obtained
were 1.086103055, 0.611178069 and 0.368911439 as a result of increasing the
network size and 0.57384652, 0.50756941 and 0.1610037 as a result of
increasing network traffic for the unstructured network, IBCs and MTCs
respectively. The values for MTCs are lower than those for IBCs and
unstructured networks in both cases which suggest it’s likely to be more
stable and can maintain the network performance longer than for the other two
network structures. It’s widely known that unstructured networks are not
scalable and have poor performance as described above in Section 2, and the
results obtained here corroborate this. Unstructured networks have difficulty
handling increasing amounts of traffic, resulting in a higher SD value and
noticeable deviation in the graphs in Fig. 11 and Fig. 12. Performance starts
to drop after a total of 1000 queries have been sent, as can clearly be seen
in Fig. 12. The situation is similar for Fig. 12. The IBCs and MTCs
successfully maintain their performance, but due to the instability of IBCs –
as can be seen from the calculated SD values – we expect that performance will
in general drop sooner than for MTCs. Also, based on the current results, we
expect that the MTCs will maintain their performance for longer due to the
higher query success rate and more stable underlying network structure.

Interest-based communities reduce the network overhead as compared to
unstructured networks, while the MTC structure reduces it further. The graphs
in Fig. 13 and Fig. 14 show the overhead produced for each of these network
structures. The network overhead is measured as the number of dropped messages
during the experiment. A message is dropped when the Time-to-Live (TTL) of the
message expires, a repetitive message is received or the peer that poses the
query receives a drop message in response. The results show a considerable
reduction in the number of dropped messages in the case of our MTCs as
compared to IBCs and unstructured network. The MTC produces approximately
seven and twelve times less network overhead than IBCs and

Figure 13: Network overhead produced by increase in network size Figure 14:
Network overhead produced by increase in network traffic

##  6 Conclusion and Future Work

In this paper we presented the idea of memory threads to properly organize
human digital memories and discussed how they can support social P2P networks.
Memory threads are reflected in our Entity-based social P2P network as the
underlying network structure in the form of Memory Thread-based Communities.
The purpose of MTCs is to connect peers meaningfully. The data shared by a
peer, which belongs to an entity, is used to connect it to other similar peers
that are sharing data of the same entity. The connectivity inside an MTC is
carried out according to an indexing criterion. This indexing criterion is a
memory key, representing tagged information in the form of metadata produced
as a result of data annotation. This allows the digital memories to be
organised in a very effective way, as shown by our simulation results. The
indexing criterion is reflected similarly in the MTC which organizes the peers
according to the digital memories being shared. The resulting network improves
performance, resulting in a higher rate of successful queries and lower
network overhead as compared to existing network structures (unstructured
networks and Interest-based communities).

The idea of Memory threads and MTCs is based on the idea that “Let the data
speaks for itself rather than represented by a peer or person”, which where
lays the novelty of our work. Considering the importance of every digital
memory and the details inside a digital memory of people, the idea of Entities
in digital memories will consider every bit of a digital memory important and
will be accessible in network through the MTCs. When further research is
carried out and efficient ways are discovered to organize data, so our social
P2P network will accommodate them and based on the results shown above
improved performance of network is expected because network will be organized
by the way people search for data.

We are currently building on this work by implementing sub-communities within
the MTCs, which will be formed according to the indexing criteria of a memory
thread to create a more robust network. As the above simulation is based on a
static network, in the future we will also explore performance for MTCs
implemented in dynamic scenarios, with peers frequently leaving and joining
the network (’churn’). We are also implementing a search technique which
operates on top of the MTCs, to determine the flexibility of the system with
more complex search criteria. This may require the development of different
structures for memory threads (not just linear) that can exist due to the
different characteristics that appear in real world scenarios for various
indexing values. The structure of a memory thread and the communities of peers
which are formed according to the memory thread, depend upon the indexing
criteria of the memory thread. The indexing criteria have a crucial effect on
this structure. For example, while the history of an entity forms a linearly
structured memory thread, the location at which data is captured might form a
structure other than a linear structure.

## References

  * (1) E.P.S.R.C (2009).  URL http://www.epsrc.ac.uk/Pages/default.aspx
  * (2) Abbas, S.M.A.: Design and analysis of social network systems (sns).  Ph.D. thesis, Manchester Metropolitan University, UK (2016)
  * (3) Ahmed, R., Boutaba, R.: A survey of distributed search techniques in large scale distributed systems.  IEEE Communications Surveys & Tutorials 13(2), 150–167 (2011)
  * (4) Brown, P.J.: GC3: memory for life: getting things back.  In: Grand Challenges in Computing Research conference (2004)
  * (5) Bush, V.: As we may think.  online (1945).  URL https://www.theatlantic.com/magazine/archive/1945/07/as-we-may-think/303881/
  * (6) Cao, X.: Semantic search and composition in unstructured peer-to-peer networks (2015).  DOI http://dx.doi.org/10.22028/D291-25422
  * (7) Crespo, A., Garcia-Molina, H.: Semantic overlay networks for p2p systems.  In: International Workshop on Agents and P2P Computing, pp. 1–13. Springer (2004)
  * (8) Ed-daoui, I., El Hami, A., Itmi, M., Hmina, N., Mazri, T.: Unstructured peer-to-peer systems: towards swift routing.  International Journal of Engineering & Technology 7(2.3), 33–36 (2018)
  * (9) Ferrara, E.: Mining and analyzing online social networks.  Ph.D. thesis (2012)
  * (10) Fitzgibbon, A., Reiter, E.: Memories for life: Managing information over a human lifetime.  UK Computing Research Committee Grand Challenge proposal 22, 13–16 (2003)
  * (11) Franchi, E., Poggi, A., Tomaiuolo, M.: Blogracy: A peer-to-peer social network.  In: Censorship, Surveillance, and Privacy: Concepts, Methodologies, Tools, and Applications, pp. 675–696. IGI Global (2019)
  * (12) Furno, A., Zimeo, E.: Self-scaling cooperative discovery of service compositions in unstructured p2p networks.  Journal of Parallel and Distributed Computing 74(10), 2994 – 3025 (2014).  DOI https://doi.org/10.1016/j.jpdc.2014.06.006.  URL http://www.sciencedirect.com/science/article/pii/S0743731514001087
  * (13) Gemmell, J., Bell, G., Lueder, R.: Mylifebits: a personal database for everything.  Communications of the ACM (CACM) 49 (2006)
  * (14) Gemmell, J., Bell, G., Lueder, R., Drucker, S., Wong, C.: Mylifebits: fulfilling the memex vision.  In: Proceedings of the tenth ACM international conference on Multimedia, pp. 235–238. ACM (2002)
  * (15) Gong, W., Jin, R., Yang, L., Huang, D.: Enhanced entropy-based resource searching in unstructured p2p networks.  Chinese Journal of Electronics 24, 229–235(6) (2015).  URL https://digital-library.theiet.org/content/journals/10.1049/cje.2015.04.002
  * (16) Hayes, N.: Foundations of psychology.  Cengage Learning EMEA (2000)
  * (17) Hsiao, H.C., Su, H.W.: On optimizing overlay topologies for search in unstructured peer-to-peer networks.  IEEE Transactions on Parallel and Distributed Systems 23(5), 924–935 (2012)
  * (18) Hua, C., Mao, Y., Jinqiang, H., Haiqing, D., Xiaoming, L.: Maze: a social peer-to-peer network.  In: IEEE International Conference on E-Commerce Technology for Dynamic E-Business, pp. 290–293. IEEE (2004)
  * (19) Humberd, J., Humberd, E.: Invitation to France: a ”why-not-travel” rather than a ”how-to-travel” essay.  Em J Pub (2001)
  * (20) Ismail, A., Merabti, M., Llewellyn-Jones, D., Sudirman, S.: A framework for sharing and storing serendipity moments in human life memory.  In: First IEEE International Conference on Ubi-Media Computing, pp. 132–137. IEEE (2008)
  * (21) Ismail, A., Merabti, M., Llewellyn-Jones, D., Sudirman, S.: Identifying personal memories and shared experience using p2p networks.  In: The 10th Annual Conference on the Convergence of Telecommunications, Networking & Broadcasting (PGNet 2009). Citeseer, Liverpool, UK (2009)
  * (22) Liu, J., Wang, G., Li, D., Liu, H.: Esr: An efficient, scalable and robust overlay for autonomic communications.  In: G. Wang, A. Zomaya, G. Martinez, K. Li (eds.) Algorithms and Architectures for Parallel Processing, pp. 415–429. Springer International Publishing, Cham (2015)
  * (23) Meng, X., Jin, J.: A free rider aware topological construction strategy for search in unstructured p2p networks.  Peer-to-Peer Networking and Applications 9(1), 127–141 (2016).  DOI 10.1007/s12083-014-0318-7.  URL https://doi.org/10.1007/s12083-014-0318-7
  * (24) Meng, X., Liu, D.: A traffic-efficient message forwarding approach in unstructured p2p networks.  Peer-to-Peer Networking and Applications 9(2), 255–265 (2016).  DOI 10.1007/s12083-015-0326-2.  URL https://doi.org/10.1007/s12083-015-0326-2
  * (25) Modarresi, A., Mamat, A., Ibrahim, H., Mustapha, N.: A community-based peer-to-peer model based on social networks.  International Journal of Computer Science and Network Security 8(4), 272–277 (2008)
  * (26) Modarresi, A., Mamat, A., Ibrahim, H., Mustapha, N.: Modeling and simulating semantic social overlay peer-to-peer systems.  Journal of Applied Sciences 9(19), 3547–3554 (2009)
  * (27) Mohs, R.C.: How human memory works (2007).  URL https://science.howstuffworks.com/life/inside-the-mind/human-brain/human-memory.htm
  * (28) Naghizadeh, A., Berenjian, S., Meamari, E., Atani, R.E.: Structural-based tunneling: preserving mutual anonymity for circular p2p networks.  International Journal of Communication Systems 29(3), 602–619 (2016)
  * (29) Naghizadeh, A., Berenjian, S., Razeghi, B., Shahanggar, S., Pour, N.R.: Preserving receiver’s anonymity for circular structured p2p networks.  In: 2015 12th Annual IEEE Consumer Communications and Networking Conference (CCNC), pp. 71–76. IEEE (2015)
  * (30) Ogino, N., Kitahara, T.: An efficient content search method based on local link replacement in unstructured peer-to-peer networks.  IEICE Transactions on Communications advpub (2017).  DOI 10.1587/transcom.2017EBP3024
  * (31) Park, H., Yang, J., Park, J., Kang, S.G., Choi, J.K.: A survey on peer-to-peer overlay network schemes.  In: 2008 10th International Conference on Advanced Communication Technology, vol. 2, pp. 986–988. IEEE (2008)
  * (32) Priyanka, C., Deeba, K.: A comparative study on optimization of search in overlay networks.  INTERNATIONAL JOURNAL OF COMPUTER SCIENCE 1(4) (2013)
  * (33) Rahman, H.U., Merabti, M., Llewellyn-Jones, D., Sudirman, S.: Investigating sharing in memory for life systems.  In: The 11th Annual Conference on the Convergence of Telecommunications, Networking & Broadcasting (PGNet 2010). PG Net (2010)
  * (34) Rahman, H.U., Merabti, M., Llewellyn-Jones, D., Sudirman, S.: An entity-based social peer-to-peer network for digital life memories.  In: International Conference on Computer Networks and Information Technology, pp. 13–19. IEEE (2011)
  * (35) Shen, W.W., Sen, S., Shuang, K., Yang, F.C.: SKIP: an efficient search mechanism in unstructured P2P networks.  The Journal of China Universities of Posts and Telecommunications 17(5), 64–71 (2010)
  * (36) Stannat, A., Pouwelse, J.: A random walk based trust ranking in distributed systems.  arXiv preprint arXiv:1903.05900 (2019)
  * (37) Upadrashta, Y., Vassileva, J., Grassmann, W.: Social networks in peer-to-peer systems.  In: Proceedings of the 38th Annual Hawaii International Conference on System Sciences, pp. 200c–200c. IEEE (2005)
  * (38) Ur Rahman, H., Merabti, M., Llewellyn-Jones, D., Sudirman, S., Ghani, A.: A community-based social P2P network for sharing human life digital memories.  Transactions on Emerging Telecommunications Technologies n/a(n/a), e3866 (2020).  DOI 10.1002/ett.3866.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/ett.3866
  * (39) Venkadeshan, R., Jegatha, M.: Tmv: Trust-matrix-value based neighbor peer selection for secure query forwarding in p2p networks.  In: A. Deshpande, A. Unal, K. Passi, D. Singh, M. Nayak, B. Patel, S. Pathan (eds.) Smart Trends in Information Technology and Computer Communications, pp. 82–91. Springer Singapore, Singapore (2018)