Leila Amgoud
email: amgoud@irit.fr

Nabil Hameurlain
email: nabil.hameurlain@univ-pau.fr

An argumentation-based approach for dialog move selection

Modeling different types of dialog between autonomous agents is becoming an important research issue. Several proposals exist with a clear definition of the dialog protocol, which is the set of rules governing the high level behavior of the dialog. However, things seem different with the notion of strategy. There is no consensus on the definition of a strategy and on the parameters necessary for its definition. Consequently, there are no methodology and no formal models for strategies. This paper argues that a strategy is a decision problem that consists of: i) selecting the type of act to utter at a given step of a dialog, and ii) selecting the content that will accompany the act. The first kind of decision amounts to select among all the acts allowed by the protocol, the best option which according to some strategic beliefs of the agent will at least satisfy the most important strategic goals of the agent. The second kind of decision consists of selecting among different alternatives (eg. different offers), the best one that, according to some basic beliefs of the agent, will satisfy the functional goals of the agent. The paper proposes then a formal model based on argumentation for computing on the basis of the above kinds of mental states, the best move (act + content) to play at a given step of the dialog. The model is illustrated through an example of auctions.

Introduction

An increasing number of software applications are being conceived, designed, and implemented using the notion of autonomous agents. These applications vary from email filtering [START_REF] Maes | Agents that reduce work and information overload[END_REF], through electronic commerce [START_REF] Rodriguez | A java-based electronic auction house[END_REF][START_REF] Wellman | A market-oriented programming environment and its application to distributed multicommodity flow problems[END_REF], to large industrial applications [START_REF] Jennings | Using archon to develop real-word dai applications part 1[END_REF]. In all of these disparate cases, however, the agents are autonomous in the sense that they have the ability to decide for themselves which goals they should adopt and how these goals should be achieved [START_REF] Wooldridge | Intelligent agents: theory and practice[END_REF]. In most agent applications, the autonomous components need to interact with one another because of the inherent interdependencies which exist between them. They need to communicate in order to resolve differences of opinion and conflicts of interest that result from differences in preferences, work together to find solutions to dilemmas and to construct proofs that they cannot manage alone, or simply to inform each other of pertinent facts. Many of these communication requirements cannot be fulfilled by the exchange of single messages. Instead, the agents concerned need to be able to exchange a sequence of messages which all bear upon the same subject. In other words they need the ability to engage in dialogs. In [START_REF] Walton | Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning[END_REF] different categories of dialogs have been distinguished including persuasion and negotiation. Work in the literature has focused on defining formal models for these dialog types. Generally, a dialog system contains the following three components: the agents involved in the dialog (i.e their mental states), a dialog protocol and a set of strategies. The dialog protocol is the set of rules of encounter governing the high-level behavior of interacting agents. A protocol defines among other things:

the set of permissible acts (eg. asking questions, making offers, presenting arguments, etc.); the legal replies for each act.

A dialog protocol identifies the different possible replies after a given act. However, the exact act to utter at a given step of the dialog is a strategy matter. While the protocol is a public notion, strategy is crucially an individualistic matter. A strategy can be seen as a two steps decision process:

1. among all the possible replies allowed by the protocol, to choose the move to play.

For instance, in a negotiation dialog, the protocol may allow after an offer act the following moves: accepting/rejecting the offer or making a new offer. 2. to choose the content of the move if any. In the above example, if the agent chooses to make a new offer, it may decide among different alternatives the best one to propose.

In most works on modeling dialogs, the definition of a protocol poses no problems. However, the situation is different for dialog strategies. There is no methodology and no formal models for defining them. There is even no consensus on the different ingredients involved when defining a strategy. Regarding persuasion dialogs, there are very few works devoted to the notion of strategy in the literature if we except the work done in [START_REF] Amgoud | Strategical considerations for argumentative agents[END_REF][START_REF] Kakas | Layered strategies and protocols for argumentation based agent interaction[END_REF]. In these works, different criteria have been proposed for the argument selection. As for negotiation dialogs, it has been argued that the game-theoretic approaches characterize correctly optimal strategies [START_REF] Kraus | Strategic negotiation in multi-agent environments[END_REF][START_REF] Rosenschein | Rules of encounter: Designing conventions for automated negotiation among computers[END_REF]. However, another line of research [START_REF] Jennings | Automated negotiation: Prospects, methods and challenges[END_REF][START_REF] Kraus | Reaching agreements through argumentation: a logical model and implementation[END_REF][START_REF] Parsons | Agents that reason and negotiate by arguing[END_REF][START_REF] Sycara | Persuasive argumentation in negotiation[END_REF] has emphasized the limits of game-theoretic approaches for negotiation, and has shown the interest of arguing during a negotiation. Consequently, the optimal strategies given by game theory are no longer valid and not suitable. In [START_REF] Amgoud | On the study of negotiation strategies[END_REF], the authors have studied the problem of choosing the best offer to propose during a dialog and several criteria have been suggested. However, in that framework, the act offer is supposed to be chosen by the agent. Thus, this work has focused only on the second step of the decision process.

This paper argues that the strategy is a decision problem in which an agent tries to choose among different alternatives the best option, which according to its beliefs, will satisfy at least its most important goals. Two kinds of goals (resp. of beliefs) are distinguished: the strategic and the functional goals (resp. the strategic and basic beliefs).

The strategic goals are the meta level goals of the agent. Such goals will help an agent, on the basis of the strategic beliefs, to select the type of act to utter. Regarding functional goals, they will help an agent to select, on the basis of the basic beliefs to select the content of a move.

We propose a formal model for defining strategies. The model takes as input two sets of goals: the strategic and the functional goals together with the strategic and basic beliefs and returns among the possible replies allowed by the protocol after a given act, the next move (act + its content) to play. The model is an extension of the argument-based decision framework proposed in [START_REF] Amgoud | A general argumentation framework for inference and decision making[END_REF]. The basic idea behind this model is to construct for each alternative the different arguments (reasons) supporting it, then to compare pairs of alternatives on the basis of the quality of their supporting arguments.

The paper is organized as follows: Section 2 presents the different classes of goals and beliefs maintained by an agent. Section 3 introduces the logical language which will be used throughout the paper. Section 4 introduces an abstract argumentationbased decision model which forms the backbone of our approach. Section 5 presents an instantiation of that abstract model for computing the best move to play among the different replies allowed by the protocol. Section 6 introduces a second instantiation of the abstract model for computing the content of the move selected by the first instantiation. The whole framework is then illustrated in section 8. Section 9 is devoted to some concluding remarks and some perspectives.

Agents' mental states

During a dialog, an agent makes two decisions: it first selects the type of act to utter, for instance making a new offer, asking a question or arguing. Once the act chosen, the agent should select the content of the act if necessary. We say if necessary because some acts such as "withdrawal" from a dialog does not need a content. However, for an act "offer", it is important to accompany the act with an appropriate content. If the agents are negotiating the "price" of a car, then the act offer should contain a given price. The two above decision problems involve two different kinds of goals:

Strategic goals: For choosing the type of act to utter, an agent refers to what we call strategic goals. By strategic goals we mean the meta-level goals of the agent such as "minimizing the dialog time", "selling at the end of the dialog", etc. Suppose that at a given step of a negotiation dialog, an agent has to choose between making an offer and asking a question. If the agent wants to minimize the dialog time then it would choose to make an offer instead of spending more time in questions. However, if the agent wants to get a maximum of information about the wishes of the other agent, then the agent would decide to ask a question. Strategic goals are generally independent of the subject of the dialog. If the agents are negotiating the place of a next meeting, then those goals are not related to the place. Functional goals: The goals of the agent which are directly related to the subject of the dialog are called functional goals. They represent what an agent wants to achieve or to get regarding the subject of the dialog. Let us take the example of the agent negotiation the place of a meeting. The agent may prefer a place which is not warm and not expensive. The agent may also prefer a place with an international airport. These functional goals are involved when selecting the content of a move. In a negotiation, an agent proposes offers that satisfy such goals.

As for goals, the beliefs involved in the two decision problems are also of different nature:

Strategic beliefs that are the meta-level beliefs of the agent. They may represent the beliefs of the agent about the dialog, and about the other agents involved in the dialog. In negotiation dialogs where agents are trying to find a common agreement, agents may intend to simulate the reasoning of the other agents. Thus it is important for each agent to consider the beliefs that it has on the other agents'goals and beliefs. Indeed, a common agreement can be more easily reached if the agents check that their offers may be consistent with what they believe are the goals of the others. Basic beliefs represent the beliefs of the agent about the environment and the subject of the dialog. Let us consider again the example of the agent negotiating the place of a meeting. Basic beliefs of the agent may include for instance the fact that "London is not warm", "Tunisia is hot", "London is very expensive", etc. This base may also contain some integrity constraints related to the dialog subject such as "the meeting cannot be at the same time in London and in Algeria".

The logical language

Let L be a propositional language, and W f f (L) be the set of well-formed formulas built from L. Each agent has the following bases:

B b = {(k p , ρ p ), p = 1, . . . , s},
where k p ∈ W f f (L), is the basic beliefs base. The beliefs can be less or more certain. They are associated with certainty levels ρ p . A pair (k p , ρ p ) means that k p is at least certain at a degree ρ p . B s = {(l j , δ j ), j = 1, . . . , m}, where l j ∈ W f f (L), is the strategic beliefs base. Each of these beliefs has a certainty level δ j . G s = {(g q , λ q ), q = 1, . . . , t}, where g q ∈ W f f (L), is a base of strategic goals.

The strategic goals can have different priority degrees, represented by λ q . A pair (g q , λ q ) means that the goal g q is important for the agent at least to a degree λ q . G f = {(go r , γ r ), r = 1, . . . , v}, where go r ∈ W f f (L), is the base of the functional goals of the agent. Each functional goal has a degree of importance denoted by γ r .

The different certainty levels and priority degrees are assumed to belong to a unique linearly ordered scale T with maximal element denoted by 1 (corresponding to total certainty and full priority) and a minimal element denoted by 0 corresponding to the complete absence of certainty or priority. We shall denote by B * b , B * s , G * s and G * f the corresponding sets of propositional formulas when weights are ignored.

Let S be the set of speech acts allowed by the protocol. S may contain acts such as "'Offer' for making offers in negotiation dialogs, "Question" for asking questions, "Assert" for asserting information such as "the weather is beautiful", "Argue" for presenting arguments in persuasion dialogs, etc. The protocol precises for each act the possible replies to it. Let us suppose that the function Replies returns for each act, all the legal replies to it.

