Amit Samir Alili

Emrah Kumar Pandey

Akin Sisbot

Rachid Alami

Interleaving Symbolic and Geometric Reasoning for a Robotic Assistant ----(Extended Abstract)

Introduction

It is now well known that while symbolic task planners have been drastically improved to solve more and more complex symbolic problems the difficulty of successfully applying such planners to robotics problems still remains. Indeed, in such planners, actions such as "navigate" or "grasp" use abstracted applicability situations that might result in finding plans that cannot be refined at the geometrical level. This is due to the gap between the representation they are based on and the physical environment (see the pioneering paper [START_REF] Lozano-Perez | Handey: A robot system that recognizes, plans and manipulates[END_REF]).

We have proposed in [START_REF] Cambon | A robot task planner that merges symbolic and geometric reasoning[END_REF][START_REF] Cambon | A hybrid approach to intricate motion, manipulation and task planning[END_REF] a general framework, called AsyMov, for intricate motion, manipulation and task planning problems. This planner was based on the link between a symbolic planner running Metric FF [START_REF] Hoffmann | The metric-ff planning system: Translating "ignoring delete lists" to numeric state variables[END_REF] with a sophisticated geometric planner that was able to synthesize manipulation planning problems [START_REF] Alami | A Geometrical approach to planning manipulation tasks. the case of Discrete placements and Grasps[END_REF][START_REF] Siméon | Manipulation planning with probabilistic roadmaps[END_REF]. The second contribution of AsyMov was the ability to conduct a coordinated search of the symbolic task planner and its geometric counterpart.

In this paper, we extend this approach and apply it to the challenging context of human-robot cooperative manipulation. We propose a scheme that is still based on the coalition of a symbolic planner [START_REF] Alili | Planning and plan-execution for human-robot cooperative task achievement[END_REF]) and a geometric planner [START_REF] Pandey | Mightability maps: A perceptual level decisional framework for co-operative and competitive human-robot interaction[END_REF][START_REF] Sisbot | Spatial reasoning for human robot interaction[END_REF][START_REF] Marin Urias | Geometric tools for perspective taking for human-robot interaction[END_REF] but which provides a more elaborate interaction between the two planning environments. The overall planning system starts from a goal or a situation to achieve, and builds a so-called cooperative plan which is based on planned actions for the robot and estimation of feasibility of actions for the human.

The task planner builds incrementally the cooperative plan, a tree task structure -thanks to a HTN refinement process -whose leaves correspond to actions to be performed by the robot or by its human partner.

We describe here below the two components, the geometric and the symbolic planners, how they are invoked in a

The Geometric Planner

The geometric reasoning and planning system considers a geometric environment (see figure 4) composed of furniture (fixed obstacles), agents (robots and humans, represented as kinematic structures with manipulation and perception abilities) and objects that can be manipulated by the agents.

The geometric planner is able to plan feasible motions for agents (robot or human) as well as to reason on their accessibilities and their visibilities towards other agents or towards the features in the environment.

Layers of Geometric Planner

As illustrated in figure 1, the geometric planner consists of 3 main layers:

Geometric Tools Layer: This layer consists of a set of geometrical tools which provides the robot with the following geometrical analysis capabilities:

• A place in 3D space is reachable or visible from the perspective of an agent or not by applying a set of virtual actions e.g making the agent virtually to sit, to turn around, to lean forward, to standup etc. • An object is visible or not as well as visibility % of the object from the perspective of an agent. • The spatial relations of an object, e.g on the table, in the box, left of human etc.

Geometric Reasoning Layer: At the top of the basic layer, we have the geometrical reasoning layer, which geometrically finds out a set of points for performing various basic actions, few of them are:

• Put an object for human to take.

• Show an object to human.

• Hide an object from human.

This layer also does various other analyses, computations and planning, few of them are:

• Planning a path to navigate for an agent. Geometric Planner Geometric Reasoning

Geometric Validation and Refinement

Set of Geometric Tools • Planning a path to manipulate an object by an agent.

• Computing where to place a robot for performing a particular task. • Analyzing geometrical level of comfort of agents .

Validation and Refinement Layer: At the top layer of geometric planner we have a geometric validation and refinement interface, which communicates with external modules (symbolic planner in our case) and handles external requests, about geometric feasibility of a particular basic task. It maintains and updates the plan, as well as contains logics for backtracking at geometric level. As shown in figure 2, in our current implementation, the symbolic planner sends a request to geometric planner with following information:

• Name of the action, put, pick, move etc.

• The parameters of the action, on table, bottle, by robot, by human etc. • The set of constraints, for example a particular object should be visible, or should be put on a particular table etc.

Types of constraints

We have three types of constraints at geometric level:

• Internal constraints known to the geometric reasoning system for performing a particular basic task. • External/additional constraints provided by the symbolic planner for the same basic task. • Discovered constraints by geometric planner due to failure at later stages of validating another task in the sequence.

In fact, the beauty of our whole system is, the geometric planner will already have a basic set of constraints for reasoning to perform a particular action without need of any external constraint. Hence, additional constraints from symbolic planner will refine the solution space for better converging towards the final task to achieve.

! Solution Space Atomic Action ! ! ! ! ! ! ! ! ! Geometric
Another novelty of our system is that, in case of nonavailability of a solution for a particular action in the sequence, instead of directly sending the fail message to the symbolic planner, it will first try to backtrack at geometric level to find the possible cause of failure and refine the solution space of a particular action. In that sense robot will have a third set of geometric constraints, which it has discovered due to failure during validating the sequence of actions. This third set of discovered geometric constraints together with the set of constraints already known to the robot at geometric planner level and the set of additional constraints provided by the symbolic planner, will serve as the new set of constraints for avoiding failure at future steps while reiterating for validation of the plan after backtracking.

The Symbolic Planner

HATP (Human-Aware Task Planner) is a hierarchical task planner [START_REF] Alili | Planning and plan-execution for human-robot cooperative task achievement[END_REF]) designed to synthesize plans for a robot that might have to achieve goals in an environment where other "agents" are present (essentially humans). The robot will have to produce a plan by taking into account its capacities and the current state of the environment. What makes HATP different is that it allows the robot to take into account also the state and the capacities of the other agents and even their preferences. The result of a planning is a plan with several synchronized streams, the stream of the robot as well as a set of streams that are devoted to anticipate the future potential actions of the other agents [START_REF] Alili | Planning and plan-execution for human-robot cooperative task achievement[END_REF]). Besides complying with standard constraints, HATP plans are bound to additional properties like the satisfaction of "social rules" [START_REF] Alili | A task planner for an autonomous social robot[END_REF].

In order to consider geometric feasibility of symbolic plans, we have adapted HATP plan search process and ex-tended its world and task representation in order to provide a systematic link between the symbolic descriptions manipulated by HATP and their geometric counterpart.

The geometry enhances the symbolic reasoning by allowing it to use facts that depend exclusively on the geometry like "visibility" and "accessibility", also it allows to reject plans that are feasible at symbolic level, but do not have a valid geometric refinement.

World states representation

The world state is defined by the pair W s =< Ent, Spacial F acts > where

• Ent =< En 1 , En 2 , ..., En n > is set of entities. An entity is unique and it is represented by the pair En i =< SAtt i , Sc i > where SAtt i is a set of symbolic attributes and where Sc i is a reference to its geometric description. We make a difference between passive entities and active entities, called "Agents" which can perform actions and modify the state of the world. • Spacial F acts represent the spatial relations that could exist between entities. This facts are assumed to be computed by the geometric planner. An example of spacial fact is the "visibility" relation between an "agent" and an "object" in a given context.

The state of an entity is given by the current value of its symbolic attributes and of the spatial relations in which it is involved. In HATP, similarly to HTNs, we can distinguish two types of tasks: Actions and Methods. An action (also called operator) is an atomic task. A method is a higher level task that must be decomposed.

Actions

Actions are defined as a tuple A =< N ame, P ar, P rec, Ef f, C, D, Const, GF > where

• N ame defines the action name.

• P ar represents the action parameters, a non-ordered list of entities and agents. • P rec represents the action preconditions.

• Ef f represents the effects of the action on the current world state. In this model we specify two kinds of effects. The "expected effects" and the "side effects". The former ones are the effects as defined in classical HTN planning [START_REF] Ghallab | Automated Planning -theory and practice[END_REF][START_REF] Nau | Shop2: An htn planning system[END_REF] or in previous version of HATP [START_REF] Alili | A task planner for an autonomous social robot[END_REF]. The latter effects, called "side effects", are the effects that depend on the geometry of the world. For example, the motion of an agent has as expected effect on the agent's position, but, as a side effect, it can also have impact on the agent's visibility on objects and other agents in the world. • C and D represent respectively the action cost, which is computed at geometric level and the duration, which is an estimation of action duration. • Const represents a set of additional constraints on the world state that could be used to refine the action at geometric level. • GF is a Boolean flag which indicates if the action is a purely symbolic action like "speak", or if its has a geometric counterpart like "move" or "pick".

Methods

Methods are defined as a tuple M =< N ame, P ar, Goal, D, Const > where

• N ame and P ar represent respectively the name and the parameters of the method. • Goal is the goal of the method. It is condition which is associated to the method. If it holds in the current world state, the method is reduced to an empty set. • D represents a set of pairs < P i , T l i , Const i >, which define all possible decompositions for the method. For each i, if preconditions P i are verified then the partially ordered list of tasks T l i is a possible way to achieve the method. As in action Const i represents a set of constraints associated to task present in T l i . • Const: As for actions, Const represents a set of constraints associated to the current method. These constraints will propagate on the valid decompositions of the method.

The Hybrid Planning Scheme