Replies: S -→ 2 S Some acts may have a content. For instance, an act "Offer" should be accompanied with a content such as a price, a town, etc. However, the act "Withdraw" does not need any content. Such acts will then have an empty content, denoted by the symbol "?". In what follows, the function Content returns for a given act, the set of its possible contents. Formally:

Content: S -→ 2 W f f (L)∪{?} For instance, Content(W ithdraw) = {?}, Content(Of f er) = {London, Algeria}.
During a dialog, agents exchange moves which are pairs: a speech act and its content. Formally: Definition 1 (Moves). A move is a pair (a, x), where a ∈ S and x ∈ Content(a).

The strategy problem is formalized as follows:

Definition 2 (The strategy problem). Let (a, x) be the current move in a dialog. What is the next move (a , x ) to utter such that a ∈ Replies(a) ?

To answer this question, one should find both a and x . Indeed, a is the "best" element in Replies(a) that satisfies G * s according to B * s . This will be denoted by: B * s , a → G * s . Here by "best" we mean the act that satisfies as much important goals as possible.

Concerning x , this is also the "best" element among X ⊆ W f f (L) that satisfies G * f according to B * b . This will be denoted by: B * b , x → G * f . Here the set X is exactly the set of different alternatives concerning the content of a move. This set may contain different offers (eg. different town) if we have to choose the content of the act "offer", it may contain a set of formulas if we have to choose the content of the act "Assert", it may also contain a set of arguments if one has to select the content of the move "Argue", etc.

The solution to the strategy problem is the pair

(a , x ) such that (B * s , a → G * s ) ∧ (B * b , x → G * f ).

The abstract argumentation-based decision model

Recently, Amgoud [START_REF] Amgoud | A general argumentation framework for inference and decision making[END_REF] has proposed a formal framework for making decisions under uncertainty on the basis of arguments that can be built in favor of and against a possible choice. Such an approach has two obvious merits. First, decisions can be more easily explained. Moreover, argumentation-based decision is maybe closer to the way humans make decisions than approaches requiring explicit utility functions and uncertainty distributions.

Solving a decision problem amounts to defining a pre-ordering, usually a complete one, on a set X of possible choices (or decisions), on the basis of the different consequences of each decision. In our case, the set X may be either the set Replies(a) of the possible replies to a move, or the set Content(a). The basic idea behind an argumentation-based model is to construct arguments in favor of and against each decision, to evaluate such arguments, and finally to apply some principle for comparing the decisions on the basis of the arguments and their quality or strengths. Thus, an argumentation-based decision process can be decomposed into the following steps:

1. Constructing arguments in favor of /against each decision in X . 2. Evaluating the strength of each argument. 3. Comparing decisions on the basis of their arguments. 4. Defining a pre-ordering on X .

Definition 3 (Argumentation-based decision framework

). An argumentation-based decision framework is a tuple <X , A, , P rinc > where:

-X is a set of all possible decisions. -A is a set of arguments.

is a (partial or complete) pre-ordering on A. -P rinc (for principle for comparing decisions), defines a (partial or complete) preordering on X , defined on the basis of arguments.

The output of the framework is a (complete or partial) pre-ordering P rinc , on X . x 1 P rinc x 2 means that the decision x 1 is at least as preferred as the decision x 2 w.r.t. the principle P rinc.

Notation: Let A, B be two arguments of A. If is a pre-order, then A B means that A is at least as 'strong' as B.

and ≈ will denote respectively the strict ordering and the relation of equivalence associated with the preference between arguments. Hence, A B means that A is strictly preferred to B. A ≈ B means that A is preferred to B and B is preferred to A.

Different definitions of or different definitions of P rinc may lead to different decision frameworks which may not return the same results.

In what follows, Arg(x) denotes the set of arguments in A which are in favor of x. At the core of our framework is the use of a principle that allows for an argument-based comparison of decisions. Indeed, these principles capture different profiles of agents regarding decision making. Below we present one intuitive principle P rinc, i.e agent profile. This principle, called promotion focus principle (Prom), prefers a choice that has at least one supporting argument which is preferred to (or stronger than) any supporting argument of the other choice. Formally: Definition 4 (Promotion focus). Let <X , A, , P rom > be an argumentation-based decision framework, and Let x 1 , x 2 ∈ X .

x 1 P rom x 2 w.r.t P rom iff ∃ A ∈ Arg(x 1 ) such that ∀ B ∈ Arg(x 2 ), A B.
Obviously, this is a sample of the many principles that we may consider. Human deciders may actually use more complicated principles. This section presents an instantiation of the above model in order to select the next move to utter. Let us recall the strategy problem. Let (a, x) be the current move in a dialog. What is the next move (a , x ) to utter such that a ∈ Replies(a) and x ∈ Content(a)? The strategic decision model will select among Replies(a) the best act to utter, say a . Thus, the set Replies(a) will play the role of X . Let us now define the arguments in favor of each d ∈ Replies(a). Those arguments are built from the strategic beliefs base B s of the agent and its strategic goals base G s .

The idea is that a decision is justified and supported if it leads to the satisfaction of at least the most important goals of the agent, taking into account the most certain part of knowledge. Formally: Definition 5 (Argument). An argument in favor of a choice d is a triple A = <S, g, d> such that:

-d ∈ Replies(a) -S ⊆ B * s and g ∈ G * s -S ∪ {d} is consistent -S ∪ {d} g
-S is minimal (for set inclusion) among the sets satisfying the above conditions.

S is the support of the argument, g is the goal which is reached by the choice d, and d is the conclusion of the argument. The set A s gathers all the arguments which can be constructed from <B s , G s , Replies(a)>.

Since the bases B s and G s are weighted, arguments in favor of a decision are more or less strong.

Definition 6 (Strength of an Argument). Let A = <S, g, d> be an argument in A s . The strength of A is a pair <Level s (A), W eight s (A)> such that:

-The certainty level of the argument is Level

s (A) = min{ρ i | k i ∈ S and (k i , ρ i ) ∈ B s }. If S = ∅ then Level s (A) = 1. -The degree of satisfaction of the argument is W eight s (A) = λ with (g, λ) ∈ G s .
Then, strengths of arguments make it possible to compare pairs of arguments as follows:

Definition 7. Let A and B be two arguments in A s . A is preferred to B, denoted A s B, iff min(Level s (A), W eight s (A)) ≥ min(Level s (B), W eight s (B)).
Property 1. The relation s is a complete preorder ( s is reflexive and transitive). Now that the arguments defined, we are able to present the strategic decision model which will be used to return the best reply a at each step of a dialog.

Definition 8 (Strategic decision model).

A strategic decision model is a tuple <Replies(a), A s , s , P rinc >.

According to the agent profile, a principle P rinc will be chosen to compare decisions. If for instance, an agent is pessimistic then it will select the Prom priciple and thus the decisions are compared as follows: Definition 9. Let a 1 , a 2 ∈ Replies(a). a 1 P rom a 2 w.r.t P rom iff ∃ A ∈ Arg(a 1 ) such that ∀ B ∈ Arg(a 2 ), A s B. Property 2. The relation P rom is a complete preorder.

Since the above relation is a complete preorder, it may be the case that several choices will be equally preferred. The most preferred ones will be returned by the function Best.

Definition 10 (Best decisions). The set of best decisions is Best(Replies(a)) = {a i ∈ Replies(a), s.t.∀ a j ∈ Replies(a), a i P rom a j }.

Property 3. If A s = ∅, then Best(Replies(a)) = ∅.
Note that when the set of arguments is empty, then the set of best decisions is also empty. This means that all the decisions are equally preferred, and there is no way to choose between them. In such a situation, the decision maker chooses one randomly.

Definition 11 (Best move). The best move to play (or the next reply in a dialog) is a ∈ Best(Replies(a)).

The functional decision model

Once the speech act to utter selected by the previous strategic decision model, say a ∈ Best(Replies(a)), one should select its content if necessary among the elements of Content(a ). Here Content(a ) depends on the nature of the selected speech act. For instance, if the selected speech act is an "Offer", then Content(a ) will contain different objects such as prices if the agents are negotiating a price of a product, different towns if they are negotiating a place of the next holidays. Now, if the selected speech act is "Argue" which allows the exchange of arguments, then the content of this act should be an argument, thus Content(a ) will contain the possible arguments. In any case, we suppose that Content(a ) contains a set of propositional formulas. Even in the case of a set of arguments, every argument will be refered to it by a propositional formula. Arguments in favor of each element in Content(a ) are built from the basic beliefs base and the functional goals base. The strength of these arguments is defined exactly as in the previous section by replacing the corresponding bases.

Definition 13 (Strength of an Argument). Let A = <S, g, d> be an argument in A f . The strength of A is a pair <Level f (A), W eight f (A)> such that:

-The certainty level of the argument is Level

f (A) = min{ρ i | k i ∈ S and (k i , ρ i ) ∈ B b }. If S = ∅ then Level f (A) = 1. -The degree of satisfaction of the argument is W eight f (A) = λ with (g, λ) ∈ G f .
Then, strengths of arguments make it possible to compare pairs of arguments as follows:

Definition 14. Let A and B be two arguments in A f . A is preferred to B, denoted A f B, iff min(Level f (A), W eight f (A)) ≥ min(Level f (B), W eight f (B)).
The arguments against decisions in X are defined in the same way as in the previous section. We have just to replace the base B s by B b , G s by G f and Replies(a) by X . The functional model which computes the best content of a move is defined as follows:

Definition 15 (Functional decision model). A functional decision model is a tuple <Content(a ), A f , f , P rinc >.

Again according to the agent profile, a principle P rinc will be chosen to compare decisions. If for instance, an agent is pessimistic then it will select the Prom principle and thus the decisions are compared as follows:

Definition 16. Let x 1 , x 2 ∈ X . x 1 P rom x 2 w.r.t P rom iff ∃ A ∈ Arg(x 1 ) such that ∀ B ∈ Arg P (x 2 ), A f B.
Here again, the above relation is a complete preorder, and consequently several options may be equally preferred.

Definition 17 (Best decisions). The set of best decisions is

Best(Content(a )) = {x i ∈ Content(a ), s.t.∀ x j ∈ Content(a ), x i P rom x j }.
The content x to utter is an element of Best(Content(a )) chosen randomly. Formally:

Definition 18 (Best move). The best content is x such that x ∈ Best(Content(a )).

Computing the next move in a dialogue

In the previous section, we have presented a formal framework for explaining, oredering and making decisions. In what follows, we will show how that framework can be used for move selection. Let (a, x) be the current move of the dialogue, and an agent has to choose the next one, say (a , x ). The act a is returned as a best option by the framework <Replies(a), A s , s , P rom > (i.e a ∈ Best(Replies(a))), whereas the content x is among the best options returned by the framework <Content(a ), A f , f , P rom >, i.e. x ∈ Best(Content(a )).

The basic idea is to look for the best replies for an act a. In case there is no solution, the answer will be (?, ?) meaning that there is no rational solution. This in fact corresponds either to the situation the set of strategic goals is empty, or the case where no alternative among the allowed replies satisfies the strategic goals of the agent.

In case there is at least one preferred solution, one should look for a possible content. If there is no possible content, then the chosen act is removed and the same process is repeated with the remaining acts. Note that the case of the existence of a preferred act but no its content is explained by the fact that the strategic goals of the agent are not compatible with its functional goals. Moreover, two forms of incompatibilities are distinguished: strong incompatibility in which there is no act which can be accompanied with a content, and a weak incompatibility in which only some acts can be associated with contents. The above idea of computing the next move is skeched in the following algorithm:

Function 1 Computing the best move

Parameters: a current move (a, x), a theory X , Bs, B f , Gs, G f 1: X ← Replies(a); 2: failure ← ⊥; 3: while X = ∅ and ¬ failure do 4:

if Best(X ) = ∅ then 5: failure ← ; return (?, ?); 6: 7:

else a ∈ Best(Replies(a)) of the argumentation system Replies(a), As, s, P rom (a' is chosen randomly); 8:

if Content(a ) =? then 9:

failure ← ; return (a , ?); 10: 11: else 12:

if Best(Content(a )) = ∅ (best decisions of the argumentation system Content(a ), A f , f , P rom ); then 13:

X ← X -{a }; 14: else 15:

failure ← ; 16:

return (a , x ) with x ∈ Content(a );

The following properties can be shown:

Property 4. If G s = ∅, or B s = ∅, then the next move is (?, ?).
To illustrate the formal model, we will present an example of auction protocols, the Dutch auction, which is used in the implementation of the fish market interaction protocol [START_REF] Noriega | Towards a test-bed for trading agents in electronic auction markets[END_REF].

The idea here is that seller S wants to sell an item using an auction. A number of potential buyers B 1 , . . . , B n , called also bidders, participate in rounds of auctions. There is at least one round for each item during, which the auctioneer counts down the price for the item and buyers simply send a signal to say if they want to bid at the current price or not.

In the context of fish market, the protocol is indeed, organized in terms of rounds. At each round, the seller proposes a price for the item. If there is no bidder then the price is lowered by a set amount until a bid is received. However, if the item reaches its reserve price the seller declares the item withdrawn and closes the round. If there is more than one bid, the item is not sold to any buyer, and the seller restarts the round at a higher price. Otherwise, if there is only one bid submitted at the current price, the seller atributes the item to that buyer. In this protocol, the set of allowed moves is then:

S = {Of f er, Accept, P ass, Attribute, W ithdraw}
The first move allows the seller to propose prices, the second move allows buyers to bid i.e to accept current price, the move P ass allows also the buyers to pass their turn by saying nothing, the move Attribute allows the seller to attibute the item to the selected buyer, and the last move W ithdraw allows the seller to withdraw the item from the auction. The following possible replies are also given by the protocol:

Replies(Of f er) ⊆ {Accept, P ass} Replies(Accept) ⊆ {Of f er, Attribute} Replies(P ass) ⊆ {Of f er, W ithdraw} The dialog starts always by a move Of f er uttered by the seller.

The seller has a strategic goal which consists of minimizing the auction time. This goal is stored in the strategic goal base of the agent. The seller has also some functional goals. The first one consist of maximizing its gain max -gain. Moreover, a seller has a starting price and also a reserve price which represents the minimum amount that it will accept for the item. Thus a functional goal of this agent would be to have a price at least equal to the reserve price, good -price.

G S f = {(good price, 1)}

The functional beliefs of the seller are given in its beliefs base:

B S f = {(current price > reserve price ∧ Of f er(current price) → good price, 1), (current price > reserve price ∧ Attribute(current price) → good price, 1), (current price < reserve price ∧ Of f er(current price) → ¬good price, 1)}

Regarding the buyers, the aim of B 1 is to get the item for the lowest possible price cheap at most at bound price, and the aim of B 2 is to get the item for the lowest possible price max prof it at most at bound price/2, that is the agent B 2 bid for the current price only when he could make at least 100% profit on the item. These last are functional goals of the buyers since it concerns the subject of the negotiation. For the sake of simplicity, these agents do not have strategic beliefs and goals. S : Of f er(current price) . In this case, the only possible move to the agent is Of f er. Indeed, this is required by the protocol. An agent should select the content of that move. Here again, the agent has a starting price so it will present it. At this stage, the agent does not need its decision model in order to select the move. B 1 andB 2 : Accept(current price) . In this case, the current price is lower than bound price/2 for the agents. The agents have an argument in favor of Accept.

G B1 f ={(cheap,
In this case, they will choose Accept. S : Of f er(current price) . In this case, the item is not sold to any buyer since there is more than one bid. The seller restarts the round at a higher price. Indeed, this is required by the protocol. The only possible move to the agent is Of f er. An agent should select the content of that move. Here again, the agent has a higher price so it will present it as the cuurent price. At this stage, the agent does not need its decision model in order to select the move. Let'us suppose that the bound price/2 < current price < bound price.

B 1 : Accept(current price) . In this case, the current price current price is lower than the price bound of the agent. In this case the agent has an argument in favor of Accept because this will support its important goal cheap. In this case, the agent will choose Accept. B 2 : P ass . In this case, the current price current price is higher than bound price/2, and then the agent could not make 100% profit on the item. In this case the agent has a counter argument again Accept because this will violate its important goal max prof it, and no arguments in favor of it. However, it has an argument in favor of P ass since it will not violate the important goal. In this case, the agent will choose P ass. S : Attribute(current price) . The only possible move of the agent is Attribute.

Inded this is required by the protocol since there is only one bidder submitted at the current price. Moreover, the current price is higher than the reserve price. In this case the seller has an argument in favor of the content current price since this will support its important goal good price. The seller decides then to attribute the item to the bidder B 1 and closes the round.

Conclusion

A considerable amount of work has been devoted to the study of dialogs between autonomous agents and to development of formal models of dialog. In most works, the definition of a protocol poses no problems and several dialog protocols have been defined even for particular applications. However, the situation is different for dialog strategies. There are very few attemps for modeling strategies. Indeed, there is no methodology and no formal models for defining them. There is even no consensus on the different parameters involved when defining a strategy. This paper claims that during a dialog, a strategy is used only for defining the next move to play at each step of the dialog. This amounts to define the speech act to utter and its content if necessary. The strategy is then regarded as a two steps decision process: among all the replies allowed by the protocol, an agent should select the best speech act to play, then it should select the best content for that speech act.

The idea behind a decision problem is to define an ordering on a set of choices on the basis of the beliefs and the goals of the agent. We have argued in this paper that selecting a speech act and selecting a content of a speech act involve two different kinds of goals and two different kinds of beliefs. Indeed, an agent may have strategic goals which represent the meta-level goals of the agents about the whole dialog. An agent may have also functional goals which are directly related to the subject of the dialog. Similarly, an agent may have strategic beliefs which are meta-level beliefs about the dialog, the other agents, etc. It may also have some basic beliefs about the subject of the dialog. We have shown that the choice of the next speech is based on the strategic beliefs and the strategic goals, whereas the choice of the content is based on the basic beliefs and the functional goals.

We have then proposed a formal framework for defining strategies. This framework can be regarded as two separate systems: one of them take as input the possible replies allowed by a protocol, a set of strategic beliefs and a set of strategic goals and returns the best speech act, and the second system takes as input a set of alternatives, a set of basic beliefs and a set of functional goals and returns the best content of a speech act. The two systems are grounded on argumentation theory. The basic idea behind each system is to construct the arguments in favour and against each choice, to compute the strength of each argument and finally to compare pairs of choices on the basis of the quality of their supporting arguments. We have shown also the agents profiles play a key role in defining principles for comparing decisions. In this paper we have presented two examples: pessimistic agents which represent very cautious agents and optimistic agents which are adventurous ones.

An extension of this work would be to study more deeply the links between the strategic and the functional goals of an agent. In this paper, we suppose implicitly that there are coherent. However, in reality it may be the case that an agent has a strategic goal which is incompatible with a functional one. Let us take the example of an agent negotiating the price of a car. This agent may have as a strategic goal to sell at the end of the dialog. It may have also the goal of selling his car with highest price. These two goals are not compatible since if the agent wants really to sell at the end its car, it should reduce the price.

Definition 12 (

 12 Argument). An argument in favor of a choice d is a triple A = <S, g, d> such that:d ∈ Content(a ) -S ⊆ B * b and g ∈ G * f -S ∪ {d} is consistent -S ∪ {d} g -S isminimal (for set inclusion) among the sets satisfying the above conditions. S = Support(A) is the support of the argument, C = Consequences(A) its consequences (the goals which are reached by the decision d) and d = Conclusion(A) is the conclusion of the argument. The set A f gathers all the arguments which can be constructed from <B b , G f , X >.

  G S s = {(min time, 0.8)} This agent has some strategic beliefs such as: if the time spent in the round is higher than a certain bound time bound then it should stop the auction. B S s = {(time spent > time bound ∧ W ithdraw → min time, 1), (time spent < time bound ∧ Of f er → min time, 1), (time spent < time bound ∧ Attribute → min time, 1)(time spent > time bound ∧ Of f er → ¬min time, 1)}

  {(current price < bound price ∧ Accept(current price) → cheap, 1), (current price < bound price ∧ Accept(current price) → buy, 1), (current price > bound price ∧ Accept(current price) → ¬buy, 1), (current price > bound price ∧ Accept(current price) → ¬cheap, 1), (current price > bound price ∧ P ass → ¬buy, 1)}

	0.8), (buy, 0.7)}
	G B2 f ={(max prof it, 0.8), (buy, 0.7)}
	The buyers are supposed to have the following beliefs.
	B B1 f = B B2 f = {(current price < bound price/2 ∧ Accept(current price) →
	max prof it, 1), (current price < bound price/2 ∧ Accept(current price) →
	buy, 1), (current price > bound price/2 ∧ Accept(current price) →
	¬buy, 1), (current price > bound price/2 ∧ Accept(current price) →

¬max prof it, 1), (current price > bound price/2 ∧ P ass → ¬buy, 1)} Let us now consider the following dialog between the seller S and the two buyers B 1 and B 2 :


Aurélie Jayol

Véronique Dubois

Laurent Poirel

Patrice Nordmann

Rapid Detection of Polymyxin-Resistant Enterobacteriaceae from Blood Cultures

Enterobacterial strains resistant to polymyxins are being increasingly reported worldwide. The conventional methods for detection of colistin-resistant isolates such as broth microdilution remain time-consuming (24 to 48 h), and methods such as disc diffusion and Etest are not reliable. Recently, the rapid polymyxin NP test was developed for rapid identification of polymyxin-resistant Enterobacteriaceae. This test is based on the detection of glucose metabolism related to bacterial growth in the presence of a defined concentration of colistin (or polymyxin B). The formation of acid metabolites is evidenced by a color change of a pH indicator (red phenol) in less than 2 h. In this study, the polymyxin NP test was evaluated for detection of colistin-resistant Enterobacteriaceae directly from blood cultures. The test was performed with 73 blood culture sets (either spiked or clinical blood cultures) with various enterobacterial species. The test exhibited excellent discrimination between polymyxin-resistant and polymyxin-susceptible enterobacterial isolates, and results are obtained from blood cultures within 4 h. It is easy to perform and requires neither subculture nor a centrifugation step. This test is rapid, specific, and sensitive and allows early identification of polymyxin-resistant Enterobacteriaceae directly from blood cultures. he spread of carbapenemase-producing Enterobacteriaceaehas Tnowbeenreportedworl dwide [START_REF] Nordmann | The difficult-to-control spread of carbapenemase producers among Enterobacteriaceae worldwide[END_REF]. Considering the paucity of antibiotics that are effective against those multidrug-resistant bacteria, it is of utmost importance to preserve the clinical efficacy of last-resort antibiotics such as polymyxins (colistin and polymyxin B) [START_REF] Livermore | What remains against carbapenem-resistant Enterobacteriaceae? Evaluation of chloramphenicol, ciprofloxacin, colistin, fosfomycin, minocycline, nitrofurantoin, temocillin and tigecycline[END_REF]. However, polymyxin-resistant Enterobacteriaceaearebeing increasingly reported worldwide, exhibiting either chromosomal mutations (3) or plasmid-mediated mcr-1 gene acquisition (4). The methods available to determine polymyxin susceptibility require isolation and growth of the bacteria from the infected samples, and the susceptibility testing methods add, at least, an additional delay of 18 h to obtain the results [START_REF] Humphries | Susceptibility testing of the polymyxins: where are we now?[END_REF]. Moreover, routine methods used in the clinical microbiology laboratory (disk diffusion, Etest strips, and some automated systems such as the Vitek2 and the MicroScan) are not reliable for detecting polymyxin-resistant isolates [START_REF] Humphries | Susceptibility testing of the polymyxins: where are we now?[END_REF][START_REF] Lo-Ten-Foe | Comparative evaluation of the Vitek 2, disk diffusion, Etest, broth microdilution, and agar dilution susceptibility testing methods for colistin in clinical isolates, including heteroresistant Enterobacter cloacae and Acinetobacter baumannii strains[END_REF][START_REF] Maalej | Comparison of disc diffusion, Etest and agar dilution for susceptibility testing of colistin against Enterobacteriaceae[END_REF][START_REF] Tan | Comparison of Etest, Vitek and agar dilution for susceptibility testing of colistin[END_REF][START_REF] Perez | Evaluation of polymyxin susceptibility profile among KPC-producing Klebsiella pneumoniae using Etest and MicroScan Walk-Away automated system[END_REF]. Molecular tests are not effective for determining polymyxin resistance due to the variety of genes that may be altered or truncated as a source of chromosomal resistance [START_REF] Olaitan | Mechanisms of polymyxin resistance: acquired and intrinsic resistance in bacteria[END_REF].

Rapid identification and antimicrobial susceptibility testing are essential for guiding clinicians in the selection of the most appropriate treatment for patients with bloodstream infections. The mortality rates from sepsis in intensive care units range from 20 to 60% worldwide. Inappropriate initial antimicrobial therapy for septic shock occurs in about 20% of patients, is associated with a 5-fold reduction in survival [START_REF] Kumar | Initiation of inappropriate antimicrobial therapy results in a fivefold reduction of survival in human septic shock[END_REF], and is responsible for an increased length of hospital stay [START_REF] Garnacho-Montero | Mortality and morbidity attributable to inadequate empirical antimicrobial therapy in patients admitted to the ICU with sepsis: a matched cohort study[END_REF]. This is largely due to the fact that its takes several days to obtain the susceptibility pattern of the bacteria responsible for the septicemia. In Italy, a large hospital outbreak of colistin-resistant and carbapenemase (KPC)-producing Klebsiella pneumoniae isolates, correlating with the local increased colistin consumption, has been recently described [START_REF] Giani | Large nosocomial outbreak of colistin-resistant, carbapenemaseproducing Klebsiella pneumoniae traced to clonal expansion of an mgrB deletion mutant[END_REF]. Therefore, there is a need for a rapid detection of polymyxinresistant isolates from blood cultures.

Recently, a diagnostic test (the rapid polymyxin NP test) based on the detection of glucose metabolism related to bacterial growth in the presence of colistin has been developed to rapidly identify (<2 h) polymyxin-resistant enterobacterial strains from colonies grown on solid media [START_REF] Nordmann | Rapid detection of polymyxin resistance in Enterobacteriaceae[END_REF]. This test yields sensitivity and specificity values of 99.3% and 95.4%, respectively. It has not yet been evaluated with clinical samples.

The aim of this study was to determine the ability of the rapid polymyxin NP test to detect polymyxin-resistant Enterobacteriaceae from blood cultures. First, we evaluated this test with blood cultures spiked with colistin-resistant enterobacterial strains exhibiting various mechanisms of resistance (intrinsic or acquired, chromosomal, and plasmid-mediated). Then, the test was performed prospectively on clinical blood cultures positive for Gramnegative bacteria.

MATERIALS AND METHODS

Spiked blood cultures. The panel of strains used for spiking blood cultures included a single reference strain susceptible to colistin (Escherichia coli AT C C 25922) and 52 colistin-resistant enterobacterial strains (MICs of colistin ranging from 4 to >128 µg/ml). Among the latter strains, 5 strains exhibited an intrinsic polymyxin resistance trait (Proteus spp., n = 2; Providencia spp., n = 1; Morganella spp., n = 1; and Serratia spp., n = 1), and 47 strains presented an acquired resistance trait and belonged to various species (E. coli, n = 11; Klebsiella spp., n = 31; Enterobacter spp., n = 4; and Hafnia alvei, n = 1). Some of the strains had previously been characterized for their polymyxin resistance mechanisms at the molecular level [START_REF] Nordmann | Rapid detection of polymyxin resistance in Enterobacteriaceae[END_REF][START_REF] Jayol | Heteroresistance to colistin in Klebsiella pneumoniae associated with alterations in the PhoPQ regulatory system[END_REF][START_REF] Jayol | Acquisition of broad-spectrum cephalosporin resistance leading to colistin resistance in Klebsiella pneumoniae[END_REF][START_REF] Jayol | Resistance to colistin associated with a single amino acid change in protein PmrB among Klebsiella pneumoniae isolates of worldwide origin[END_REF][START_REF] Jayol | Modulation of mgrB gene expression as a source of colistin resistance in Klebsiella oxytoca[END_REF][START_REF] Poirel | The mgrB gene as a key target for acquired resistance to colistin in Klebsiella pneumoniae[END_REF][START_REF] Poirel | Plasmidmediated carbapenem and colistin resistance in a clinical isolate of Escherichia coli[END_REF].

To spike the blood cultures, the colistin-resistant enterobacterial strains were subcultured onto Luria-Bertani agar overnight. Then, aerobic and anaerobic blood culture vials without charcoal (BacT/Alert FA Plus and BacT/Alert FN Plus, respectively; bioMérieux, Marcy l'Etoile, France) containing 10 ml of sterile human blood were inoculated with 10 3 CFU/ml of the bacterial strain to be tested. This inoculum was prepared by diluting a 0.5 McFarland standard suspension (about 10 8 CFU/ml) in 0.9% NaCl. Then, blood culture vials were incubated until a positive blood culture was detected by the BacT/Alert 3D blood culture system. With this protocol, the time for detecting the positivity of the blood cultures ranged from 6 to 15 h, and the final inoculum ranged from 10 7 to 10 9 CFU/ml, as previously reported [START_REF] Dortet | Rapid detection of carbapenemase-producing Enterobacteriaceae from blood cultures[END_REF].

Clinical blood cultures. All sets of positive blood cultures recovered during the November 2015 to February 2016 period of time from nonduplicate patients that were detected as positive by the BacT/Alert 3D blood culture system (bioMérieux) and stained as Gram-negative were included. Both aerobic and anaerobic vials were tested. Species identification was carried out with the matrix-assisted laser desorption ionization-time of flight mass (MALDI-TOF MS) Biotyper system (Bruker Corporation, Bremen, Germany) after 3 h of incubation of the blood culture on chocolate agar. Positive blood cultures with nonentero-bacterial isolates or with a mix of bacteria were excluded from the testing. Overall, a total of 20 monomicrobial blood cultures positive for entero-bacterial isolates were tested (Table 1).

Colistin susceptibility testing. Colistin susceptibility testing was performed by determination of MICs using the broth microdilution method (BMD) according to the CLSI guidelines [START_REF]Methods for dilution of antimicrobial susceptibility tests for bacteria that grow aerobically; approved standard-9[END_REF][START_REF]Performance standards for antimicrobial susceptibility testing[END_REF]. The BMD method was carried out with colonies grown on chocolate agar after incubation of the positive blood cultures. The EUCAST guidelines (version 2015) were used for categorical agreement [START_REF]Antimicrobial Susceptibility Testing[END_REF].

Detection of colistin resistance from positive blood cultures using the rapid polymyxin NP test. For each positive blood culture tested (spiked or clinical blood culture), 50 µl of blood culture was mixed with 450 µl of sterile 0.9% NaCl (10-fold dilution). The rapid polymyxin NP test was then performed as described with bacterial colonies [START_REF] Nordmann | Rapid detection of polymyxin resistance in Enterobacteriaceae[END_REF]. Briefly, 50 µl of the 10-fold dilution of the blood culture was mixed with (i) 150 µl of colistin-free polymyxin NP solution and (ii) 150 µl of polymyxin NP solution containing 5 µg/ml of colistin sulfate (Sigma-Aldrich, Buchs, Switzerland) in a 96-well polystyrene plate (reference no. 82.1582.001; Sarstedt, Nümbrecht, Germany) (Fig. 1). The final concentration of colistin was 3.75 µg/ml in each well. In parallel, 50 µl of 0.9% NaCl was mixed with the polymyxin NP solution to verify the absence of medium contamination. The plate was incubated at 35 ± 2°C in ambient air for 4 h, and visual inspection was performed each hour to observe the color change. Test results were interpreted by technicians who were blinded to the sample identity. The test was considered negative when the well containing the mix with colistin remained orange and positive when it turned from orange to yellow (Fig. 1). The test was considered noninterpretable when the colistin-free well remained orange (absence of glucose metabolization) (Fig. 1). E. coli AT CC 25922 and a Morganella morganii strain were used as negative and positive controls, respectively.

RESULTS AND DISCUSSION

To determine the performance of the rapid polymyxin NP test directly from blood cultures, 73 blood culture sets (aerobic and anaerobic vials) positive for enterobacterial strains were tested, including monomicrobial clinical samples and blood cultures spiked with colistin-resistant isolates presenting various mechanisms of resistance (intrinsic, acquired chromosomally encoded, plasmid-mediated, and unknown mechanisms). The results for the rapid polymyxin NP test were compared with the MICs determined by the BMD method taken as the gold standard.

The 52 blood cultures spiked with enterobacterial strains resistant to colistin gave positive results in 2 to4h (Table 1), except for a single colistin-resistant E. coli isolate that also gave a negative result by using the rapid polymyxin NP test performed from col- onies [START_REF] Nordmann | Rapid detection of polymyxin resistance in Enterobacteriaceae[END_REF]. The mechanism of colistin resistance of this single isolate remains unknown. Twenty positive clinical blood culture sets detected by the BacT/Alert 3D blood culture system were also tested. Among them, four were positive with colistin-resistant enterobacterial isolates in 2 to4h of incubation: three isolates belonged to species that are naturally resistant to colistin (two Serratia marcescens isolates and a single Proteus vulgaris isolate) and a single H. alvei isolate showed acquired resistance to colistin. The rapid polymyxin NP test gave positive results for all of those isolates (Table 1). Sixteen blood cultures were grown with enterobacterial isolates belonging to genera naturally susceptible to colistin (E. coli, Klebsiella, Enterobacter, and Citrobacter). None of them presented acquired resistance to colistin (the MICs of colistin ranging from 0.125 to 0.5 µg/ml) and the rapid polymyxin NP test gave negative results. Positive blood cultures with nonfermenting bacterial isolates (Acinetobacter spp. and Pseudomonas spp.) gave noninterpretable results (Fig. 1).

A series of other conditions (variable blood culture dilutions or conditions of atmosphere incubation) were tested but gave less optimal results. Indeed, the test performed without blood culture dilution revealed that the excess of blood prevented the optimal reading of color changes. We did not observe spontaneous lysis of the blood cultures that might possibly have interfered with the results of the test. Other blood culture dilutions (1/5 or 1/100) gave less rapid positive results (data not shown). Incubation under CO 2 gave false-positive results because of excessive acidification of the polymyxin NP solution, as opposed to results obtained with the rapid polymyxin NP test performed with bacterial colonies [START_REF] Nordmann | Rapid detection of polymyxin resistance in Enterobacteriaceae[END_REF].

This test performed from blood cultures may have the same limitation as the rapid polymyxin NP test performed from bacterial colonies (13), i.e., the lack of detection of heteroresistant isolates with low MICs to polymyxins by BMD. This limitation to be further explored.

In conclusion, the rapid polymyxin NP test from positive blood cultures showed good performances for the detection of enterobacterial isolates resistant to colistin. It shortens the delay in obtaining results to ca. 4 h versus 48 h for standard antibiotic susceptibility testing (24 h for obtaining a bacterial culture and 24 additional hours for susceptibility testing). This test may be implemented for routine testing of blood cultures and is best when combined with a rapid identification technique such as MALDI-TOF technology. It is cost-effective since it avoids in particular the time-consuming steps of manual determination of MIC values (e.g., powder weighing and dilution). As highlighted above, test allows rapid identification of polymyxin-resistant Enterobacteriaceae responsible for bacteremia, which is not possible molecular techniques, considering the complexity and the diversity of the polymyxin resistance mechanisms.

Early detection of colistin-resistant strains might contribute to early initiation of appropriate antibiotic therapy for septic patients infected with multidrug-resistant Enterobacteriaceae. In countries where carbapenemase-producing enterobacterial isolates are endemic (e.g., Greece and Italy), implementation of the test might contribute to early initiation of appropriate antibiotic therapy. Its use may preserve polymyxin as the last-resort antibiotherapy. In addition, implementation of contact isolation precautions for carriers of polymyxin-resistant isolates could prevent the development of outbreaks with those multidrug-resistant isolates.

FIG 1

 1 FIG 1Strategy for identification of colistin-resistant Enterobacteriaceae from blood cultures using the rapid polymyxin NP test. T, time.

TABLE 1

 1 Rapid polymyxin NP test results for spiked blood cultures and clinical blood cultures

	Mechanism of resistance	MIC for

(Continued on following page)

TABLE 1 (

 1 Continued) MIC values of colistin: the breakpoint value for susceptible is ≤ 2 µg/ml and for resistance is >2 µg/ml for Enterobacteriaceae according to the EUCAST[START_REF]Antimicrobial Susceptibility Testing[END_REF]. c Discrepant results obtained with the rapid polymyxin NP test compared to the broth dilution method are in bold. -, negative; +, positive.

	Mechanism of resistance	MIC for

a S, susceptible; R, resistant. b d NA, not applicable.

ACKNOWLEDGMENTS

This work was financed by the University of Fribourg, Switzerland.

An international patent form has been filed on behalf of the University of Fribourg (Switzerland) corresponding to the rapid polymyxin NP test.

FUNDING INFORMATION

This work, including the efforts of Aurelie Jayol, Véronique Dubois, Laurent Poirel, and Patrice Nordmann, was funded by University of Fribourg, Switzerland.


Sajad Daei

Saeed Razavikia

Marios Kountouris
email: kountour@eurecom.fr

Mikael Skoglund

Gabor Fodor

Carlo Fischione
email: carlofi@kth.se

Blind Asynchronous Goal-Oriented Detection for Massive Connectivity

Keywords: Random access, reconstruction-free inference, goal-oriented optimization, Internet of Things, MIMO communications systems, atomic norm minimization

Resource allocation and multiple access schemes are instrumental for the success of communication networks, which facilitate seamless wireless connectivity among a growing population of uncoordinated and non-synchronized users. In this paper, we present a novel random access scheme that addresses one of the most severe barriers of current strategies to achieve massive connectivity and ultra reliable and low latency communications for 6G. The proposed scheme utilizes wireless channels' angular continuous group-sparsity feature to provide low latency, high reliability, and massive access features in the face of limited time-bandwidth resources, asynchronous transmissions, and preamble errors. Specifically, a reconstruction-free goal oriented optimization problem is proposed which preserves the angular information of active devices and is then complemented by a clustering algorithm to assign active users to specific groups. This allows to identify active stationary devices according to their line of sight angles. Additionally, for mobile devices, an alternating minimization algorithm is proposed to recover their preamble, data, and channel gains simultaneously, enabling the identification of active mobile users. Simulation results show that the proposed algorithm provides excellent performance and supports a massive number of devices. Moreover, the performance of the proposed scheme is independent of the total number of devices, distinguishing it from other random access schemes. The proposed method provides a unified solution to meet the requirements of machine-type communications and ultra reliable and low latency communications, making it an important contribution to the emerging 6G networks.

I. INTRODUCTION

Wireless connectivity continuously evolves and will increasingly play a critical role in people's everyday lives. Internet of Things (IoT) devices in beyond 5G (B5G) and 6G systems will create new applications such as smart homes, smart manufacturing, autonomous vehicles, healthcare monitoring, and smart learning. To address these applications, 5G and B5G specifications have identified two essential use cases for machine-type user equipment (UE) in IoT: ultra-reliable and low latency communications (URLLC) and massive machinetype communications (mMTC). These two features will coexist in IoT, enabling data transmission from many UEs anywhere and anytime [START_REF] Razavikia | Blind asynchronous over-the-air federated edge learning[END_REF]- [START_REF] Razavikia | Computing functions over-the-air using digital modulations[END_REF].

Random access (RA) is an indispensable component of 5G and B5G communication between UEs and base station (BS). There are two different ways that UEs can access the network: sourced RA (S-RA) and unsourced RA (U-RA). In S-RA, which is suitable for device-oriented applications, UEs first receive information from the network that helps them to determine when to transmit their data. In contrast, in U-RAintroduced in [START_REF] Polyanskiy | A perspective on massive random-access[END_REF], the BS does not identify the UEs, and only the transmitted messages matter for the BS. Thus, U-RA is employed in the so-called content-oriented applications.

There are two different ways of managing data transmission in sourced RA: grant-based sourced RA (S-GBRA) and grantfree sourced RA (S-GFRA). In S-GBRA, UEs request permission or a grant from the BS to transmit data, while in S-GBRA, UEs transmit their data without waiting to get permission from the BS. Grant-based unsourced RA is typically unnecessary due to the absence of a requirement to identify UEs in such cases. The S-GBRA strategy [START_REF] Hasan | Random access for machineto-machine communication in LTE-advanced networks: Issues and approaches[END_REF], [START_REF] Björnson | A random access protocol for pilot allocation in crowded massive MIMO systems[END_REF], which has often been used in human-type communications, involves four stages: preamble selection, resource allocation, connection request, and contention resolution (see [START_REF] Björnson | A random access protocol for pilot allocation in crowded massive MIMO systems[END_REF] for more details). Recently, advanced methods have been proposed (see, e.g., [START_REF] Björnson | A random access protocol for pilot allocation in crowded massive MIMO systems[END_REF]) to reduce the collision probability in S-GBRA. However, these types of strategies result in significant signaling overhead and latency, making them unattractive for battery-driven mMTC devices that have short data payloads, sparse activity rates (sporadic traffic), and low latency requirements. To fulfill the requirements of mMTC, the GFRA scheme has been proposed in 5G as an alternative to the GB approach [START_REF] Chen | Sparse activity detection in multi-cell massive MIMO exploiting channel large-scale fading[END_REF]- [START_REF] Afshar | Active user detection and channel estimation for spatial-based random access in crowded massive MIMO systems via blind super-resolution[END_REF]. GFRA allows active UEs to transmit data packets without reserving channel resources, resulting in reduced access delay. However, the number of active UEs that can access the network is severely confined by the number of available orthogonal preambles, which is limited by channel coherence time. Moreover, nonorthogonal preambles can degrade performance [START_REF] Ke | Compressive sensing based adaptive active user detection and channel estimation: Massive access meets massive MIMO[END_REF]- [START_REF] Ding | Analysis of non-orthogonal sequences for grant-free RA with massive MIMO[END_REF]. Polyanskiy in [START_REF] Polyanskiy | A perspective on massive random-access[END_REF] proposed an interesting RA scheme that does not depend on the total number of inactive devices. The price to pay for this benefit is that users in this method are forced to select their messages from a known and shared large codebook and that the transmitted (active) messages need to be synchronized.

All in all, the theoretical study in [START_REF] Fengler | Non-bayesian activity detection, large-scale fading coefficient estimation, and unsourced random access with a massive MIMO receiver[END_REF] has summarized the aforementioned approaches and has shown that with the best existing approaches, the number of active UEs that can access the BS in S-RA and the number of active messages that can be transmitted in U-RA are K a " OpT 2 {log 2 p K T 2 qq and K a " OpT 2 {log 2 p 2 B T 2 qq, respectively, where K is the total number of users, T is the random access duration (time resource) and B is the number of bits that each user has to transmit in U-RA. This theoretical finding reveals that given a certain time resource T , the number K a of active UEs that can get a grant to access the BS in S-RA and the number of active messages that can be transmitted in U-RA depends explicitly and inversely on the total number of UEs (i.e., K) and messages (i.e., 2 B ), respectively, and is thus severely limited in large K and 2 B . More explicitly, this property poses severe restrictions for massive connectivity where a very large number of UEs want to connect to the BS with sporadic and irregular traffic and can be considered as a severe barrier to cater to a very large number of IoT devices in 6G wireless networks.

Given the aforementioned issues, the questions that arise in sourced and unsourced RA are:

1) Does massive connectivity in sourced and unsourced RA entails massive communication resources? 2) How essential is it to have strong assumptions, such as synchronization and shared codebook, in U-RA? 3) Is it possible to transmit a massive number of short asynchronous data payloads in U-RA? The succinct replies to these questions are negative, negative, and affirmative, respectively. This work provides some innovative approaches to thoroughly addressing these questions.