The symbolic planner (Algorithm .1) has the world state s and the planning problem Tree as input. The algorithm starts by initializing actions' temporal projection Prj to an empty set (line 1). The main loop of the algorithm (line 2 to 13) runs until all the tree is explored. The refinement function at line 3 is responsible for the tree refinement. It decomposes all high level tasks present in the tree until the reach of a sequence of action. When an action appears in the tree, the algorithm checks its precondition (line 5). If the precondition does not hold, the algorithm makes a backtrack to the refinement step (line 3) to continue the exploration of other branches. If the precondition holds in the current world state, the algorithm calls the geometric refinement procedure to query the geometric validation of the action (line 6). If geometric refinement procedure validates the action, the algorithm updates the plan and applies the effects of the action on the current world state. On the other hand, if the geometry fails, the algorithm needs to backtrack to explore other tree branches.

Algorithm .2 describes the geometric refinement procedure. With a given world state and an action, this procedure is in charge of planning a motion to achieve the action while maintaining a continuous geometric motion plan. The algorithm first tests if there is a solution to achieve the given action with the given symbolic world state and its "internal geometric state". In case of a successful validation, the cost and facts are sent to the algorithm .1 and the geometric state is saved. In case of a failure in this step, the geometry looks for a point, in its previously planned motion plan, which will have an effect to the achievement of the current action by backtracking (line 6). If the current action can be achieved by modifying properties of the previously planned motions, the algorithm returns true and updates costs and facts.

Example

Let us consider a scenario where the Robot HRP-2 and the Human in a sitting face-to-face situation across the table (figure 4). On the table there is a bottle (B), cup (C) and coffee box (CB). It also shows the reachability of the Human and HRP2 from their current sitting positions. The yellow and blue circles show the reachabilities exclusively by left and right hands of the agent and green circle shows the regions reachable by both hands of the agent. Clearly there is a common reachability region on the table, but the cup, bottle and coffee box is not reachable to the human. The goal is to have a coffee for the human. The robot's role is to assist the human partner by making the objects accessible.

Backtracking at Geometric Level

Figure 5 shows one of the sequences of actions planned by the symbolic planner for the task of making coffee. For each node, which is basic action, the symbolic planner queries to the geometric planner about the feasibility of the action. To show the need of backtracking at the very beginning, let us assume that for validating the 2nd node, which is to put the cup on the table, geometric planner has chosen a place, which is visible and reachable for human. At this stage, it has also maintained other solutions to put the cup, while maintaining the constraints. And when it reached at 4th node to validate the action of putting the bottle, the geometric planner found that there exists no such place on the table, which is visible and reachable to human, to put the bottle. At this stage, instead of communicating the non-feasibility of the solution to the symbolic level, it will first try other possible solutions at geometric level itself. Here it will store additional constraint that the bottle should be put at a visible and reachable place to the human, and then it backtracks to previous nodes to try with other stored solutions. In the cur-rent scenario, it will backtrack to 3rd node, but there is no other pickup configuration of bottle, which could facilitate the putting of the bottle. Then it backtracks to 2nd node and it found a set of other stored solutions to put the cup. So, it selects a new solution to put the cup, so that the discovered constraint about putting the bottle also satisfied. Then it again starts validating from that node onwards. Similarly, on the later stage of validation, at node 6, human has to pick the cup, but let us assume that unaware of this task during the first iteration, the robot has decided to put the cup and bottle in such a way that human could not take the cup. In this case also a similar backtracking will occur with additional discovered constraint, that human should be able to pick the cup.

Backtracking at Symbolic level

It may be the case that even after backtracking and exploring all the possible solution at geometric level, the feasibility of a particular node of symbolic plan could not be validated. In that case, the geometric planner would inform to the symbolic planner about non-availability of solution. Then the symbolic planner could decide to explore another (sub)branch of its plan.

In our example of coffee making, if the geometry fails because of the absence of a stable position to put the bottle down, the symbolic planner may switch to an alternative solution where the robot "gives" the object directly to the human. If all actions are valid at both levels, symbolic and geometric, we can say that we have a valid plan.

Conclusion

We have devised a new and more elaborate task planning scheme, which extends the Asymov scheme and which exhibits the following features:

• The HTN planning scheme opens the possibility to provide more information about the context to the geometric planner through a set of constraints that should be taken into account at geometric level.

• A geometric reasoning systems that is able to deal with elaborate requests concerning the achievement of situations that are generally expressed at symbolic level. This has been made possible thanks to its ability to deal not only with path planning but also with spatial perspective taking, and human-robot cooperative object manipulation actions.

• A task planning scheme which provides a context for backtracking at symbolic as well as at geometric level and for various cost-based plan enhancement strategies.

Figure 1 :

 1 Figure 1: Layers of Geometric Planner

Figure 2 :

 2 Figure 2: Communication between geometrical and symbolic planner and their roles in the overall system.

Figure 3 :

 3 Figure 3: Links between the symbolic and the geometric representations of entities, actions and plans

  the Tree is explored;

Algorithm . 2 :Figure 4 :

 24 Figure 4: Scenario of Human and Robot sitting face to face

Figure 5 :

 5 Figure 5: An example of a plan for coffee making scenario.

  Planner

	!		-Action for validation
	!		-Constraints
	!
	!
	!	Generate and
	maintain symbolic ! sequences & ! select one for ! validation !	-Validity and	Validate, maintain & update the plan & solution spaces.
		Symbolic	weight of the
		Planner	action
			-World state

Acknowledgments

The research leading to these results has received funding from the European Community's Information and Communication Technologies Seventh Framework Program FP7/2007-2013 under grant agreement no 215805, the CHRIS project and from ANR Psirob AMORCES project.


Lavindra De

Silva Amit

Kumar Pandey

Rachid Alami

An Interface for Interleaved Symbolic-Geometric Planning and Backtracking

While symbolic planners work with an abstract representation of the real world, allowing plans to be constructed relatively quickly, geometric planning-although more computationally complex-is essential for building symbolic plans that actually work in the real world. To combine the two types of systems, we present in this paper a meaningful interface, and insights into a methodology for developing interwoven symbolic-geometric domains. We concretely present this "link" between the two approaches with algorithms and data structures that amount to an intermediate layer that coordinates symbolic-geometric planning. Since both planners are capable of "backtracking" at their own levels, we also investigate the issue of how to interleave their backtracking, which we do in the context of the algorithms that form the link. Finally, we present a prototype implementation of the combined system on a PR2 robot.

I. INTRODUCTION

In the past decade we have witnessed much interest in bridging the gap between symbolic and geometric planning. Some have focused on defining how geometric entities and planning capabilities can be meaningfully used within symbolic planning, and how symbolic information can be used as heuristics in geometric planning. These efforts have included defining the link between geometric and symbolic actions, specifying what information should be shared with the symbolic (resp. geometric) planner, and how this information should be used in symbolic (resp. geometric) states, actions and planning algorithms. One issue that must be addressed when combining the two systems is "backtracking," i.e. trying alternative options for choices that were already made during planning. Both systems backtrack at their own "levels" when a plan being pursued turns out to not work: the symbolic planner when some precondition is not met, and the geometric planner when a planned path includes a collision. It is therefore important to investigate the relation between symbolic and geometric backtracking in order to interleave them effectively and know when to switch between them.