A. Our contributions

This paper proposes a novel strategy called Blind asynchronous Goal-Oriented Detection (BaGOD), which addresses the three questions posed in the previous section. BaGOD is designed based on the assumption that multiple input, multiple output (MIMO) channels exhibit angular continuous groupsparsity features. Indeed, only a few components in the angular domain contribute to the channel of each UE, and the angles of arrival (AoAs) corresponding to each UE lie alongside each other in a group, as shown in Fig. 2. BaGOD provides a novel goal-oriented optimization problem to achieve the specific goal of active user detection (AUD), which has a significantly smaller subset of information than the whole message information of all UEs. This specific optimization problem does not keep the information of UEs' messages and complex channel coefficients and is designed only to capture the goal. Interestingly, the solution to this reconstruction-free optimization problem reveals only the angle information of all active UEs. The specific feature of the BaGOD method, distinguishing it from all prior RA works, makes it independent of the total number of inactive UEs and messages in sourced and unsourced frameworks, respectively. After finding the angle information of active UEs by the proposed optimization problem, a clustering algorithm is developed to group active UEs based on their angles. At this step, stationary active UEs are identified by their line of sight (LoS) angles. For mobile UEs, we develop an alternative minimization (AM) method to recover the preambles of mobile UEs. The identification of mobile UEs is accomplished by both their preamble and LoS angles. Mobile UEs from different sections (shown by circles in Fig. 1(a) allow to use of the same preambles (shown with the same color in Fig. 1(a). This feature allows using the same orthogonal preambles for mobile UEs located on different angular ranges (e.g., Θ 1 , . . . , Θ 4 in Fig. 1(a) from the BS, which indeed leads to high detection performance. The goal-oriented feature of BaGOD provides some new features in the community of RA, which are listed below:

Channel and noise distributions are arbitrary. In contrast to prior RA works, such as covariance-based methods and approximate message passing (AMP) algorithms, there are no assumptions for the distributions of users' channels and noise in our method. The BS only has to know an upper bound η for the standard deviation of the measurement noise.

The total number of inactive users is irreverent. In sharp contrast to all prior sourced RA works, our proposed strategy does not search for the active devices among a total number of devices; instead, it indirectly obtains the identity (ID) of active stationary users. However, to identify active mobile devices, an AM algorithm has to be implemented. Therefore, our work can be considered the first S-RA strategy in wireless communications that is fully independent of the total number of inactive devices.

Minimal communication cost. In BaGOD, stationary devices do not require spending any resources for RA. They are identified by their LoS angles. Mobile devices in S-RA, however, require to include a preamble in their payload for their identification. In the case of U-RA, the (stationary and mobile) devices need to spend no resources for random access, and the resources are to be used only for data transmission. By incorporating angular diversity into the detection mechanism of mobile UEs, the number of orthogonal preambles required to identify mobile UEs can be substantially decreased, leading to a huge saving in resources.

Massive connectivity and ultra-reliability. In BaGOD, communication costs at the users' side for RA are somehow transferred to the computational complexity at the BS. In fact, the number of active users that can access the BS directly depends on the computational complexity that the BS can bear and is not a theoretical limitation of BaGOD. In addition to providing massive connectivity for stationary UEs, BaGOD allows a massive number of mobile UEs to access the BS by using the same orthogonal preambles for mobile UEs located at different angular ranges (see Fig. 1(a)) with respect to the BS (as shown in Fig. 1(a)). Besides this, the use of orthogonal preambles provides a high detection performance for mobile UEs leading to ultra-reliability. Unsourced RA with unknown individual codebooks. To the best of our knowledge, all prior unsourced RA methods follow the strong assumptions of [START_REF] Polyanskiy | A perspective on massive random-access[END_REF], in which the users are obliged to select one of predefined messages from a codebook that is shared among all users and BS. The maximum number of active messages that can be transmitted is severely limited in large codebooks with a large number of messages. Our method can be considered the first unsourced RA strategy in which users can send different arbitrary messages from different unknown codebooks satisfying certain assumptions in advance. Moreover, the allowable number of active transmitted messages is fully independent of the total number of inactive messages.