In [START_REF] Karlsson | Combining task and path planning for a humanoid twoarm robotic system[END_REF], [START_REF] Lagriffoul | Constraint propagation on interval bounds for dealing with geometric backtracking[END_REF] the authors present algorithms for geometric backtracking. They extend the Justin robot with symbolicgeometric planning capabilities: for symbolic planning they use the JSHOP2 [START_REF] Nau | Totalorder planning with partially ordered subtasks[END_REF] totally-ordered HTN planner, and for geometric planning they use a specialised path planner. The authors follow the approach of keeping the symbolic state orthogonal to the geometric state: e.g. changing in the *We thank Malik Ghallab and the anonymous reviewers for their valuable feedback, and Mamoun Gharbi for Figure 2 and help with experiments. This work was conducted within the EU SAPHARI project (www.saphari.eu) funded by the E.C. division FP7-IST under contract ICT-287513. **CNRS, LAAS, 7 avenue du Colonel Roche, F-31400 Toulouse, France. ***Univ. de Toulouse, LAAS, F-31400 Toulouse, France. {ldesilva,akpandey,rachid}@laas.fr geometric state the pose of an object has no consequence on the symbolic state. In contrast, we require symbolic and geometric states to be "intertwined," which we find to be natural in some domains. To this end, we derive symbolic facts from the geometric state and use them in symbolic planning. Nevertheless, the geometric planner in [START_REF] Karlsson | Combining task and path planning for a humanoid twoarm robotic system[END_REF], [START_REF] Lagriffoul | Constraint propagation on interval bounds for dealing with geometric backtracking[END_REF] is much like ours in how it backtracks when an action being considered by the symbolic planner is not applicable, forcing the system to reconsider previous geometric choices (e.g. the pose of a cup on the table) to make the new action applicable (e.g. changing the cup's pose to make room for another one).

Since we derive and use geometric states as symbolic facts, however, we also need to address the ramifications of such backtracking on already pursued symbolic actions. Also related to our objectives is work on interfacing symbolic and geometric planning. In [START_REF] Dornhege | Integrating symbolic and geometric planning for mobile manipulation[END_REF], [START_REF] Dornhege | Semantic attachments for domain-independent planning systems[END_REF] the authors introduce Semantic Attachments, which associate selected predicates in the planning domain to external procedures, called at runtime to evaluate the predicates. In [START_REF] Dornhege | Integrating task and motion planning using semantic attachments[END_REF], Semantic Attachments are implemented using a trajectory planner that computes collision free trajectories, the existence of which causes the associated Semantic Attachments to evaluate to true, and false otherwise. Likewise, "effect applicators" in effects of actions consult the geometric planner to set certain state variables (e.g. position and orientation) in the symbolic domain. Due to such variables being deterministic, effect applicators cannot "choose" between different outcomes. In contrast, it is important in our work to give the geometric planner some leeway to make such choices. Some systems do not make a clear distinction between symbolic and geometric planning. In [START_REF] Wolfe | Combined task and motion planning for mobile manipulation[END_REF], a hierarchical planner plans all the way down to the level of geometric actions, and symbolic and geometric backtracking happens in the same "space" of solutions. Their hierarchical planner is a specialised one where primitive actions are implemented by invoking external solvers like rapidly-exploring random trees (RRTs), and states model low-level geometric details like robot joint configurations. Similarly, [START_REF] Kaelbling | Hierarchical task and motion planning in the now[END_REF], [START_REF]Unifying perception, estimation and action for mobile manipulation via belief space planning[END_REF] describes a hierarchical planner that is tightly integrated with a geometric motion planner for planning and then executing the most basic actions. In their work, however, geometric actions are executed while the plan is being constructed. This is different to the other work described above which formulates a complete plan first, before executing it. Finally, the Asymov [START_REF] Cambon | A robot task planner that merges symbolic and geometric reasoning[END_REF] system is a combined task and motion planner for problems that are difficult to solve when the symbolic planner is in control of the geometric search, e.g. in the geometric Towers of Hanoi problem that the authors present. Unlike the above approaches, in Asymov the geometric planner uses the symbolic planner-as well as the symbolic model of the domain-as a heuristic when choosing roadmaps during geometric search. Similarly, in [START_REF] Plaku | Sampling-based motion and symbolic action planning with geometric and differential constraints[END_REF] a symbolic planner guides a sampling-based motion planner, which in turn sends back utility estimates to improve the guide in the next iteration.

To summarise, the contributions of this paper are the following. First, we present a precise interface between symbolic and geometric planning. In particular, we investigate the "right" level of abstraction at which the two approaches should be combined. To this end, unlike other work, we use a geometric task planner [START_REF] Pandey | Towards planning human-robot interactive manipulation tasks: Task dependent and human oriented autonomous selection of grasp and placement[END_REF], which lets us define the interface to symbolic planning in a more meaningful way, and also give more leeway to the geometric level to make decisions. Second, we provide algorithms and data structures for an intermediate layer that coordinates symbolic and geometric backtracking and planning, as well as algorithms that highlight the characteristics of the underlying geometric task planner. Finally, we propose a methodology for developing an intertwined symbolic and geometric planning domain, including a concrete example with the PR2 robotics platform [START_REF] Wyrobek | Towards a personal robotics development platform: Rationale and design of an intrinsically safe personal robot[END_REF] in the context of Human-Robot Interaction (HRI).

II. BACKGROUND

In this paper we use a STRIPS-like planning language [START_REF] Fikes | STRIPS: A new approach to the application of theorem proving to problem solving[END_REF]. Therefore, we briefly recall some relevant STRIPS notions. A STRIPS action is a ground instance of a STRIPS operator, or for convenience, just a ground instance of the operator's name. Given an action a and a state S such that S |= pre(a) (i.e. the precondition of a holds in S), we define the result of applying a to S (with respect to a set of operators), denoted Res(a, S), as (S \ eff (a) -) ∪ eff (a) + , where eff (a) is a set of ground literals denoting the effects of a. This definition trivially extends to a sequence of actions

a 1 • . . . • a n : the result of applying a 1 • . . . • a n to a state S, denoted Res(a 1 • . . . • a n , S), is S if |a 1 • . . . • a n | = 0 and Res(a 2 • . . . • a n , Res(a 1 , S)) otherwise.
While classical planners focus on bringing about states of affairs or "goals-to-be," Hierarchical Task Network (HTN) planners focus on solving abstract tasks or "goals-to-do." In this paper we use a popular type of HTN planning called "totally-ordered" HTN (henceforth simply referred to as HTN) planning, which, more importantly than efficiency, allows calls to external functions [START_REF] Nau | SHOP: Simple hierarchical ordered planner[END_REF]-an important requirement in our work. An HTN planning problem is the 3-tuple d, S 0 , D, where d is the sequence of (primitive or abstract) tasks to solve, S 0 is an initial state as in classical planning, and D is an HTN planning domain. Specifically, a HTN planning domain is the pair D = A, M where A is a finite set of operators as before, and M is a finite set of methods. A method is a tuple consisting of the name of the method, the abstract task that the method is used to solve, a precondition specifying when the method is applicable (like an operator's precondition), and a body indicating which tasks are used to solve the task associated with the method. The method-body is a sequence of primitive and/or abstract tasks. The planning process works by selecting applicable reduction methods from M and applying them to abstract tasks in d in a depth-first manner. In each iteration this will typically result in d becoming a "more primitive" sequence of tasks. The process continues until d has only primitive tasks left. At any stage during planning if no applicable method can be found for an abstract task, the planner essentially "backtracks" and tries an alternative method for an abstract task refined earlier.

For the geometric counterpart, we adopt the approach of finding a solution in a discrete space of candidate grasps and placements [START_REF] Lagriffoul | Constraint propagation on interval bounds for dealing with geometric backtracking[END_REF], [START_REF] Pandey | Towards planning human-robot interactive manipulation tasks: Task dependent and human oriented autonomous selection of grasp and placement[END_REF] for tasks involving picking and placing. Basically, our Geometric Task Planner (GTP) iterates in a four dimensional search space, consisting of a set of agent "effort" levels, discrete grasps, object placement positions, and object placement orientations. For each object, sets of possible grasps are pre-computed and stored for the anthropomorphic hands and the robot's gripper, which are later filtered based on task requirements and the environment. The amount of "effort units" required to perform certain tasks, e.g. moving the head, extending an arm, and standing, are predefined; to this end, we have made simplifying assumptions about which tasks require less effort than others (e.g. we assume that extending an arm requires less effort than standing up). At runtime, sets of placement positions and possible orientations of objects are dynamically extracted, based on the environment, the task, and restrictions on how much effort should be put into the task. The sets are then weighted based on the environment and situation, with criteria like grasp and placement stability, feasibility of simultaneous grasps by two agents, and the agent's visibility of the object. These factors are used to build the final configuration which is then used online with an RRT based planner [START_REF] Gharbi | A sampling-based path planner for dual-arm manipulation[END_REF] to find a feasible trajectory. Computed RRTs can be reused for successive planning requests whenever feasible. We note that while the GTP is not complete in the sense of planning in a continuous search space, if there is a solution in the discrete search space of the task, it will find one.

The advantage of the GTP framework is that a variety of day-to-day tasks like showing and giving an object can be represented in terms of different constraints, based on factors like object reachability and the ability to grasp an object. A geometric solution is found using a constraint hierarchy based approach, by carefully introducing constraints successively at the different stages of planning. This facilitates the reduction of the search space successively, before introducing relatively more computationally expensive constraints.

In this paper we use the following conventions: symbol is the empty string/sequence, variables begin with upper case, and predicates and constants with lower case. We assume that symbolic and geometric states are fully observable, and allow negative literals and universal quantification in preconditions of actions and HTN methods. Finally, this paper only deals with planning: we do not interleave planning with execution.

III. A SUITABLE INTERFACE

The HTN developer interfaces with the GTP using evaluable predicates. Truth values to evaluable predicates are not assigned in the conventional way-by referring to the state of the world-but by calling an associated external procedure, which returns true or false. So every (relevant) GTP task t is associated with a non-negated evaluable predicate, denoted t ? , in the HTN domain (e.g. GTP task SHOW(O, H) is associated with evaluable predicate show(O, H) ? for some object O and human H), which basically evaluates to true if t has a GTP solution and false otherwise. Whenever such an evaluable predicate is mentioned in the precondition of an operator (resp. action), we call it a Geometric-Symbolic (GS) operator (resp. action).

Conceptually, a GTP task t is also associated with an add list function, denoted t + , and a delete list function, denoted t -, which are the (possibly empty) add and delete lists for t computed by the GTP, based basically on the world resulting from the solution that was found for t on calling evaluable predicate t ? . 1 For example, for GTP task

SHOW(o 1 , h 1 ), show(o 1 , h 1 ) + might return the set {visible(o 1 , h 1 ), reachable(o 1 , h 1 )} and show(o 1 , h 1 ) -the set {visible(o 3 , h 1 ), reachable(o 3 , h 1 )}: that is, object o 1 is
both visible to human h 1 and reachable to h 1 , but object o 3 is neither visible nor reachable to h 1 . Such "side effects" can only accurately be inferred at runtime, from the most recent state of the geometric 3D world. Hence, the effects of a GS operator are the combination of its add and delete lists with its "dynamic" add and delete lists, obtained via the add and delete list functions.

It is sometimes useful to share certain symbolic predicates between the HTN planner and the GTP. A "shared predicate" (or "shared literal") is an abstract relation between objects that needs to be modelled in the HTN domain, but is based on geometrical properties and consequently modelled more accurately by the GTP. For example, predicate on(b 1 , b 2 ) in the HTN domain is an abstract representation specifying that book b 1 is on top of b 2 , which in the GTP amounts to two rectangular objects in 3D space conforming to certain constraints like one object's side touching the other's. Likewise, in the HTN domain visible(o, h) specifies that object o is visible to human h, which is computed by the GTP based on whether the human's field of view in a 3D world overlaps with the object [START_REF] Pandey | Mightability maps: A perceptual level decisional framework for co-operative and competitive human-robot interaction[END_REF]. There are, of course, also symbolic predicates that are specific to the HTN planner (such as full(c), breakable(c), and emailed(p) for some cup c and person p) which are not modelled by the GTP. Furthermore, low-level predicates specific to the GTP, e.g. the exact position of an object in terms of (x, y, z) coordinates, is often too much detail for the HTN domain.

It is worth mentioning that checking if a symbolic predicate holds in a geometric world state requires anchoring [START_REF] Coradeschi | An introduction to the anchoring problem[END_REF] the predicate (e.g. visible(o, h) for some object o and human h) to the right geometrical attributes (e.g. position, orientation and field of view). We refer the reader to [START_REF] Pandey | Visuo-spatial ability, effort and affordance analyses: Towards practical realization of building blocks for robots complex socio-cognitive behaviors[END_REF], [START_REF] Pandey | Mightability maps: A perceptual level decisional framework for co-operative and competitive human-robot interaction[END_REF] for a detailed account of how we address this problem. In this paper we ignore the issue of anchoring a ground literal 1 Add and delete list functions are only conceptual entities. Later, in the algorithms, we present a slightly different representation.

to its corresponding geometrical attributes, and assume that we can simply check if a ground literal holds in a geometric world state.

With sharing symbolic predicates between the geometric and symbolic planners comes the need to manage consistency in the two world representations. Specifically, we may reach a point during symbolic-geometric planning where there is an inconsistency between shared (ground) literals implied by the GTP world state and those actually in the HTN state. This could happen, for instance, if the HTN developer incorrectly predicts, while writing the domain, the side effects of the SHOW(o 1 , h 1 ) action mentioned before. We address this issue by disallowing the HTN developer from mentioning shared predicates in add and delete lists. Specifically, such predicates can only be added to and removed from the HTN state via add list and delete list functions. Likewise, when constructing the HTN initial state, the GTP must be consulted to get the shared (ground) predicates that hold in the initial GTP state.

We will now be precise about how we interface the geometric planner to the symbolic. A GS operator maps to exactly one GTP task: only one evaluable predicate that corresponds to a GTP task can appear in an operator's precondition. Intuitively, this means that the lowest "level of abstraction" in an HTN domain-i.e. primitive tasks-is the highest "level of abstraction" in the GTP domain-i.e. compound GTP tasks. This can always be accounted for, as a GTP task can be as "compound" as necessary, where a compound GTP task encompasses multiple, more specific ones that are too "low level" to be included in the HTN domain. For example, consider the rightmost (fourth) column of Figure 2 which shows the grasp and placement actions that the four "compound" GTP tasks in the third column refine into. We could imagine a domain where these actions are encapsulated into one compound PICKMAKEACCESSIBLE(O, H) task (for object O and human H), instead of the two tasks PICK(O) and MAKEACC(O, H). This will let the GTP backtrack from PLACE(O) to GRASP(O), facilitating early failure detection in HTN planning-i.e. PICKMAKEACCESSIBLE(O, H) will have no solution when the "future" GTP task PLACE(O), due to be tried later by the HTN planner, is predicted by the GTP to be impossible even with different solutions for PICK(O). Such encapsulation can also minimise GTP backtracking by, from the outset, planning with respect to definite future GTP tasks (e.g. planning the grasp with respect to the placement).

IV. A SYMBOLIC-GEOMETRIC PLANNING EXAMPLE

In this section we detail a concrete domain that illustrates how symbolic and geometric planning is interfaced and combined. Particularly, we show how HTN and GTP backtracking is interleaved, and shed light on a methodology for building symbolic-geometric planning domains. Our example is a PR2 robot working as a library receptionist. We focus here on the important aspects of this domain and refer the reader to [START_REF] Silva | Towards combining HTN planning and geometric task planning[END_REF] for more details.

Members of the library can use their membership ID to do things like reserve books online and top up their library credit. The ID corresponds to information including the member's name, books reserved, borrowed, and remaining credit. Reserved books need to be collected in person from the library. After an online reservation, (human) librarians find the books and make them accessible to the PR2 on a shelf adjacent to it; basically, an object is accessible to an agent if it is both visible, and reachable without needing to navigate from the current position. The HTN hierarchy is shown in Figure 1 and detailed in Table I. The top-level HTN task MANAGEORDER(M ) for member M has one method (m 1 ) with two subtasks: LEND(M ) and TAKEPAYMENT(M ). The first task has methods m 2 , m 3 , and m 4 and these are "ordered," i.e. tried in that order. Method m 2 trivially succeeds if there are no (more) books held by the member. If it is not applicable, m 3 is tried, which has the following actions: pick from the adjacent shelf a book reserved (held) by the member, speak out the title, make it accessible to him/her on the desk, do some bookkeeping-e.g. send the current total to the Point-of-Sale (POS) machine-and then recursively call LEND(M ).

(M ) m1 held(B, M ) LEND(M ) • TAKEPAYMENT(M ) LEND(M ) m2 ∀B, ¬held(B, M ) m3 held(B, M ) ∧ title(B, T ) PICK(B) • SAY(T ) • MAKEBKACC(B, M ) • ADD(B, M ) • LEND(M ) m4 held(B, M ) ∧ title(B, T ) ∧ ¬hvy(B) DISPLAY(B, T, M ) • GIVEBK(B, M ) • WAITTAKE(B, M ) • ADD(B, M ) • LEND(M ) DISPLAY(B, T, M ) m5 true PICK(B) • SHOW(B, M ) • SAY(T ) TAKEPAYMENT(M ) m6 nLnt(M, N ) DEBITACC(M, N * c) m7 nLnt(M, N ) ∧ cr(M, C) ∧ (C < N * c) PLACEPOSM() • PUTAWAYPOSM(M ) • EMAIL(M ) PLACEPOSM() m8 reachable(posm, pr2) PICK(posm) • SAY(swipe) • PUTON(posm, stnd) m9 true NAV(posm) • PICK(posm) • NAV(desk) • SAY(swipe) • PUTON(posm, stnd) PUTAWAYPOSM(M ) m10 true SAY(thank) • PICK(posm) • PUTAWAY(posm, M ) SAY(T ) true {spoke (
Method m 4 starts with an HTN abstract task to display a book, which refines into the three steps related to showing a book to the person. The abstract task is followed by: giving the book to the person;2 waiting for it to be taken, which is a non-GS action that uses the gripper angle and force sensors to check if an object is in the gripper; the bookkeeping action; and finally a recursive call to LEND(M ). Note that a book is given only if it is deemed light enough to be directly taken from the gripper, and that by forcing an ordering between m 3 and m 4 we are encoding a preference for placing a book on the table over handing it (directly) to the member, allowing the member to pick up the book and put it in a bag at his/her own pace. Note also that if a book is heavy (hvy(B)) it could be made accessible rather than given directly.

The TAKEPAYMENT(M ) task of m 1 is associated with methods m 6 and m 7 . Method m 6 involves debiting the member according to the number of books lent nLnt (all books have the same cost c), provided there is enough credit C in the member's account. If not, the member must pay by debit/credit card (m 7 ). The PLACEPOSM() task is associated with two ordered methods for giving the POS machine (posm): if it is reachable, it is picked up and put onto the stand (stnd) after asking the user to swipe the card and enter the PIN, but if not-presumably because it is with another receptionist-the PR2 must navigate to pick it up and bring it back. The PUTAWAYPOSM(M ) task includes actions to thank the person and to move the machine away from the person's reach, and EMAIL(M ) emails the member with details including the books that were lent.

The example serves to highlight some key characteristics. First, there is some interesting interleaving of HTN planning and geometric task planning that is possible with the domain described. Suppose that the library reception desk is small and somewhat cluttered with boxes, and that a member has reserved two big books b 1 and b 2 . While there is enough space on the table to make one of them accessible (to the member), there is not enough space to make them both accessible, nor to make one accessible but give the other (directly), as the books are so big that they block the path to the member. Figure 2 illustrates how the combined planning process might work with such a setup. In the figure b 1 is successfully picked and made accessible (i.e. the GTP tasks corresponding to the PICK(b 1 ) and MAKEBKACC(b 1 , m) GS actions are successfully planned), and LEND(M ) is recursively called. However, because of our setup, the attempt to make book b 2 accessible will fail. In our current approach, at this point the GTP must backtrack to reconsider its choicesfirst for PICK(b 2 ), and if that fails, for MAKEBKACC(b 1 , m), and if that also fails, for PICK(b 1 ). Since the GTP will still not find a way to change the pose of the first book so as to make the second accessible, the system will then resort to HTN backtracking, which will choose the alternative method m 4 to give b 2 directly to the person. 3 According to our initial setup, this will also fail even after the GTP tries to change the pose of b 1 . The HTN planner will then backtrack once again (not shown), this time right to the beginning, and perhaps choose method m 4 , 4 to give b 1 directly to the person; if this happens the planner will then successfully make b 2 accessible and continue planning.

The second characteristic that the domain depicted in Figure 1 highlights is "GTP influenced" HTN preconditions. In Table I, subsets of preconditions of the GIVEBK(B, M ) and MAKEBKACC(B, M ) operators are duplicated in the HTN methods where they occur. This is solely for efficiency: to ensure that the preceding GS actions (e.g. PICK(B)) in those methods, which are costly to plan, are not planned unnecessarily, i.e. if the preconditions of GIVEBK(B, M ) and MAKEBKACC(B, M ) are guaranteed to eventually not hold. So intuitively, for any GS action occurring in the method body, it makes sense to duplicate in the method- 3 we assume here that the book is light enough to be handed to the person 4 Method m 3 could also be chosen here to make book b 2 accessible. precondition the subset of the action's precondition5 that does not "depend" on-that has no causal links [START_REF] Ghallab | Automated Planning: Theory and Practice[END_REF] with-any preceding action in the body (e.g. the held(B, M ) literal in the precondition of MAKEBKACC(B, M ) has no causal link with any of its preceding actions in the body). We could also order methods based on their estimated "computational cost." For example, by forcing method m 8 to be tried before m 9 we avoid unnecessarily planning to navigate-when the POS machine is likely reachable-as generally planning to navigate and pick up an object is more computationally expensive than planning to simply pick it up. 6 Interestingly, the notion of a "computationally costly" action here is different to the standard notion of "action cost," which is the estimated cost of executing the action. Finally, note that the reachable(O, A) predicate in the precondition of m 8 is a weaker notion than "real" reachability: when agent a can really reach object o, i.e. a collision-free trajectory exists from the arm of a to o, then reachable(o, a) holds, but the converse is not necessarily true; the predicate is derived from the 3D world with a heuristic based on the area covered on extending the robot's arm with respect to all its degrees of freedom. Hence, the weak notion will clearly not hold if there is an obstacle blocking the path from the robot's arm to where the object is located. With such a "lazy predicate" we can quickly determine if an object is definitely unreachable and also if an object is likely to be reachable, e.g. before testing putOn(posm, stnd) ? to see if it is really the case. In contrast, the visible(O, A) shared predicate and others like on(O, O 2 ) and in(O, O 2 ) (for an agent A and objects O, O 2 ) only depend on the current geometric state-not on the existence of a trajectory-and thereby accurately correspond to their "real" notions.

V. ALGORITHMS FOR SYMBOLIC-GEOMETRIC PLANNING

We now present the Algorithms and data structures for an "intermediate layer" that coordinates HTN and GTP backtracking and planning, and a skeleton of the underlying GTP algorithm with certain features highlighted. We begin by illustrating some of the main ideas with an example. Consider a similar HTN domain to Figure 1 where the PR2 first makes reserved books accessible to the member (to show what he/she has borrowed), and then the POS machine if it is not already accessible, and finally gives the books (directly) to the member after asking him/her to insert the card and enter the PIN. To avoid any confusion when the user is asked to enter the PIN, the PR2, just before asking, hides from the member's view any other POS machines lying around on the table that are not involved in the transaction. Asking the member to enter the PIN is similar to the (non-GS) SAY(swipe) action from Figure 1 except for an additional requirement to have only one POS machine visible to the member-all others must be hidden. Now suppose that initially two POS machines posm 1 , posm 2 were accessible to a member who had reserved two books b 1 , b 2 . Suppose also that: (i) MAKEBKACC(b 1 , m) was successful, but with the side effect where posm 2 , the one not used for the transaction, became hidden from the member; (ii) MAKEBKACC(b 2 , m) was successful without leading to anything being hidden from the member; and finally, (iii) SAY(swipe) was successful because literals visible(posm 1 , m) and ¬visible(posm 2 , m) were both true. Now, if for some reason GTP backtracking is triggered at some later point and the GTP picks different solutions for MAKEACC(b 2 , m) and/or MAKEACC(b 1 , m), the GTP must ensure that those two literals will still hold: it must "protect" them when backtracking. Not doing this may render current HTN plan invalid. So if we use sequence L to keep track of the shared literals to protect per action in the HTN partial plan, at this point in our example we have L = ∅ • ∅ • {visible(posm 1 , m), ¬visible(posm 2 , m)}. Consequently, the final state resulting from consecutively applying any new solutions for the first two actions' GTP tasks must be consistent with the literals in the last set in L. In the algorithms we use Res(σ, s) and Res( σ, s) to denote, like in classical planning, the GTP world state resulting from applying respectively the GTP solution σ and the sequence of GTP solutions σ to the GTP world state s. 7 We also keep the notion of a GTP (world) state and GTP solution abstract. Basically, a GTP state is a 3D world model with positions and configurations of all objects, and a solution σ is sometimes simply a trajectory, but in general includes additional domain-specific information like the effort required to perform the task and symbolic information like the relative location of a manipulated object. We refer the reader to [START_REF] Pandey | Towards planning human-robot interactive manipulation tasks: Task dependent and human oriented autonomous selection of grasp and placement[END_REF] for more details. 7 In practice, we do not explicitly compute Res(σ, s) as the GTP stores the end state of a solution found.

Algorithm 1 Evaluate Symbolic Predicate (GTP Task) if len < | t| then // backtracked symbolically 5:

t ← (len > 0 ? t1 • . . . • t len : )

6: L ← (len > 0 ? L1 • . . . • L len • ∅ : ∅) 7:
ans ← PLANTASK( t • t, L)

return (ans = fail ? false : true)

Before planning starts, the HTN initial state must be made consistent with that of the GTP initial state. This is done using function GETSYMFACTS(), which will compute ground literals from the current geometric state, e.g. which objects are visible and reachable to which agents [START_REF] Pandey | Visuo-spatial ability, effort and affordance analyses: Towards practical realization of building blocks for robots complex socio-cognitive behaviors[END_REF], [START_REF] Pandey | Mightability maps: A perceptual level decisional framework for co-operative and competitive human-robot interaction[END_REF], and which objects are on top of which other objects [START_REF] Lemaignan | Bridges between the Methodological and Practical Work of the Robotics and Cognitive Systems Communities -From Sensors to Concepts[END_REF]. Moreover, before planning starts the following global variables are initialised: the sequence t (initially ) of GTP tasks successfully planned so far; the sequence L (initially ∅) of sets of literals to protect; the current GTP task t cur (initially ) for which a GTP solution is being sought; its corresponding GTP solution σ cur (initially ); solution sequence σ (initially ); and initial GTP world state s 0 , where the last three variables are only visible to the GTP.

Given a sequence of GTP tasks t and a GTP solution sequence σ for it from world state s, 8 we say that σ protects a set of ground literals L from s, denoted P r( σ, L, s), if all l ∈ L hold in Res( σ, s). As illustrated in the previous example, we maintain the sequence of sets of ground literals L = L 1 • . . . • L n that need to be protected by new GTP solutions for the currently pursued sequence t of GTP tasks, and then try to ensure, given a prefix t 1 • . . . • t i of t, that some solution sequence σ 1 • . . .

• σ i for t 1 • . . . • t i protects L i+1 ∈
L from the initial GTP state. Algorithm 1 is the function called to evaluate predicates associated with GTP tasks. Indeed, for efficiency, this function should be called last while evaluating preconditions to ensure it is not called unnecessarily, i.e. when the rest of the precondition does not hold. In this algorithm, to detect if backtracking has occurred at the HTN level that warrants reconsidering certain GTP tasks in the postfix of t, the length of the currently pursued HTN plan-actually, its subsequence containing GS actions-is checked: if less than the length of the current sequence t of GTP tasks then the algorithm explicitly "backtracks" by trimming the sequence accordingly. To understand how this works, consider Figure 2. Suppose again that we have a member m who has reserved two books b 1 , b 2 , and that the HTN planner chose method m 3 (for b 1 ) followed by m 3 again, to solve task LEND(m). Now, if the precondition of MAKEBKACC(b 2 , m) is not applicable, the HTN planner must "discard" the second method m 3 , and then continue perhaps by checking the precondition of PICK(b 2 ) of task DISPLAY(B, T, M ). So the length we are interested in is two, as the two GS actions from the initially 8 that is, σ 1 ∈ σ is the solution for t 1 ∈ t from s; σ 2 ∈ σ for t 2 ∈ t from s 1 = Res(σ 1 , s); σ 3 ∈ σ for t 3 ∈ t from Res(σ 2 , s 1 ); and so on Algorithm 2 Protect Ground Literals and Apply GTP Task Let L ⊆ L be the set of shared literals in L return ( σcur = fail ? false : true)

3: L ← L1 • . . . • L | t| • (L | t|+1 ∪ L ),
selected method m 3 are still in the partial plan. 9 After line 7 we assume a cache is kept of previous solutions for PLANTASK( t•t, L), to avoid recomputing a plan for the same input on repeated calls to Algorithm 1. This is possible, for example, if the HTN planner needs to check multiple ground instances of a precondition before finding one that holds in the current state.

The HTN planner calls Algorithm 2 when an action's effects need to be applied to the state of the world. The input is the set of ground literals that was checked in the precondition, and it returns the set of shared (ground) literals (both positive and negative) resulting from executing GTP task t cur .

Algorithms 3 and 4 (PTR is short for PLANTASKRE-CURSE) depict the basic geometric task planning algorithm. They illustrate how the GTP backtracks on choices and how literals are protected during geometric planning. Indeed, such a basic depth-first search algorithm will need to be supported by efficient heuristics to be practical: some promising steps in this direction are proposed in [START_REF] Lagriffoul | Constraint propagation on interval bounds for dealing with geometric backtracking[END_REF].

Algorithm 3 simply truncates solution sequence σ if its corresponding sequence of GTP tasks t was already truncated in Algorithm 1, and then calls Algorithm 4. Algorithm 4 is basically backward state space search from the new GTP task that needs to be planned to the last GTP task that was already planned, and eventually to the first GTP task that was already planned. Lines 5 and 6 try to keep the largest possible prefix of the previously planned GTP solution sequence σ. Line 8 ensures that the relevant literals are protected when looking for a new solution for t 1 .

VI. IMPLEMENTATION AND EFFICIENCY ISSUES

For the integration we use the HATP [START_REF] Alili | A task planner for an autonomous social robot[END_REF] HTN planner and our GTP [START_REF] Pandey | Towards planning human-robot interactive manipulation tasks: Task dependent and human oriented autonomous selection of grasp and placement[END_REF], which have both been used extensively (albeit separately) in the LAAS architecture [START_REF] Fleury | Genom: A tool for the specification and the implementation of operating modules in a distributed robot architecture[END_REF] for HRI experiments. We will start with a brief overview of the LAAS architecture. The PR2 uses the Move3D [START_REF] Simeon | Move3d: a generic platform for path planning[END_REF] integrated planning and visualisation platform for representing the real 9 This length could be maintained straightforwardly in the HTN domain without any modifications to the planner, and included as an extra parameter in the evaluable predicate.

Algorithm 4 Geometric Task Planning if σ sol = fail then return σ1 • σ sol 8:

if σ for t1 from s such that P r(σ, L2, s) then return fail return fail world in 3D and for doing geometric task planning with it. Through various sensors the PR2 can also update the 3D world state in real-time. To this end, a tag-based stereovision system is used for object identification and localisation, and a Kinect (Microsoft) sensor for localising and tracking the human. With our geometric tools we not only anchor a symbolic fact, but also compute the cost (in terms of effort) associated with the fact [START_REF] Pandey | Visuo-spatial ability, effort and affordance analyses: Towards practical realization of building blocks for robots complex socio-cognitive behaviors[END_REF], [START_REF] Pandey | Mightability maps: A perceptual level decisional framework for co-operative and competitive human-robot interaction[END_REF].

Although we keep the symbolic-geometric planning separate from execution, we have implemented the mechanisms to execute on the real PR2 platform the plans produced. We have also implemented the HTN domain and all GTP tasks in Figure 1, except for NAV(Obj) which requires further work, and sufficiently implemented the algorithms presented in this paper to gain some preliminary insights. [START_REF] Pandey | Mightability maps: A perceptual level decisional framework for co-operative and competitive human-robot interaction[END_REF], and the others using domainspecific heuristics. We found that in practice, computing visibility and reachability in a standard domain with 3 agents and 6 objects takes approximately 0.2 seconds on average, which is negligible compared to the time it takes to do geometric backtracking [START_REF] Lagriffoul | Constraint propagation on interval bounds for dealing with geometric backtracking[END_REF]. We refer the reader to [START_REF] Silva | Towards combining HTN planning and geometric task planning[END_REF] for some preliminary results on the runtime performance of our symbolic-geometric planning system.

In Figure 3, (a) to (d) show in Move3D a part of the backtracking depicted in Figure 2, and (e) to (g) summarises the visible(O, A) and reachable(O, A) shared literals involving the human, for each of the Move3D states, with (f) corresponding to both (b) and (c). Sub-figure (a) shows a grey and white book on the shelf adjacent to the PR2, and a person ("HUMAN") at the reception counter; (b) shows the PR2 making the grey book ("Grey") accessible on a box on the desk; (c) shows how it is later moved, after backtracking, to make room for the white book ("White"); and (d) shows the PR2 placing the white book on the box. Sub-figure (e) shows that the grey book is (easily) visible ("Vis") to the human, i.e. with an effort ("E") of either 0 or 1, but that it cannot be (easily) reached ("Reach") by himthat requires an effort greater than 1. Columns (f) and (g) are self explanatory. Although not shown in the figure, both books were always visible and reachable to the PR2 with E=1.

VII. DISCUSSION AND CONCLUSION

In this paper, we have investigated issues related to linking geometric reasoning with symbolic planning. To this end, we focussed on defining a clear interface between the two planners, in particular, defining how geometric entities, like compound tasks and 3D world states, can be meaningfully included in HTN planning. This led to a first attempt at a methodology for developing symbolic-geometric planning domains. We showed with a non-trivial example how carefully written HTN domains coupled with "lazy" conditions could improve performance. We discussed an approach to interleaved backtracking and provided algorithms for it, together with algorithms that link the two planners. These included a way to "protect" shared literals, which may otherwise be negated while backtracking in the GTP, possibly making the pursued HTN plan invalid. Finally, we discussed a prototype that implements some of the useful bits of the combined system, and presented a basic backtracking scenario along with the shared literals computed at each step.

We note that while our aim is to preserve completeness as much as possible, and evaluable predicates corresponding to GTP tasks trigger GTP backtracking to this end, a shared literal (e.g. visible(b 1 , h 1 )) mentioned in an HTN precondition will not trigger GTP backtracking, resulting in the possible loss of solutions: the literal might just not hold because of a particular GTP solution choice made earlier (e.g. the pose of book b 1 with respect to human h 1 ). To address this, we are working on an alternative combined planning strategy for domains where completeness is important. Intuitively, in our new approach the HTN planner backtracks to ask the GTP to find alternative solutions for relevant GTP tasks. To this end, certain GS operator instances essentially map to different GTP solutions for the operators' corresponding GTP tasks.

3 AND 4 ANDFig. 1 :

 341 Fig.1: The part of the HTN domain that handles online book reservations. Solid rectangles are HTN abstract tasks; rounded rectangles methods (where the incoming vertex is the task that the method solves, and outgoing vertices are the tasks in the method's body); and dashed rectangles actions. Standard HTN actions are in bold and GS actions are underlined.ACTION/HTN TASK M PRECONDITION METHOD-BODY/ACTION-EFFECTS MANAGEORDER(M ) m1 held(B, M ) LEND(M ) • TAKEPAYMENT(M ) LEND(M ) m2 ∀B, ¬held(B, M ) m3 held(B, M ) ∧ title(B, T ) PICK(B) • SAY(T ) • MAKEBKACC(B, M ) • ADD(B, M ) • LEND(M ) m4 held(B, M ) ∧ title(B, T ) ∧ ¬hvy(B) DISPLAY(B, T, M ) • GIVEBK(B, M ) • WAITTAKE(B, M ) • ADD(B, M ) • LEND(M ) DISPLAY(B, T, M ) m5 true PICK(B) • SHOW(B, M ) • SAY(T ) TAKEPAYMENT(M ) m6 nLnt(M, N ) DEBITACC(M, N * c) m7 nLnt(M, N ) ∧ cr(M, C) ∧ (C < N * c) PLACEPOSM() • PUTAWAYPOSM(M ) • EMAIL(M )

  T )} MAKEBKACC(B, M ) held(B, M ) ∧ makeAcc(B, M ) ? {¬held(B, M ), lent(B, M )}, makeAcc(B, M ) - , makeAcc(B, M ) + WAITTAKE(B, M ) held(B, M ) ∧ gave(B, M ) {¬held(B, M ), ¬gave(B, M ), lent(B, M )} ADD(B, M ) lent(B, M ) ∧ nLnt(M, N ) {¬nLnt(M, N ), nLnt(M, N + 1)} GIVEBK(B, M ) held(B, M ) ∧ give(B, M ) ? ∧ ¬hvy(B) {gave(B, M )}, give(B, M ) - , give(B, M ) + PICK(O) pick(O) ? pick(O) - , pick(O) + DEBITACC(M, Cost) cr(M, C) ∧ (C ≥ Cost) {¬cr(M, C), cr(M, C -Cost)} EMAIL(M ) lent(B, M ) {emailed(M )}

Fig. 2 :

 2 Fig. 2: Interleaved GTP and HTN backtracking and planning.

1 : 2 :

 12 function TESTEVALPRED(t, len) Let t = t1 • . . . • tn and L = L1 • . . .

1 :

 1 function PROTECTANDAPPLY(L) 2:

9 :Nondeterministically choose such a σ 10 : 11 :

 91011 σ sol ← PTR(Res(σ, s), t2 • . . . • tn, , L2 • . . . • Ln) if σ sol = fail then return σ • σ sol 12:

Fig. 3 :

 3 Fig. 3: Screenshots showing backtracking and facts produced.

TABLE I :

 I The table for Figure1. The top half (above the thick line) are methods (M) and the bottom half are operators. For legibility, empty sets have been omitted from the table. Omitted operators are defined similarly to PICK(O).

  where L = L1 • . . . • Ln

	4: 5: 6: 7:	if t ? cur ∈ L then t ← t • tcur L ← L • ∅ APPLYLASTTASK()	// applying effects of a GS action
	8:	return GETSYMFACTS()
	9: Algorithm 3 Geometric Task Planning (Top-Level) return ∅
	1: function PLANTASK( t,	L)
	2: 3: 4: 5:	Let σ ← (| t| > 1 ? σ1 • . . . • σ | t|-1 : ) σ = σ1 • . . . • σn σ, L) σcur ← PTR(s0, t,

  L1 • . . . • Ln and σ = σ1 • . . . • σn-1 sol ← PTR(Res(σ1, s), t2 • . . . • tn, σ2 • . . . • σn-1, L2 • . . . • Ln)

	1: function PTR(s, t, σ,	L)
	2: 3: L = 4: Let t = t1 • . . . • tn Let if | t| = 0 then return 5: if | σ| > 0 then 6:	// tn is the new GTP task // try stored solution
	7:

σ

We could also imagine more generic GIVEBK(B, M ) and MAKEBKACC(B, M ) actions that can handle any object type or give and make books accessible for reasons other than lending.

excluding the evaluable predicate linked to a GTP task

If there are abstract tasks in the method body, then the GS actions they might refine into will also need to be taken into account, and this process repeated until leaf-level methods (those that do not mention any abstract tasks in their bodies) are reached, as done for instance in[START_REF] Clement | Theory for coordinating concurrent hierarchical planning agents using summary information[END_REF] to "summarise" HTN hierarchies.


Ali Mokh
email: ali.mokh@insa-rennes.fr

Mohamed Shehata
email: mohamad.shehata@insa-rennes.fr

Matthieu Crussière
email: mattieu.crussiere@insa-rennes.fr

Maryline Hélard
email: maryline.helard@insa-rennes.fr

Analytical Performance of Hybrid Beam Index Modulation

Keywords: Beam Index Modulation, Zero Forcing, Hybrid Beamforming, Analog Beamforming, mmWave

come

I. INTRODUCTION

Increasing data rates, the spectral efficiency (SE) and the energy efficiency (EE) are considered as the main targets of future wireless networks. This can be achieved by different key enablers such as massive multiple-input multiple-output (MIMO) system architecture and millimeter wave (mmWave) communications. Hardware complexity however remains a major issue to address for the practical implementation of such solutions.

Hybrid beamforming [1] has rapidly emerged as a promising solution to decrease the massive MIMO hardware complexity by utilizing less radio frequency (RF) chains than the number of antenna elements. It has even been shown that employing hybrid beamforming achieves close SE performance compared to the full digital solutions in sparse channels as for example in mmWave systems [1].

Complementary to hybrid beamforming approaches, Index Modulation (IM) has recently been proposed as a low complexityenergy efficient technique for next generation wireless communication systems [START_REF] Basar | Index modulation techniques for next-generation wireless networks[END_REF]. IM is the generalization of the ON OFF keying concept applied to a certain dimension, such as frequency (sub-carrier) or space (antenna) for instance.

Specifically, Spatial Modulation (SM) has become a popular index modulation technique applied along the spatial axis, where the index of the transmit or receive antennas codes the useful information [START_REF] Di Renzo | Spatial modulation for generalized mimo: Challenges, opportunities, and implementation[END_REF]- [START_REF] Mokh | Extended receive spatial modulation mimo scheme for higher spectral efficiency[END_REF]. With the emerging mmWave systems, SM has recently been adapted to sparse scattering propagation conditions. As an example, SM dealing with pure Line of Sight (LoS) channels has been studied in [START_REF] Liu | Line-of-sight spatial modulation for indoor mmwave communication at 60 ghz[END_REF], where analog beamforming is implemented at the transmitter.

Another IM technique applied to the spatial domain and referred to as Beam Index Modulation (BIM) has very recently been proposed [START_REF] Ding | Beam index modulation wireless communication with analog beamforming[END_REF]. The idea behind BIM is to exploit the multiple path scattering in a given channel by mapping the information bits onto the indexes of the beams associated to the propagation paths that can be established between the transmitter and the receiver. In other words, a given M-ary symbol is transmitted when activating one given propagation path out of M possible ones. Clearly, path activation relies on beamforming capacilities at both the transmitter and the receiver. In [START_REF] Ding | Beam index modulation wireless communication with analog beamforming[END_REF], the authors restrained the study to the simple case of analog beamforming, thus suffering from potential inter-beam interference.

In this letter, we extend the BIM approach by making use of a hybrid beamforming architecture instead of the pure analog one, where the additional digital precoder aims at mitigating the inter-beam interference. We provide analytical derivations for the SE and Bit Error Probability (BEP ) expressions of the proposed hybrid-BIM system when applying the zero forcing (ZF) criterion to the digital precoder. We then highlight the enhancement provided by the hybrid-BIM approach compared to the pure analog-BIM one.

II. SYSTEM MODEL

In this section, we set up the complete model for a communication system utilizing the BIM scheme with hybrid beamforming.

A. MIMO System Model with hybrid beamforming

A MIMO system equipped with N t transmit antennas and N r receive antennas is considered and can be modeled as follows:

y =F r H∆F t Wx s +F r n, (1)
where H ∈ C Nr×Nt is the MIMO flat fading channel matrix with elements h j,i representing the complex channel gain between the ith transmit antenna, denoted T i , and the jth receive antenna, denoted R j . s∈C Nt×1 is the vector of samples transmitted through the N t transmit antennas. y ∈ C Nr×1 is the vector of the received signals.

F t ∈C Nt×Lt is the analog beamformer at the transmitter, such that L t is the number of RF chains at the transmitter. Throughout this letter we assume that the number of transmit and receive RF chains equals the number of the selected paths (transmit beams) L t = L r = N p . W ∈C Lt×Np is the digital ZF precoder used to annihilate the interbeam interference. F r ∈C Np×Nr is the analog beam combiner at the receiver. n ∈ C Nr×1 is the vector of additive white Gaussian noise (AWGN) samples η j such that η j ∼CN (0,σ 2 n ) given that σ 2 n represents the noise variance. Finally, ∆∈R Np×Np is a diagonal scaling matrix of entries δ j ,j ∈ [1,N p ] which ensures the normalization of the transmitted power after hybrid beamforming. We hence have:

δ j = 1 Tr (F t Wx j ) H F t Wx j . (2)

B. Beam Index Modulation

The spatial symbol x k where k is the index of the beam that should be targeted according to the spatial mapping, are formed such that the entries x k (j) of x k verify x k (j)=1 for j =k and x k (j)=0, ∀j =k. A group of m = log 2 (N p ) bits, where N p is the number of paths (transmit-receive beam pairs), are mapped onto a spatial symbol

x k ∈ N Np×1 written as x k = 0 ... 1 k-thposition ... 0 T
given that k represents the targeted beam. Then, the analog and digital beamforming matrices F t W transforms the vector of spatial symbols x into the vector of transmitted samples s∈C Nt×1 . At the receiver side, the BIM receiver has to detect the targeted beam using analog beam combining. The block diagram of the analog beamforming BIM system is depicted in Fig. 1.

III. CHANNEL MODEL AND BEAMFORMING

Throughout this letter, we use the sparse geometric channel model detailed in [START_REF] Alkhateeb | Limited Feedback Hybrid Precoding for Multi-User Millimeter Wave Systems[END_REF]. Then, the active path selection is done at both the transmitter and the receiver through beam training and beam alignment steps [START_REF] Tsang | Coding the beams: Improving beamforming training in mmwave communication system[END_REF]. The channel matrix for each path (transmit-receive beam pair) p is represented as follows:

H p = N t N r α p a r (θ p )a H t (φ p ), (3)
where α p is the complex amplitude of propagation path p which is one of the N p chosen, such that E[|α p | 2 ]= α. φ p represents the Angle of Departure (AoD) for path p, such that φ p ∈[0,2π]. θ p represents the Angle of Arrival (AoA) for path p, such that θ p ∈[0,2π]. Finally, a t (φ p ) and a r (θ p ) are the transmit array and receive array steering vectors respectively, which depend on the array geometry. In this letter, we use Uniform Linear Array (ULA) for transmit and receive arrays. Henceforth, the steering vectors a t (φ p ) and a r (θ p ) are defined as:

a t (φ p )= 1 √ N t [1,e jγ(φp) ,...,e j(Nt-1)γ(φp) ] T , (4)
a r (θ p )= 1 √ N r [1,e jζ(θp) ,...,e j(Nr-1)ζ(θp) ] T , (5)
such that γ(φ p ) is represented as γ(φ p ) = 2π λ d t sin(φ p ) and ζ(θ p ) is given as ζ(θ p ) = 2π λ d r sin(θ p )
, where λ is the wavelength of the signal, and d t and d r are the inter-element antenna spacing at the transmitter and the receiver respectively.

A. Analog Beamforming and Combining Technique

In the proposed scheme, the analog beamformer and combiner are designed in order to align the transmit and receive beams to discriminate between different paths of the channel, where the selection of the path is related to the transmitted symbol using BIM. As aforementioned, only the most dominant N p channel paths are chosen for transmission, such that N p is chosen to satisfy certain hardware constraints N p ≤ min(L t ,L r ). The dominant paths are estimated using conventional beam training techniques [START_REF] Tsang | Coding the beams: Improving beamforming training in mmwave communication system[END_REF].

Therefore, the analog beamformer at the transmitter side is calculated as follows

F t = [a t (φ i )] i=[1:Np]
. Also, the analog beam combiner is calculated at the receiver side as follows

F r =[a r (θ i ) H ] i=[1:Np]
. Furthermore, the equivalent channel H e is calculated as: H e =F r HF t . Finally, the ZF precoder is calculated as W=H H e (H e H H e ) -1 for the inter-beam interference mitigation.

IV. ANALYTICAL PERFORMANCE ANALYSIS A. Spectral Efficiency

The analog beamformer at the transmitter F t and combiner at the receiver F r aim at normalizing the spatial phases of H p , so that, the p-th term in the equivalent channel's diagonal, which represents the channel gain at path p, can be expressed as:

|H e (p,p)|=|F p r H p F p t |= 1 √ N t N r Nt i=1 Nr i=1 |α p |= N t N r |α p |. (6
) In [START_REF] Liu | Line-of-sight spatial modulation for indoor mmwave communication at 60 ghz[END_REF], one can observe the cancellation of the phase effects arising from the channel spatial dimensions (AoD and AoA) through beam alignment, ending up with the amplitude of the channel gain |α p | scaled by the transmit and receive antenna array gains √ N t N r . On that basis, the equivalent channel H e can statistically be analyzed by splitting the diagonal and off-diagonal parts and tackling each one separately. Considering the diagonal term in [START_REF] Liu | Line-of-sight spatial modulation for indoor mmwave communication at 60 ghz[END_REF], and assuming that the channel complex values α are independent and identically distributed (i.i.d) complex Gaussian α∼CN (0,1), we can conclude that |α| follows a Rayleigh distribution with mean √ π 2 and variance 1-π 4 . Therefore, we have:

|F p r H p F p t |∼Rayleigh √ πN t N r 2 ,N t N r (1- π 4 ) . (7)
Also, each off diagonal term F p r H p F y =p t is as follows:

|F p r H p F y =p t |= N r |α p | Nt i=1 |a H t (φ p )a t (φ y )| (8)
Given that φ is uniformly distributed in [0,2π], d t = λ 2 and that φ and α are statistically independent, the expected value of the offdiagonal term E |F p r H p F y =p t | can be expressed according to [START_REF] Wu | On favorable propagation in massive mimo systems and different antenna configurations[END_REF] as follows: where J 0 (x) is the zero order Bessel function of x and it decays in magnitude proportional to 1 √ x , which means that J 2 0 (x) decays in magnitude proportional to 1

E |F p r H p F y =p t | = N r E{|α p |}E Nt i=1 |a H t (φ p )a t (φ y )| = √ N r π 2N t Nt i=1 J 2 0 (π(i-1)) (9
x . Therefore, from equations( 7) and ( 9) the off diagonal term can be assumed to be negligible compared to the diagonal ones when N t is large enough. Moreover, the off diagonal term is proved in [START_REF] Wu | On favorable propagation in massive mimo systems and different antenna configurations[END_REF] to approach 0, when N t →∞ leading to the favourable propagation. Henceforth, considering the diagonal elements only, for tractability, the calculated SE can be considered as an upper bound for our framework.

Proposition 1: The average per stream SE upper bound can be approximated by:

C p ≈ 2 ln2 ln( ρN t N r σ)+ ln(2) 2 - κ 2 ( 10
)
where ρ is the Signal to Noise Ratio (SNR), and κ ≈ 0.5772 is the Euler constant.

Proof: This upper bound for per stream SE can be asymptotically achieved with increasing N t and is represented as follows:

C p =E log 2 1+ρ|F p r H p F p t | 2 =E log 2 1+ρN t N r |α p | 2 . ( 11
)
Assuming that ρN t N r >> 1, which is a valid assumption in mmWave massive MIMO systems, then

1 + ρN t N r |α p | 2 ≈ ρN t N r |α p | 2 .
Therefore, the per stream SE upper bound can be expressed as:

C p ≈ 2 ln2 E ln ρN t N r |α p | (12)
where ln √ ρN t N r |α p | has a Log-Rayleigh distribution defined in [START_REF] Rivet | Log-rayleigh distribution: A simple and efficient statistical representation of log-spectral coefficients[END_REF] (ln

√ ρN t N r |α p | ∼ LogRay(ρN t N r σ 2 ))
, where σ 2 is the variance of the complex Gaussian channel coefficients α. Then, the Probability Density Function (PDF) of z =ln √ ρN t N r |α p | is given as follows [START_REF] Rivet | Log-rayleigh distribution: A simple and efficient statistical representation of log-spectral coefficients[END_REF]:

f(z)= (e z ) 2 σ 2 z exp - (e z ) 2 2σ 2 z ( 13
)
where σ 2 z results from scaling σ 2 by ρN t N r (σ z = ρN t N r σ 2 ). Moreover, the mean (µ) and variance (η 2 ) of ln √ ρN t N r |α p | are expressed as [START_REF] Rivet | Log-rayleigh distribution: A simple and efficient statistical representation of log-spectral coefficients[END_REF], [START_REF] Wu | Cooperative spatial modulation for cellular networks[END_REF]: µ=ln( √ ρN t N r σ)+ ln(2) 2 -κ 2 and η 2 = π 2 24 . Therefore, the average per stream SE upper bound in can be expressed as in [START_REF] Wu | Cooperative spatial modulation for cellular networks[END_REF].

B. Conditional Bit Error Probability

The detector has to analyze the received signals:

∀j, y j =    δ j +u j , if j th beam is targeted u j , otherwise (14)
where u j is the received noise at beam j after applying the analog combiner, given that u = F r n and u ∈ C Np×1 . Then, the formula that derives the analytic average BEP conditioned by the channel P e for BIM schemes is:

P e = 1 m •E    Np k Np j =k P(x k →x j )d(x k ,x j )    . ( 15
)
where d(x k , x j ) is the Hamming distance between two spatial symbols x k and x j , and P(x k →x j ) is the Pairwise Error Probability (PEP) between x k and x j .

Proposition 2: Considering the Maximum Likelihood (ML) detection, the PEP of the BIM scheme conditioned by the knowledge of the channel matrix H is approximated by:

P(x k →x j |H)≈Q( -j 2σ n ) (16)
Proof: The PEP writes as,

P(x k →x j |H)=P(d k >d j |H) =P((u j δ j -u k δ j )> 1 2 (2δ j 2 )|H)=Q( ξ) (17)
where d j = y-δ j x j 2 and Q(x) is the Gaussian distribution function:

Q(r)= ∞ x 1 2π e -r 2
2 dr and ξ is calculated as follows:

ξ = δ 2 j 2 F k r -F j r 2 σ 2 n , (18)
where,

F k r -F j r 2 = 1 N r Nr b=1 (e jbθ k -e jbθj ) 2 (19)
For high numbers of receive antennas, the analog combiners at the receiver become orthogonal. Thus, we can write

F k r -F j r 2 ≈ 2.
Then we have ξ =

δ 2 j 4σ 2 n
, which concludes the proof.

C. Multistream ABER Proposition 3:

The multistream Average BEP (ABEP) of BIM transmission in a Rayleigh fading channel is approximated by:

ABEP≈ 1 2 µ 1+µ (20)
where µ= NtNr 4σ 2 n .

Proof:

When the channel H changes, the value of ξ changes. Assume that the channel matrix entries follow a Rayleigh distribution in amplitude, i.e. α follows a Rayleigh distribution. For δ j , considering the best case to find the lower bound of the Average BEP (ABEP), where for high number of transmit antennas, the interference at the off diagonal terms in the equivalent channel matrix is zero, in this case δ j could be approximated by the diagonal terms: δ j =H e (j,j)= N t N r α j .

(21) Than we can easily see that:

ξ = N t N r α j 4σ 2 n =µα 2 (22)
follows a chi squared distribution where the PDF is:

p(ξ)= 1 µ e -ξ µ , ξ >0 (23)
and as a result, using the same mathematical derivations used to comthe ABEP of BPSK in Rayleigh channels, the ABEP is given by:

+∞ 0 Q( ξ)p(ξ)dξ = 1 2 µ 1+µ (24)
V. SIMULATION RESULTS In this section, the performance of the proposed hybrid-BIM scheme is evaluated in terms of SE and BER. The transmit and receive antenna arrays are ULAs, and the number of transmit/receive RF chains equals the number N p of the active sparse channel paths. Finally, we consider that perfect Channel State Information (CSI) is available at both the transmitter and the receiver.

In Fig. In Fig. 3, the performance of the proposed hybrid-BIM is evaluated through the measurement of the SE versus the ratio between the average transmit power level and noise level, i.e. SNR= Pt σ 2 n . Two system configurations, namely 32x8 with N p = 2 paths and 128x8 with N p =2 paths, are considered. It is observed that the numerical results are upper bounded by the theoretical ones for all setups and almost match asymptotically (N t is large), hence validating the derived SE model in Proposition 1. Moreover, the analog-BIM scheme is compared to the hybrid-BIM one for both setups. It is concluded that the hybrid approach achieves higher SE compared to the pure analog one. One can also note that the SE gap between them increases when the SNR level is raised. This is easily explained from the beam-interference level which is not cancelled with analog-BIM and thus limits the performance at high SNR regime.

In Fig. [START_REF] Mokh | Theoretical performance of coherent and incoherent detection for zero-forcing receive antenna shift keying[END_REF], the performance of the proposed system is evaluated in terms of BER versus SNR and using the same system configurations as previously. The theoretical ABEP given by Proposition 3 is compared to the simulated BEP of BIM using either hybrid or analog beamforming. Again from its beam-interference cancellation capability, it is clearly seen that the hybrid-BIM scheme outperforms the analog-BIM one, as more as the SNR level increases. On one other hand, it is shown that the theoretical BEP of the hybrid-BIM system becomes accurate when sufficiently increasing the number of transmit antennas. This comes from the approximation made in Proposition 3, where a high number of transmit antennas is considered to neglect the off-diagonal elements of the equivalent channel.

VI. CONCLUSION

In this letter, BIM with hybrid beamforming at the transmitter and analog combining at the receiver is introduced and studied in a mmWave context. Analytical derivations of the SE and BEP of the proposed hybrid-BIM scheme are provided. Thereby, it is shown that the hybrid-BIM approach increases the system SE and reduces the transmission BER compared to the pure analo-BIM case of the literature. More precisely, it is highlighted that the proposed hybrid-BIM scheme outperforms the analog-BIM one at high SNR, since the latter may be strongly affected (dominated) by inter-beam interference.

Figure 1 :

 1 Figure 1: Block diagram of BIM with analog beamforming architecture

Figure 3 :Figure 4 :

 34 Figure 3: Comparing the per stream SE for the analog and hybrid beamforming scenarios in a sparse nLoS channel environment.

  1

  2, we first compare the empirical probability density function (PDF) of ln √ ρN t N r |α p | with the theoritical PDF obtained from the Log-Rayleigh distribution in (13) for validation purpose.

	1 2 3 4 5 6 7 8 9 10 11	Probability Density Function (PDF)	0 0.1 0.2 0.3 0.4 0.5 0.7 0.8 0.6			Simulation (N p =2, N t =32, N r =8) Theoritical (N p =2, N t =32, N r =8) Simulation (N p =2, N t =128, N r =8) Theoritical (N p =2, N t =128, N r =8)
	13 12		0	1	Ln(abs(F r,RF p H p 2 3 4	F t,RF p )) 5	6	7
	14 15	Figure 2: Empirical and theoretical PDF of ln(|F p r H p F p t |) for
	16	different multiantenna scenarios.
	17
	18
	19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 F o r R e v i e w O n l y

  [1] A.Alkhateeb, O. E. Ayach, G. Leus, and R. W. Heath, "Channel estimation and hybrid precoding for millimeter wave cellular systems," IEEE Journal of Selected Topics in Signal Processing, vol. 8, no. 5, pp. 831-846, Oct 2014.

			No Interference Case (Upper Bound)
			Theoritical HBF
		16	Analog (N p	=2, N t	=32, N r	=8)
	Spectral Efficiency (bps/Hz)	6 8 10 12 14 4	HBF (N p Analog (N p =2, N t =2, N t =32, N r =128, N r =8) HBF (N p =2, N t =128, N r =8) =8) 128 × 8 32 × 8
		2
		-10	-5		0	5	10	15
					SNR (dB)