Asynchronous and erroneous data transmission. In the case of RA without any prior synchronization, there are some delays in the data transmission of UEs, which might lead to collisions, corruption, or data loss. Besides that, data or preamble errors in AUD can lead to inaccurate detection of active mobile users, false positives or false negatives [START_REF] Björnson | Random access protocol for massive MIMO: Strongest-user collision resolution[END_REF], and inefficient use of communication resources. Unlike [START_REF] Polyanskiy | A perspective on massive random-access[END_REF], the users in BaGOD do not need to be synchronized for data transmission. BaGOD takes into account these imperfect data or preamble transmission by modeling the delays and preamble errors of devices into a goal-oriented optimization and compensates for the effects of asynchronous and erroneous preambles.

This paper is a conference version of [START_REF] Daei | Blind goal-oriented massive access for future wireless networks[END_REF] with the following key differences:

B. Organization of the paper

The paper organization is as follows: In Section II, the considered system model is presented. In Section III, we provide our proposed RA approach, which consists of two steps: Goal-oriented optimization III-A and data/preamble recovery III-B. Section IV verifies the performance of our algorithm in comparison to state-of-the-art RA works by providing some numerical experiments. Lastly, the paper is concluded in Section V.

C. Notations

Bold lower-case letters x indicate vector quantities, and bold upper-case X denote matrices. The transpose and Hermitian of a matrix X are represented by X T and X H , respectively. For vector x P C n and matrix X P C n1ˆn2 , the ℓ 2 norm and Frobenius norm are represented by }x} 2 , }X} F , respectively. X ľ 0 means that X is a positive semidefinite matrix. For two arbitrary matrices A, B, xA, By represents the trace of B H A. P Ω p¨q is an operator transforming an arbitrary matrix to a reduced matrix with rows indexed by Ω. The Toeplitz matrix T pvq is defined as

T pvq " » - - - - v 1 v 2 . . . v N v 2 v 1 . . . v N ´1 . . . . . . . . . . . . v N v N ´1 . . . v 1 fi ffi ffi ffi fl (1)
where the pi, lq-th element is given by T pvq pi,lq "

" v i´l`1 i ě l v l´i`1 i ă l * . 1 Ω is a vector of size R N which has 1s
on the indices corresponding to the set Ω and zero elsewhere. diagpxq is a diagonal matrix whose main diagonal composes of the elements of x P R N . e i P R N is the canonical vector whose i-th element is 1 and zero elsewhere.

II. SYSTEM MODEL AND PROBLEM FORMULATION

We consider a wireless system with a single base station (BS) equipped with a uniform linear array (ULA) composed of N antennas, and K user equipments (UEs), each of which has a single antenna. Among these UEs, K a are active and identified by the set S AU . Following the conventional block fading wireless channel model, wherein the channel remains constant during a coherence time T , the channel vector in the frequency domain, corresponding to the UE at index k to the BS with L k ! N spatial angles of arrival (AoA) 1 , can be expressed as follows [START_REF] Zhang | Blind signal detection in massive MIMO: Exploiting the channel sparsity[END_REF]Eq. 7]:

h k " ÿ L k l"1 α k l apθ k l q ": A k α k P C N ˆ1. (2)
where α k l accounts for the gain of the l-th path, θ k l is the AoA of the l-th path for the k-th user and α k :" rα k 1 , ..., α k L k s T , A k :" ra r pθ k 1 q, ..., a r pθ k L k qs P C N ˆLk , and apθq is the array response vector of BS defined by

apθq " 1 ? N r1, e ´j2π d λ cospθq , ..., e ´j2π d λ pN ´1q cospθq s T , (3)
where λ and d are the carrier wavelength and antenna spacing, respectively. Then, the BS uses only the received signals by M antennas over N indexed by Ω Ď t1, ..., N u (|Ω| " M ) for each UE. Let ϕ k P C T ˆ1 be the information transmitted by k-th user 2 . Consider a practical case where active users have time-lag delays τ e k , k " 1, ..., K a with maximum delay τ max 3 , and their data have been under some gain errors, which are denoted by g k P R T ˆ1, k " 1, ..., K a . The received signal at the BS in the frequency domain becomes in the form of [START_REF] Liu | Massive connectivity with massive MIMO-part i: Device activity detection and channel estimation[END_REF]Eq. 7], [START_REF] Daei | Blind goal-oriented massive access for future wireless networks[END_REF]Eq. 5]:

Y Ω " P Ω `ÿ kPSAU h k r ϕ H k F H ext ˘`N " ÿ kPSAU P Ω ph k φ H k E k q `N
:"

ÿ kPSAU P Ω pX k q `N P C M ˆT , (4)
1 We assume there is little local scattering around BS, and the channel gains α k pθq of user k seen at the BS are constrained to lie in a small region pθ min k , θ max k q, known as an angular spread which composes of L k ! N spatial AoA [START_REF] Ke | Compressive sensing based adaptive active user detection and channel estimation: Massive access meets massive MIMO[END_REF], [START_REF] Djelouat | Joint user identification and channel estimation via exploiting spatial channel covariance in mMTC[END_REF], [START_REF] Ma | Sparse bayesian learning for the time-varying massive MIMO channels: Acquisition and tracking[END_REF] (see Figs. 2 and1(a)). 2 For simplicity, the data length of all UEs are considered to be the same. 3 Alternatively, their corresponding channels can have different delays.

where r ϕ k P C pT `τmaxq is the zero-padded, delayed version of ϕ k , F ext P C T ˆpT `τmaxq is the partial discrete Fourier transform (DFT) matrix , φ k :" F k ϕ k P C T ˆ1, F k :" P k F P C T ˆT is the DFT matrix applied to the last T samples of r ϕ k , F P C T ˆT is the regular DFT matrix of size T and P k is the permutation matrix. Also, X k :" h k φ H k E k , , E k " diagpr e k q P C T ˆT , and r e k " r1, e j2πτe k 1 T , . . . , e j2πτe k T ´1 T s T dp1 T ˆ1 `gk q and τ e k denotes the time-delay of UE k. Note that E k s are delay-gain error matrices that model the continuous-valued unknown time-lag delays between UEs and gain error of the preambles. Also, N P C M ˆT denotes the additive noise matrix which has arbitrary distribution with }N } F ď η and S AU Ď t1, . . . , Ku is the set of active users. X k can be described as a sparse linear combination of some building blocks (so-called atoms) taken from the atomic set r

A k :" tapθ k l qφ H k E k : }φ k } 2 " 1, θ P p0, πq, }E k } 2Ñ2 ď C e u
where C e :" 1 `ζ and ζ is an upper-bound for the gain error, i.e., max k }g k } 8 ď ζ.

III. PROPOSED METHOD

In this section, we describe our blind RA strategy. First, in Subsection III-A, we design a goal-oriented optimization problem that only reflects the ID of active UEs without doing any reconstruction tasks. In the second step provided in Subsection III-B, data recovery, channel estimation, and gainerror of preambles are investigated. It is worth mentioning that the first step is sufficient to identify active stationary UEs by their LoS angles, while for mobile active UEs, preamble and LoS angles are both required (see Fig. 1(b)). A summary of these two steps is provided in Algorithm 1.

A. Goal-oriented optimization problem

While the under-determined system of equations in (4) has KN T number of unknowns and only M T observations at the BS, the degrees of freedom thereof is ř kPSAU pL k `T q. This motivates us to use a challenging optimization problem that promotes angular sparsity features of all the channels corresponding to all UEs as follows: (see [START_REF] Sayyari | Blind two-dimensional superresolution in multiple-input single-output linear systems[END_REF]- [START_REF] Fernandez-Granda | Super-resolution of point sources via convex programming[END_REF] for more details):

min Z k PC N ˆT k"1,...,K Y ‹ PC M ˆT K ÿ k"1 β k }Z k } r A k `γ 2 }Y ´Y ‹ } 2 F s.t. Y ‹ " ÿ K k"1 P Ω pZ k q, (5)
where γ ą 0 is a regularization parameter that makes a balance between the noise energy and angular sparsity feature, and the atomic norm }¨} A k is the best convex surrogate for the number of atoms composing Z k which is defined as the minimum of the ℓ 1 norm of the coefficients forming Z k :

}Z k } r A k :" inftt ą 0 : Z k P tconvp r A k qu " inft L k ÿ l"1 c k l : Z k " L k ÿ l"1 c k l apθ k l qφ H k E k , c k l ą 0, }E k } 2Ñ2 ď C e , }φ k } 2 " 1u, (6)
where convp r Aq is the convex hull of r A. β k s are some parameters that are employed to compensate for the effects of synchronization and gain errors. If

β k " 1, then ř K k"1 }Z k } r A k
is a convex surrogate for the total number of paths, i.e., ř K k"1 L k . While the optimization problem stated in (6) may initially appear manageable due to its convexity, it presents significant challenges due to the continuous nature of the angles θ k . This continuous aspect renders the problem computationally intractable. Additionally, ( 6) is designed to extract both message and channel information for all UEs. However, the primary objective of this section is to detect the AoAs of active users, which represents a considerably smaller subset of the complete message and channel information for all users. To address this objective, we propose a new theorem that introduces a reconstruction-free optimization problem that only aims to reflect the goal of active user detection (AUD) (a goal-oriented feature related to the AoA information specifically corresponding to active users.)

Theorem 1. Let c 1 :" C e max k"1,...,K }ϕ k }2 min k β k ? N
and V ˚be the solution to the following optimization problem:

V ˚" argmax V PC N ˆT QPC N ˆN RexV , Y y ´1 2γ }V } 2 F s.t. " Q P Adj Ω pV qc 1 pP Adj Ω pV qq H c 1 I T ȷ ľ 0,
xT pe q q, Qy " 1 q"0 , q " ´N `1, ..., N ´1.

Then, the AoAs corresponding to the active users are uniquely identified provided that ∆ ą 1 N , where ∆ :" min k"1,...,K min i‰q | cospθ k i q ´cospθ k q q|,4 by finding angles that maximize the ℓ 2 norm of the goal-oriented dual polynomial q G pθq as follows:

p θ k l " arg max θPp0,πq }q G pθq} 2 , l " 1, ..., L k , k P S AU , ( 8
)
where q G pθq :" pP Adj Ω pV ˚qq H apθq. Proof. See Appendix A. The goal-oriented dual polynomial q G pθq contains all the necessary information for identifying active users. A typical example of the ℓ 2 norm of this function, }q G pθq} 2 , is shown in Fig. 3. The angles corresponding to active devices can be obtained by maximizing }q G pθq} 2 . The proposed optimization problem ( 7) is agnostic to the number of devices, K, and can be solved using optimization solvers, such as CVX [START_REF] Grant | CVX: MATLAB software for disciplined convex programming[END_REF]. However, solving this problem can be challenging in massive MIMO communication scenarios where N " 1, and conventional solvers, such as the SDPT3 solver of the CVX package, may not be able to provide the solution. To address this issue, a fast ADMM method can be designed, which reduces the computational complexity tailored to massive access [START_REF] Daei | Blind goal-oriented massive access for future wireless networks[END_REF]Algorithm 1]. Obtaining |q G pθq| 2 requires the matrix dual solution V , which is typically returned along with the primal variables by most CVX solvers. Optimization Problem (7) yields P Adj pV q, which can be utilized alongside [START_REF] Fengler | Pilot-based unsourced random access with a massive MIMO receiver, interference cancellation, and power control[END_REF] in Theorem 1 to estimate active angles. However, the association of angles with corresponding devices is not straightforward. We design a clustering method that groups angles into several clusters that correspond to active devices. First, we discretize the continuous function q G pθq on a desired angular grid. Second, we form the vector of angles achieving the maximum within a specific range. Third, we identify the boundary of clusters (jump points) by realizing the large variations in the vector of angles. By this task, all of the clusters with their lengths can be identified. The number of clusters denoted by p K a provides an estimate of K a , and the number of angles within the k-th cluster denoted by p L k gives an estimate of p L k . As a result, we can find estimates for the angles of each active user denoted by t p θ k u

x Ka k"1 . At this step, the BS can directly identify active stationary devices by their LoS angles. To identify active mobile devices, orthogonal preambles are also exploited, as detailed in the following subsection.

B. Recovery of preambles, channel amplitudes and delay-gain matrices

We propose an alternative minimization scheme to retrieve the preamble of each active device and the delay-gain errors. In particular, the following optimization problem should be solved:

min α k :"rα k 1 ,...,α k L k s, E k ,P k ,ϕ k }Y ´ÿ kP p SAU p L k ÿ l"1 α k l P Ω pap p θ k l qϕ H k F H P H k E k q} F s.t. }E k } 2Ñ2 ď C e , ϕ k ě 0, }ϕ k } 2 " 1, k " 1, . . . , p K a , (9)
where the non-negative constraint ϕ k ě 0 is included to remove the multiplication ambiguities of multiple elements.

Due to the unitary properties of the permutation matrices, the latter optimization problem can be further simplified to

min α k :"rα k 1 ,...,α k L k s, E k ,ϕ k }Y ´ÿ kP p SAU p L k ÿ l"1 α k l P Ω pap p θ k l qϕ H k F H E k q} F s.t. }E k } 2Ñ2 ď C e , ϕ k ě 0, }ϕ k } 2 " 1, k " 1, . . . , p K a , (10)
where P k is integrated into diagonal matrix E k without changing the spectral norm constrains. By using an alternative numerical optimization, the estimates of complex channel amplitudes, preambles, and permuted delay-gain error matrix, denoted by p α :" r p α 1 , ..., p α

x Ka s, Φ :" rϕ 1 , ..., ϕ

x Ka s P C T ˆx Ka and p E k , respectively, can be recovered. Following the successful recovery of the users' preamble ϕ k s, the user IDs and LoS angles are both exploited to identify active mobile UEs. The pseudo-code of the proposed method, which is indeed a summary of the aforementioned steps, is provided in Algorithm 1.

Algorithm 1 Blind asynchronous Goal-Oriented Detection (BaGOD) Require: Y P C M ˆT 1: Obtain V ˚by solving optimization in [START_REF] Chen | Sparse activity detection in multi-cell massive MIMO exploiting channel large-scale fading[END_REF].

2: Compute q G pθq " pP Adj Ω pV ˚qq H apθq by discretizing θ on a fine grid up to a desired accuracy.

IV. SIMULATIONS

In this section, we evaluate the detection performance of the BaGOD method and compare it to the AMP approach employed in [START_REF] Ke | Compressive sensing based adaptive active user detection and channel estimation: Massive access meets massive MIMO[END_REF] 5 . AMP uses the resource T for AUD and channel estimation, while BaGOD uses this resource for data recovery of stationary UEs and preamble and data recovery of mobile UEs. Here, we employ Gaussian distributed ϕ k s for AMP known to be the best distribution for AMP as discussed in [START_REF] Ke | Compressive sensing based adaptive active user detection and channel estimation: Massive access meets massive MIMO[END_REF] and a positive ϕ k uniformly distributed from U p0, 1q for BaGOD method. We consider different delays τ k s between ϕ k s of active UEs, which alternatively represent different phases of φ k s in the frequency domain. Moreover, we have considered some gain-error in the preambles of active mobile users, which affects the preamble recovery in Subsection III-B. The simulations are done for 50 Monte-Carlo trials to calculate P d , P f a . The regularization parameter γ is set to 1 η , where η is an upper bound for the standard deviation of the measurement noise, i.e., η ě }N } F . The signal to noise ratio is defined by SNR " 10 log 10 p }PΩpXq} 2 F M T σ 2 q. Fig. 4 shows comparisons between BaGOD and AMP methods with different T, N, K S , K M , K a,M , K a,S . Here, K S and K M represent the total number of stationary and mobile UEs, while K a,M and K a,S indicate the number of active mobile and stationary UEs, respectively. As it turns out, BaGOD provides a substantial performance improvement in the detection of both stationary and mobile devices in the considered scenarios. When the number of active UEs increases, the number of peaks in the goal-oriented dual polynomial (as illustrated in Fig. 3) also increases. This, in turn, makes it more difficult to identify the active UEs and ultimately results in a decrease in detection performance, as demonstrated in Fig. 4(a) and Fig. 4(b). K S does not have any role in the detection, as shown in Fig. 4(e). The utilization of LoS angles and orthogonal preambles for detecting active mobile UEs has resulted in a minimal impact of K M on detection performance, as evidenced by the data presented in Fig. 4(c). As depicted in Fig. 4(f), an increase in the number N of antennas results in sharper peaks of active UEs, making identification easier and improving detection performance. Fig. 4(d) shows that an increase in the number T of orthogonal preambles improves the identification of active mobile UEs. Moreover, the probability of detection and false alarm of AMP both tend towards one as T increases.

Furthermore, we observe that asynchronous active UEs can be identified by BaGOD perfectly, and asynchronous UEs do not make RA harder as long as the maximum delays do not exceed the channel coherence time. Aside from this, if we know an upper bound for the maximum preamble gain distortion, i.e., ζ ě max k }g k } 8 , we can compensate the effect of gain error in preamble recovery by solving [START_REF] Liu | Sparse signal processing for grant-free massive connectivity: A future paradigm for random access protocols in the internet of things[END_REF] which plays a key role in active mobile UE detection.

V. CONCLUSION

This paper proposes a novel strategy for RA in B5G and 6G networks based on reconstruction-free optimization. A goaloriented optimization approach is introduced to find a valuable continuous function that provides sufficient information to obtain the ID of active users. The proposed method achieves the goal of active user detection without reconstructing the corresponding channels and messages, making it independent of the number of devices. The proposed scheme offers a

Fig. 4. Detection performance comparison between BaGOD and AMP. a) versus the number K a,M of active mobile UEs for T " 2, N " 64, K S " 1500, K M " 500, K a,S " 3, Lmax " 20, and SNR " 10 dB b) versus the number K a,S of active stationary UEs for N " 64, T " 2, K S " 1500, K M " 500, K a,M " 3, Lmax " 20, and SNR " 10 dB c) versus the total number K M of mobile UEs for N " 128, K S " 1500, K a,S " 3, K a,M " 2, Lmax " 20, and SNR " 20 dB d) versus the number T of preambles for N " 64, K S " 1500, K M " 500, K a,S " 3, K a,M " 3, Lmax " 20, and SNR " 20 dB e) versus the number K S of stationary UEs for N " 128, K M " 500, K a,S " 3, K a,M " 3, Lmax " 20, and SNR " 20 dB f) versus the number of antennas N for T " 2, K S " 1500, K M " 500, K a,S " 3, K a,M " 3, Lmax " 20, and SNR " 20 dB.

promising solution to overcome the challenges of massive MTC and URLLC in IoT applications, which are essential for the success of smart cities and connected vehicles. Simulation results show that the proposed method meets the URLLC and massive connectivity requirements of 6G networks and outperforms existing RA methods.

APPENDIX A PROOF OF THEOREM 1

By following similar steps as in [11, Appendix B], one can obtain the dual problem of [START_REF] Hasan | Random access for machineto-machine communication in LTE-advanced networks: Issues and approaches[END_REF] where in the last step above, we used Hölder's inequality. A sufficient condition for the latter constraints in [START_REF] Daei | Blind goal-oriented massive access for future wireless networks[END_REF] to hold is given in the following relation:

}pP Adj Ω pV qq H apθ k q} 2 C e max k }ϕ k } 2 ď min k β k , (13)
for θ k P p0, πq, where we used the unitary properties of DFT and permutation matrices and that }g} 8 ď ζ. Then, by defining the notation c 1 and (3), ( 13) can be rewritten as follows:

T ÿ i"1 ˇˇN ÿ l"1
pP Adj Ω pV qq pl,iq c 1 e ´j2πpl´1q cospθq ˇˇ2 ď 1,

where θ P p0, πq. Next, we define a i as i-th column of P Adj Ω pV q, i.e., a i :" c 1 rpP Adj Ω pV qq p1,iq , ..., pP Adj Ω pV qq pN,iq s T and f pθq :" r1, ..., e j2πpN ´1q cospθq s T , ( 14) can be reformulated as

T ÿ i"1 |f pθq H a i | 2 ď 1, (15)
which implies that the polynomial 1 ´f pθq H ř T i"1 a i a H i f pθq is non-negative. Based on [33, Theorem 1.1], there exists a polynomial q 1 pθq :" ř N i"1 b i e ´j2πpi´1q cospθq " f pθq H b for some b P C N that 1 ´f pθq

Further, by ( 16), we have:

f H pθqQf pθq " xQ, f pθqf H pθqy " 1, @θ P p0, πq.

With the same arguments as in [11, Appendix C] (see Eq. (51) to Eq (67)), we can show that (18) leads to xT pe q q, Qy " 1 q"0 , q " ´N `1, ..., N ´1.

Therefore, ( 19) and ( 17) together lead to ř T i"1 |f pθq H a i | 2 ď 1 which is equivalent to [START_REF] Daei | Blind goal-oriented massive access for future wireless networks[END_REF].

  This work was supported in part by Digital Futures. The work of M. Kountouris has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant agreement No. 101003431). The work of Gabor Fodor was supported by Digital Futures Project PERCy. Saeed Razavikia and Carlo Fischione acknowledge the support of WASP, SSF SAICOM, VR, and Digital Futures.

Fig. 1 .

 1 Fig. 1. (a) The overall BaGOD scheme. Θ 1 , Θ 2 , Θ 3 , Θ 4 represent the angular ranges in which mobile UEs can have the same orthogonal preambles shown with the same colors. Stationary UEs do not need preambles. (b) Proposed blind massive access scheme. Bottom image: The BS has full access to the LoS angle information of stationary devices. Top image: UEs are moving, sending random preambles to the BS, which accounts for their identification. Note that for clarification purposes, preambles and data payloads are shown by sine and pulse waveforms, respectively.

'

  The active UEs are asynchronous in data transmissions. ' There are gain-errors in the preambles of active mobile UEs, which are incorporated in the goal-oriented optimization problem. ' The mobile active UEs are detected based on both preambles and LoS angles as shown in Fig. 1(b).

Fig. 2 .

 2 Fig.2. Angular continuous group-sparsity in the uplink channel. Only Ka " 3 UEs are active, and the maximum number of multi-path components are considered to be five (Lmax :" max k L k " 5) in this figure. Note that the channel in LoS angles has higher amplitudes compared to NLoS angles.

2 K 1 }q G pθq} 2 Fig. 3 .

 2123 Fig. 3. The ℓ 2 norm of the goal-oriented dual polynomial function i.e. }q G pθq} 2 . The angles for which }q G pθq} 2 achieves its maximum determine the angles of active UEs

  3: Localize the angles by finding all the maximums of ℓ 2 norm of q G pθq,i.e., p θ k l " arg max θPp0,πq }q G pθq} 2 , l " 1, ..., L k , k P S AU ,

	4: Perform the clustering method:
	rt p θ k u kP p SAU , p K a , t p L k u kP p SAU s " clusterp p θq.
	5: Solve the optimization problem 10 to obtain the estimates
	p α k , p ϕ k and delay-gain matrix p E k
	Return: p S AU , t x θ k u kP p SAU , t x ϕ k u kP p SAU , t x α k u kP p SAU , p K a	"
	| p S AU |, t p L k u kP p SAU , p h k :"	ř L k p l"1 p α k l ap p θ k l q, p E k , k P p S AU .

  The RA performance is quantified in terms of detection and false alarm probabilities, defined by P d " E|SAU SAUzSAU| K´Ka , respectively, where | p S AU zS AU | counts the number of elements in p S AU that are not present in S AU . Moreover, the detection and false alarm probabilities regarding stationary and mobile users are defined as P d,S " E|SSAU

	Ş Ka	p SAU|	and
	P f a " E| p
		Ş Ka,S SSAU| p	,
	P f a,S " E| p SSAUzSSAU| KS´Ka,S , and P d,M " E|SMAU Ka,M Ş p SMAU|	, P f a,M "
	E| p SMAUzSMAU| KM´Ka,M , respectively.

  Pp0,πq,φ k , }E k }2Ñ2ďCe }pP Adj Ω pV qq H apθ k q} 2 }E H k φ k } 2 ,

					Recall the definition of } ¨} r A k from (6), we can write
					}P Adj Ω pV q} d r A k	"	sup θ k Pp0,πq,φ k ,	xP Adj Ω pV q, apθ k qφ H k E k y
					}E k }2Ñ2ďCe
					"	sup
					θ k
					as follows
	max V PC N ˆT RexV , Y y	´1 2γ	}V } 2 F
	s.t. }P Adj Ω pV q} d r A k	ď β k , @θ k P p0, πq, k " 1, ..., K. (11)
	Here, } ¨}d r A k	is the dual norm associated with the atomic norm
	} ¨} r A k and is defined as
	}P Adj Ω pV q} d r A k	}Z} A k Ă :" sup ď1 xP Adj Ω pV q, Zy.	(12)

  i a H i f pθq " |q 1 pθq| 2 " f pθq H bb H f pθq. (16) Set Q " ř T i"1 a i a H i `bb H . Since both Q and Q´ř

		T
	H	ÿ
		i"1
						T i"1 a i a H i
	are positive semidefinite, using Schur complement lemma [34,
	Appendix A.5.5] leads to the semidefinite constraint:
		"	Q Ω pV qq H c 1 pP Adj	P Adj Ω pV qc 1 I T	ȷ	ľ 0.

a

The absolute value only for minimum separation ∆ is evaluated over the unit circle, e.g., |0.2 ´0.8| " 0.4.

It should be noted that, unlike[START_REF] Daei | Blind goal-oriented massive access for future wireless networks[END_REF], covariance-based methods are not utilized in the numerical results due to their inability to detect in the specific setting under consideration effectively.