Hakim Badis
email: badis@u-pem.fr

Abderrezak Rachedi
email: rachedi@u-pem.fr

Modeling tools to evaluate the performance of wireless multihop networks

Keywords: Wireless Multi-hop networks, Modeling tools, Performance evaluation, MIMO

Recently, multi-hop communication has been introduced in next generation wireless networks to extend the service coverage area and to improve the wireless transmission capacity. In this chapter, we study several modeling tools mainly used to evaluate the performance of wireless multi-hop networks. We investigate three aspects of modeling tools: 1) stochastic modeling based on Markov-chain, 2) conflict graph particularly graph coloring, 3) asymptotic approaches for large-scale networks. For each tool, two physical communication systems are investigated: Single-Input Single-Output (SISO) and Multi-Input Multi-Output (MIMO). In addition, we illustrate how each tool contributes in the performance evaluation with particular emphasis on throughput and network capacity.

Introduction

A wireless multi-hop network can be viewed as a set of nodes able to communicate with each other directly or beyond their transmission range by using nodes as relay points acting as routers. Multi-hop communication has several advantages such as: interference reduction, spectrum reuse increase, radio coverage extension, traffic load balancing, and energy consumption reduction. These advantages make multi-hop communication more popular, and several kinds of networks are based on it such as Mobile Ad hoc Networks (MANETs) [START_REF]Mobile Ad hoc Networking (MANET) : Routing Protocol Performance Issues and Evaluation Considerations[END_REF], Vehicular Ad hoc Networks (VANETs) [START_REF] Aoki | Inter-Vehicle Communication: Technical Issues on Vehicle Control Application[END_REF][START_REF] Al-Sultan | A comprehensive survey on vehicular Ad Hoc network[END_REF], Wireless Sensor Networks (WSN) [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF], Wireless Mesh Networks (WMNs) [START_REF] Akyildiz | Wireless mesh networks: a survey[END_REF], and so on. Their application range varies from civilian use to disaster recovery and military use. Recently, this technology has become a promising solution for the next generation wireless communication systems. It is considered in the standardization process of next-generation mobile broadband communication systems such as 3GPP LTE-Advanced [6], IEEE 802.16j (mobile WiMax) [START_REF]Baseline Document for Draft Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems[END_REF], and IEEE 802.16m [START_REF]IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems Amendment 3: Advanced Air Interface[END_REF]. For example, Mobile Multi-hop Relaying mechanism (MMR) is integrated into intermediate nodes to forward the traffic from mobile stations (MSs) to the base station (BS). In doing this, a wireless multi-hop network can effectively extend the service coverage and improve the overall capacity performance of a wireless communication system. Moreover, if each node is equipped with multiple antennas, and using point-to-point MIMO techniques to increase the rate of every individual link, then the overall capacity of the network increases linearly with the number of antennas per node [START_REF] Chen | MIMO communications in ad hoc networks[END_REF][START_REF] Jiang | On the Asymptotic Capacity of Multi-Hop MIMO Ad Hoc Networks[END_REF][START_REF] Jindal | Multi-Antenna Communication in Ad Hoc Networks: Achieving MIMO Gains with SIMO Transmission[END_REF]. For this reason, both singleantenna and multi-antenna communications in multi-hop networks are considred in this chapter. Several advantages of wireless multi-hop communication can be summarized as follows:

-Interference reduction: it is due to the reduction of transmission power (P TX ) where nodes use close neighboring nodes to relay packets instead of increasing P TX . This allows to reduce the number of competitor nodes sharing the same channel (link). -Spectrum reuse increase: it is due to the short communication range where the spectrum can be reused more frequently. The spectral efficiency increases when the coverage area decreases [START_REF] Rappaport | Microcellular communication systems with hierarchical macrocell overlays: traffic performance models and analysis[END_REF]. Thus, the availability of frequency channels per unit area increases the system capacity. -Radio coverage extension: it is guaranteed by relayed nodes through multi-hop communication, and it allows to reduce the nodes' isolation. -Traffic load balancing: it is due to the different potential paths to reach the destination. This allows to avoid the congested nodes/links and to select non-congested nodes in order to ensure load balancing between them. -Power consumption reduction: it is due to short-range communication where nodes reduce their power transmission and select relayed neighboring nodes to forward packets to their destination.

However, wireless multi-hop networks have some drawbacks such as: system complexity and security. The complexity is related to the design of an efficient routing protocol able to support a large number of nodes on the one hand, and a distributed MAC protocol able to face the hidden nodes problem on the other hand. The security issue is mainly related to the link vulnerability and end-to-end security services (authentication, confidentiality, integrity, and non-repudiation) guarantee.

Despite extensive research in networking, many challenges remain in the study of wireless multi-hop network including the development of MAC protocols that exploit the capabilities of advanced physical layer technologies like Multiple-Input Multiple-Output (MIMO) and Orthogonal Frequency-Division multiplexing (OFDM) [START_REF] Prasad | OFDM for Wireless Communications Systems[END_REF]. That is why in this chapter we focus on the modeling tools able to design efficient performance models.

Examples of emerging wireless multi-hop networks

A transmission over multi-hop networks consists of multiple low-power transmissions of data over short distances. This approach enhances the network coverage, increases the network throughput through frequency reuse and reduces the total energy consumption of all participating nodes. This is why multi-hop relaying is being curentltly considred in the next generation wireless communication systems. Three emrging multihop networks have attracted growing attention: Vehicular Ad Hoc Network (VANETs), Wireless Sensor Networks (WSNs) and Multihop Cellular Networks.

Vehicular Ad Hoc Networks

VANET is a particular case of wireless multihop network, which has the constraint of fast topology changes due to the high node mobility [START_REF] Aoki | Inter-Vehicle Communication: Technical Issues on Vehicle Control Application[END_REF][START_REF] Al-Sultan | A comprehensive survey on vehicular Ad Hoc network[END_REF]. With the increasing number of vehicles equipped with computing technologies and wireless communication devices, inter-vehicle communication is becoming a promising field of research, standardization, and development. VANETs enable a wide range of applications, such as prevention of collisions, safety, blind crossing, dynamic route scheduling, real-time traffic condition monitoring, etc. Another important application for VANETs is providing Internet connectivity to vehicular nodes. Figure 2 shows an example of a VANET.

Wireless sensor networks

WSNs are composed by low-power sensor nodes equipped with sensing board, processing, and wireless communication capabilities [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF]. Sensor nodes collaborate to collect and to relay sensed information to a sink node using multi-hop communication. These networks can be applied in different applications such as healthcare, military, industrial, monitoring, tracking based on multimedia sensor and many other fields [START_REF] Boulanouar | Energy-Aware Object Tracking Algorithm using Heterogeneous Wireless Sensor Networks[END_REF][START_REF] Prasanna | An Overview of Wireless Sensor Networks Applications and Security[END_REF]. Recently, IP-based sensor networks are attracting more attention, and are enabling the developpement of the Internet of things (IoT) [START_REF] Tsai | Future Internet of Things: open issues and challenges[END_REF]. However, energy consumption continues to remain a barrier challenge in many sensor network applications that require long lifetimes. Figure 3 shows an example of a WSN. and IEEE 802.16m [START_REF]IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems Amendment 3: Advanced Air Interface[END_REF]. Figure 4 shows an example of a MCN.

SISO versus MIMO systems

In traditional single-antenna systems, called Single-Input Single-Output (SISO) systems, both transmitter and receiver are equipped with only one antenna each as illustrated in Figure 5. SISO systems are advantageous in terms of simplicity and they are relatively easy to design and implement. They are used in several radio communication technologies like radio and TV broadcast, mobile phone networks (2G and 3G), local and personal wireless technologies (e.g. Wi-Fi and Bluetooth), sensor networks, etc. The channel capacity of such systems is given by Shannon's well-known formula [START_REF] Shannon | A mathematical theory of communication[END_REF]:

⎟ ⎠ ⎞ ⎜ ⎝ ⎛ + = N S B C 1 log * 2
where C is the capacity in bits per second, B is the bandwidth of the channel in Hertz, and S/N is the signal-tonoise ratio. Despite the significant progress made in improving the performance of SISO communication systems using OFDM and advanced coding and modulation schemes, they remain insufficient to meet the rapidly growing demands for high bandwidth and robustness in the next-generation networks. Recently, the use of multiple antennas at both transmitter and receiver has attracted much interest. This system is called Multiple-Input Multiple-Output (MIMO). Figure 6 shows an example of a MIMO system having three antennas at the transmitter and at the receiver. MIMO system is introduced in the new communication technologies standards like the Long Term Evolution (LTE) of the third Generation Partnership Project (3GPP) [START_REF]3GPP, Technical Specification and Technical Reports for a UTRAN-based 3GPP system[END_REF] the second generation of the Worldwide Interoperability for Microwave Access (WiMAX 2) [START_REF]IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems Amendment 3: Advanced Air Interface[END_REF], WiFi (IEEE 202.11n) [START_REF][END_REF], etc. This growing interest in MIMO systems is attributed to their various physical layer capabilities that allow:

• an increased channel capacity at higher signal-to-noise ratios by means of spatial multiplexing techniques.

The new capacity of MIMO channel is given by [START_REF] Foschini | Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas[END_REF][START_REF] Gesbert | From theory to practice: An overview of MIMO space-time coded wireless systems[END_REF] ⎟ ⎠

⎞ ⎜ ⎝ ⎛ × × + = N S M N B C 1 log * 2
where N and M are respectively the number of transmitting and receiving antennas; • a decreased error rate by means of spatial diversity techniques;

• an improved signal-to-noise ratios using beamforming techniques.

However, these capabilities cannot be fully leveraged at the same time. The optimal strategy can be taken by the upper layers (MAC and routing) based on adapted cross-layer design approaches [START_REF] Sundaresan | A fair medium access control protocol for ad-hoc networks with mimo links[END_REF][START_REF] Tang | A joint mimo-ofdm transceiver and mac design for mobile ad hoc networking[END_REF][START_REF] Park | Space-mac: Enabling spatial reuse using mimo channel-aware mac[END_REF][START_REF] Fakih | Beamforming in Ad Hoc Networks: MAC Design and Performance Modeling[END_REF][START_REF] Mundarath | A cross layer scheme for adaptive antenna array based wireless ad hoc networks in multipath environments[END_REF].

MIMO capabilities

By employing multiple transmitting antennas and multiple receiving antennas in conjunction with appropriately designed signal processing algorithms, MIMO has offered great benefits to wireless communications compared to conventional SISO systems. Indeed, a significant enhancement of communication quality at the physical layer has been observed in terms of link capacity, link reliability and communication range. Below, we briefly describe the physical layer capabilities.

Spatial multiplexing [START_REF] Foschini | Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas[END_REF][START_REF] Telatar | Capacity of multi-antenna Gaussian channels[END_REF][START_REF] Chiani | MIMO networks: the effect of interference[END_REF]. At the transmitter, the data sequence is split into N sub-sequences that are transmitted simultaneously using the same frequency band (see figure 7). At the receiver, the sub-sequences are separated by means of interference cancellation algorithms, e.g., linear Zero-Forcing (ZF) [START_REF] Choi | A transmit preprocessing technique for multiuser MIMO systems using a decomposition approach[END_REF][START_REF] Spencer | Zero-forcing methods for downlink spatial multiplexing in multiuser MIMO channels[END_REF], Minimum Mean-Squared-error (MMSE) detector [START_REF] Barry | Digital Communications[END_REF], Maximum-Likelihood (ML) detector [START_REF] Foschini | Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas[END_REF][START_REF] Oussama Damen | IEEE On Maximum-Likelihood Detection and the Search for the Closest Lattice Point[END_REF], Successive Interference Cancellation (SIC) detector [START_REF] Weber | Transmission Capacity of Wireless Ad Hoc Networks with Successive Interference Cancellation[END_REF], etc. For a good error performance, M≥N is required. Under the spatial multiplexing technique, the capacity of MIMO systems scales linearly with min{N,M} [START_REF] Foschini | Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas[END_REF]:

{ } ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ + × × = N S B M N C 1 log , min 2 Figure 7. Spatial Multiplexing
Beamforming [START_REF] Lo | Maximum ratio transmission[END_REF][START_REF] Love | Grassmannian Beamforming for Multiple-Input Multiple-Output Wireless Systems[END_REF][START_REF] Kang | Largest eigenvalue of complex Wishart matrices and performance analysis of MIMO MRC systems[END_REF]. Due to antenna array geometry, radio frequency (RF) signals reach antenna elements at different times. By adjusting the initial phase of the RF signals on each antenna element, constructive superposition at the receiver can be achieved. From figure 8, beamformers can reject interference while omnidirectional antennas cannot improve SNR and system capacity. Spatial Diversity [START_REF] Alamouti | A simple transmit diversity technique for wireless communications[END_REF][START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF][START_REF] Zheng | Diversity and multiplexing: A fundamental tradeoff in multiple-antenna channels[END_REF]. By sending/receiving multiple redundant versions of the same data stream and performing appropriate combining, the error rates decrease. When using diversity transmission, an appropriate pre-processing is needed to enable a coherent combining at the receiver. The well-known techniques are: Alamouti's scheme [START_REF] Alamouti | A simple transmit diversity technique for wireless communications[END_REF], space-time trellis codes [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF], and orthogonal space-time block codes [START_REF] Tarokh | Space-time block codes from orthogonal designs[END_REF]. When using diversity reception, an appropriate combining is needed. Various combining strategies are proposed [START_REF] Zheng | Diversity and multiplexing: A fundamental tradeoff in multiple-antenna channels[END_REF]: Equal-Gain Combining (EGC), Selection Combining (SC), Maximum-Ratio Combining (MRC), etc.

Modeling of SISO and MIMO channels

The following notation will be used throughout the chapter. Scalars are given by normal letters, vectors by boldface lower case letters, and matrices by boldface upper case letters.

Under SISO systems and using OFDM, the channel can be expressed in the frequency domain as:

) ( ) ( ) ( ) ( k w k s k h k r + × =
where r(k) is the received symbol, s(k) is the transmitted symbol, w(k) is the Additive White Gaussian Noise (AWGN), and h(k) is a scalar value representing the gain and phase of the channel for subcarrier, k.

For MIMO systems, the received and transmitted symbols become vectors. Let us also assume that a transmitting station is equipped with N antennas and the receiving station is equipped with M antennas. The (MxN) channel matrix H(k) is written as:

⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( , 2 , 1 , , 2 2 , 2 1 , 2 , 1 2 , 1 1 , 1 k h k h k h k h k h k h k h k h k h k N M M M N N ! " " " " ! !

H

where the elements, h i,j (k), are each complex scalar representing the channel gain and phase from transmitting antenna j to receiving antenna i, for subcarrier k. The n th column of H is often referred to as the spatial signature of the n th transmitting antenna across the receiving antenna array. The MIMO channel is given after the Fast Fourier Transform (FFT) as in [START_REF] Barry | Digital Communications[END_REF].

) ( ) ( ) ( ) ( k k k k w s H r + × = where r(k) = [r 1 (k) r 2 (k) … r M (k)] T and s(k) = [s 1 (k) r 2 (k) … r N (k)] T .
In order to estimate the SISO channel in OFDM systems, several methods [START_REF] Barry | Digital Communications[END_REF] can be employed using time or frequency domain samples. These methods are extended to MIMO channel estimation like Least-Squares (LS) method or Minimum Mean-Squared-Error linear detectors.

3.

Performance models

A performance model is a model that is used to assess and to evaluate the performance of a network. The development of any performance model follows the following modeling steps: 1) understanding the network properties, (2) model construction, and (3) verification and validation. In this section, we focus on stochastic modeling based on Markov-chain to evaluate the network performance in terms of throughput. The conflict graph models are presented to evaluate the network capacity. Finally, we present asymptotic capacity modeling to assess the upper and lower band network capacity. All these performance models are presented for SISO and MIMO systems.

Stochastic modeling based on Markov-chain

Preliminary and definitions

A Markov chain is a very powerful tool used in various fields including physics, economics, engineering, genetics, and more. It is widely used because of its simplicity, and flexibility. It's easy to model different systems with an arbitrary number of states and their transition matrix. It's used to model a dynamic system like wireless network that changes its states over time. Markov chains are classified into two kinds: continuous time Markov chains (CTMC) and discrete time Markov chains (DTMC). In DTMC, the state is allowed to change only at the discrete instants; that is not the case for CTMC where the state can change at any time.

In computer network area, the stochastic models are selected to represent uncertainty phenomena of the network (because it depends on many unknown factors) where its behavior varies as time advances. In this subsection, we focus on two communication systems: Single-Input Single-Output (SISO), and Multiple-Input Multiple-Output (MIMO) both in wireless multi-hop networks. We present stochastic models based on Markov chain to evaluate the network throughput and MAC protocols performance based on IEEE 802.11.

Case of SISO System

In carrier sense multiple access with collision avoidance (CSMA/CA) protocol, before node transmitting, it checks the state of the channel if it is busy or idle. If the channel is busy, the node waits until the channel becomes idle. If a collision happens, each node waits for a random time named "backoff". The backoff mechanism has a key role to avoid the interference between competitor nodes.

The well-known performance model based on DTMC to estimate the throughput at the MAC layer with IEEE802.11 is proposed by Bianchi [35]. This model assumes a single collision domain to reduce the complexity of the interference relationship. On the other hand, only one node among N competitors nodes can successfully transmit a packet at any time. It takes into account only the case of N active nodes called "saturated case" where these nodes always have a packet to transmit. Bianchi's model consists in modeling the behavior of backoff algorithm of a CSMA/CA in the saturated case as illustrated in figure 9. The idea behind this model is to get the throughput expression (S) according to different probabilities such as probability that a transmission is successful (P s ), and the probability that there is at least one transmission in a given slot time (P tr ) where these probabilities depend on backoff parameters. Equation 1shows the throughput expression [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]: The limits of this analytical model are based on two strong assumptions: saturated traffic, and single type of traffic assumptions. The typical traffic network is not only non-saturated, but also is heterogeneous. Many proposed models are based on non-saturated case, but without taking into account the heterogeneity of the traffic source [START_REF] Daneshgaran | Unsaturated throughput analysis of IEEE 802.11 in presence of non ideal transmission channel and capture effects[END_REF][START_REF] Lee | On use of traditional M/G/1 model for IEEE 802.11 DCF in unsaturated traffic conditions[END_REF]. The main idea of these models consists in adding a new state representing the case where the buffer is empty without a significant change of the Bianchi's model.

Other proposed models taking into account the heterogeneity of traffic sources with distinct arrival rates are proposed in literature [START_REF] Malone | Modeling the 802.11 distributed coordination function in nonsaturated heterogeneous conditions[END_REF][START_REF] Alazemi | Stochastic modelling and analysis of 802.11 DCF with heterogeneous non-saturated nodes[END_REF]. The added value of these models consists in the integration of the queuing model in order to evaluate the network performance with heterogeneous traffic sources. In the network, it's impossible to predict the human behavior and their communication requirements, that's why probability and stochastic processes particularly queuing theory are good candidates to predict the network behavior and to understand how traffic arrives. In these models the traffic arriving at the transmission queues is assumed as Poisson process.

However, all these models are proposed for legacy IEEE 802.11. Recently, other models are proposed for the IEEE 802.11 Enhanced Distributed Channel Access (EDCA) function [START_REF] Kosek-Szott | A Comprehensive analysis of IEEE 802.11 DCF heterogeneous traffic sources[END_REF][START_REF] Nguyen | Performance analysis of IEEE 802.11 WLANs with saturated and unsaturated sources[END_REF]. These models are applied only to the single collision domain where each link interferes with all other links as illustrated in figure 10.a. Figure 10.b illustrates the case of multiple collision areas which is a typical case of the multi-hop network. In other words, these models can be used in the case of one hop communication (eg. WLAN). Other models are proposed in the case of wireless multi-hop networks [START_REF] Aziz | Models of 802.11 multi-hop networks: Theoretical insights and experimental validation[END_REF][START_REF] Abreu | Hierarchical Modeling of IEEE 802.11 Multi-hop Wireless Networks[END_REF][START_REF] Benslimane | Rate adaptation scheme for IEEE 802.11-based MANETs[END_REF]45,[START_REF] Jiao | End-to-End Delay Distribution Analysis for Stochastic Admission Control in Multi-hop Wireless Networks[END_REF]. The adaptation of Bianchi's model to the multi-hop network is mainly based on the integration of neighboring nodes' environment in the throughput expression. In this kind of network the hidden-terminal problem may significantly impact the performance of MAC protocol [START_REF] Xu | Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks?[END_REF]. That's why in different proposed models each node has to take into account the parameters of its neighboring nodes such as: the probability to access a channel, the probability of failure, etc. For instance, a 3-dimension Markov chain is used to model the rate adaptation scheme in Mobile Ad hoc Networks (MANETs) [START_REF] Benslimane | Rate adaptation scheme for IEEE 802.11-based MANETs[END_REF]. This model evaluates the performance of dynamic rate adaptation scheme able to guarantee a tradeoff between throughput and relative fairness. The third dimension represents the rate that varies according to different parameters like link quality.

DTMC is not only used to evaluate the performance of the MAC layer protocol, but also to evaluate the impact of misbehaving nodes that are cheating on Binary Exponential Backoff (BEB) [START_REF] Guang | Enhancing IEEE 802.11 Random Backoff in Selfish Environments[END_REF][START_REF] Rachedi | Toward a cross-layer monitoring process for mobile ad hoc networks[END_REF]. The misbehaving nodes particularly the selfish nodes may maliciously manipulate BEB parameters in order to create unfairness situations, or to disrupt the network services.

Case of MIMO

Performance models based on DTMC for MIMO system do not require any change from those proposed for SISO systems if the used MAC protocol is independent from the underlying physical layer. For example, the MAC protocol CSMA/CA can be applied to both SISO and MIMO systems, and thus all the models previously developed for SISO systems (see section 3.1.2) remain valid. In literature, several works [START_REF] Zhou | A novel distributed MIMO aware MAC protocol design with a Markovian Framework for performance evaluation[END_REF][START_REF] Akin | On the throughput and energy efficiency of cognitive MIMO transmissions[END_REF][START_REF] Carvalho | Analytical Modeling of Ad Hoc Networks that Utilize Space-Time Coding[END_REF] maintain the same performance models based on the original or enhanced Bianchi's two-dimensional Markov chain.

The traditional MAC protocols do not fully exploit the capabilities of the MIMO physical layer like multiple simultaneous transmissions from multiple nodes in the same collision area. Thus, some recent works [START_REF] Sundaresan | A fair medium access control protocol for ad-hoc networks with mimo links[END_REF][START_REF] Tang | A joint mimo-ofdm transceiver and mac design for mobile ad hoc networking[END_REF][START_REF] Park | Space-mac: Enabling spatial reuse using mimo channel-aware mac[END_REF][START_REF] Fakih | Beamforming in Ad Hoc Networks: MAC Design and Performance Modeling[END_REF][START_REF] Mundarath | A cross layer scheme for adaptive antenna array based wireless ad hoc networks in multipath environments[END_REF] on cross-layer MAC protocols design have been proposed to offer multiple functionalities like parallel transmissions without interference. The main idea is to distribute the spatial degrees of freedom (DoFs) between spatial multiplexing, beamforming and spatial nulling to schedule multiple concurrent transmissions simultaneously. The performance evaluations of these MAC protocols based on DTMC models remain unexplored.

In the following section we show how to integrate the MIMO physical layer capabilities into the performance model. Without loss of generality, we consider only the SPACE-MAC [START_REF] Park | Space-mac: Enabling spatial reuse using mimo channel-aware mac[END_REF]

Performance modeling based on graph coloring and clique constraints

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to the vertices or edges, or both, subject to certain conditions. It has found a number of applications in computer science such as data mining, image segmentation, clustering, image capturing, networking etc. Since a wireless multi-hop network can be modeled as a graph, graph coloring has found its natural place to address some issues related to connectivity, scheduling, resource allocation, frequency assignment, interference reduction, capacity estimation, etc. In this section we show how to use graph coloring to find a link scheduling policy to satisfy the desired rates. Then, we compute the available link capacity to control the amount of data that could be inserted into the network.

The capacity of any link in wireless multi-hop networks is closely related to the interference relationships between all the active links on the same channel. Conflict graphs offer a way to represent and model such relationships, in which wireless links are represented by nodes, conflicts between links are represented by edges, timeslots are represented by the colors, and allocating time-slots to links can be represented by assigning colors to nodes with no adjacent vertices having the same color. The smallest number of colors needed to color the conflict graph is known as the chromatic number of the graph. If we can color our conflict graph with the fewest number of colors possible, we can schedule all the links having the same color at the same time.

All the mutual conflict links belong to the same complete sub-graph (clique). At each slot time, at most one link in each clique can be active. This rule is converted to a constraint and we will show when this constraint becomes necessary and/or sufficient.

Preliminary and definitions

The link capacity in a single-hop network can be defined as the physical transmission bit rate of the source, determined by: the Shannon limit, the fixed modulation scheme and the bit error rate. In a wireless multi-hop network context, several links share the same transmission medium, and so the link capacity decreases when more simultaneous transmissions occur. The sum of all active data stream throughputs in the same interference area gives the consumed capacity. Consequently, the available link capacity is the difference between the link capacity (in a single-hop network) and the consumed capacity:

Available Link Capacity = Link Capacity -Consumed Capacity A wireless multi-hop network can be seen at each time instant as an undirected graph in which the nodes represent wireless devices, and there is an edge between two nodes if the nodes are within transmission range of each other. The resulting graph G, called connectivity graph, is undirected because our channel model only considers bidirectional communication links and ignores unidirectional links. Figure 12 shows an example of a connectivity graph. Note that graph G is not Euclidean due to the radio propagation/interference characteristics. In the mathematical area of graph theory, a clique is a complete subgraph. A clique is maximal if it is not contained in another larger clique. In other words, a maximal clique cannot be extended by including one or more adjacent nodes. Determining maximal cliques in the clique graph will allow to determine the set of links that mutually conflict with each other in the corresponding connectivity graph. The conflict graphs shown in figures 13.a and 13.b have three ({1,2,4,5}, {1,2,3} and {2,3,6,7}) and one ({1,2,3,4,5,6,7}) maximal cliques respectively. We note that, as distance-H of the interference model increases, the number of maximal cliques decreases.

Link capacity estimation with SISO

The LCG-nodes in a maximal clique represent the maximal set of mutually contending wireless links, along which only one flow may transit at any given time on the channel. Accordingly, the sum of the rates of LCGnodes in each maximal clique cannot exceed the capacity of the channel; these conditions define which we call the clique constraints. Since the network must satisfy the capacity constraints for all cliques, we can write the clique constraints in a matrix form. We represent a set of flow rates as the column vector F of size n, where n is the number of links in the network G and F i is the average flow rate assigned to link i. Let C i be a column vector of size n with all entries equal to the channel capacity C i . Hence we have,

i i C F Q i ≤ × ∀ , (1)
where Q i is an incidence matrix, which is of order q * n. Here, q is the number of maximal cliques that this link i belongs to, and n is the total number of links. The union of the clique matrices across all the links gives the global clique matrix Q. For example, consider the conflict graph shown in figure 13.a, the corresponding global clique matrix Q is given by:

! ! ! ! " ! ! ! ! # $ Links q q q Q ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 3 2 1
Note that the flow rate F i assigned to link i in an interval of time ]tτ, t], can be written as:

, ) ( 1 ∫ - = t t i i dr r F F τ τ !
where F i (r) is the instantaneous flow rate utilization on link i at time r. Consequently, equation 1 can be written as

i i C F Q i ≤ × ∀ ! , (2)
It is clear that the clique constraints represent a necessary condition for a realizable scheduling transmission to exist, since there cannot be a feasible schedule over links that form a violated clique constraint. The challenge is to show that these conditions are also sufficient. Unfortunately, as shown in [START_REF] Badis | An efficient bandwidth guaranteed routing for ad hoc networks using ieee 802.11 with interference consideration[END_REF][START_REF] Gupta | Sufficient rate constraints for QoS flows in ad-hoc networks[END_REF], the sufficiency is acquired only when the conflict graph is: • A perfect graph, i.e., for every induced subgraph, the clique number equals the chromatic number;

• A unit disk graph, i.e., a planar graph in which an edge exists between two vertices if and only if their Euclidean distance is lower than a constant threshold. In this case, the clique constraints must be scaled by a factor of 0.46. • If distance-3 interference model is used, then the average scaling factor value is 0.71.

In general, and based on the notion of scaling factor, equation 2 becomes:

i i C F Q i × ≤ × ∀ β ! , (3)
As the LCG-node can be a part of multiple cliques, it considers all the cliques that it belongs to, and takes the worst case available capacity over all the cliques. The available capacity on an LCG-node, i, is ( )

⎭ ⎬ ⎫ ⎩ ⎨ ⎧ × - × = Γ F Q C i i i ! β min (4)
where Γ i is the available capacity on link i, taking into account active flows on i, as well as interference from neighboring links. For example, in figure 13.a, let the allocated flow on each LCG-node { 1 = (a,b), 2 = (b,c), 3 = (c,d), 4 = (a,e), 5 = (a,f), 6 = (d,g), 7 = (d,h) } be denoted by { Ḟ 1 , Ḟ 2 , Ḟ 3 , Ḟ 4 , Ḟ 5 , Ḟ 6 , Ḟ 7 }. Then, the available capacity on the link between the monitor-forwarding nodes, 2 = (b,c), is:

( ) ( ) ( ) ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ + + + - × + + + - × + + - × = Γ ) ( ), ( ), ( min 7 6 3 2 2 5 4 2 1 2 3 2 1 2 2 F F F F C F F F F C F F F C ! ! ! ! ! ! ! ! ! ! ! β β β
In the same way, from figure 13.b we can write Γ 2 as: ( )

7 6 5 4 3 2 1 2 2 F F F F F F F C ! ! ! ! ! ! ! + + + + + + - × = Γ β 3.2.

Link capacity estimation with MIMO

Beamforming and spatial multiplexing techniques allow data streams concentration exclusively on one active link at each time; while spatial nulling allows traffic distribution between different concurrent links. We assume that the number of antennas at each node in the wireless multi-hop network is M. Let M i (M i ≤ M) be the DoF of the MIMO G-link i. At each time, the total number of DoFs allocated for beamforming, spatial multiplexing and spatial nulling cannot exceed M i . Consequently, a G-link i can support at most M i active data streams. Each DATA stream on the shared channel consumes one DoF. A DoF is defined by a pair of Transmit/Receive filters (precoding and receiving vectors). Two DoFs used simultaneously on the shared channel must be orthogonal to each other or have a low cross-correlation. Destructive interference can occur when two or more concurrent G-links are simultaneously using non-orthogonal or high cross-correlation DoFs due to:

• imperfect (and possibly very bad) estimation of the channel of active links in the collision area;

• mobility;

• the number of data streams in the collision area exceeds the number of available DoFs.

The first and second reasons can be avoided respectively by perfect channel estimation and static network assumptions. However the third reason can be expressed in the clique constraints.

Denote Tx(i) and Rx(i) the transmitter and receiver of G-link i, respectively. The average flow rate, Ḟ i , assigned to a G-link i is the sum of the multiplexed data streams (S i ) among all available DoFs transmitted by Tx(i) to Rx(i):

∑ = = i M j j i i S F 1 !
The set of all flow rates assigned to each G-link in the connectivity graph G is given by ( )

T M j j n i M j j i M j j T n i k i S S S F F F F ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = = ∑ ∑ ∑ = = = 1 1 1 1 1 1 ! ! " ! " ! " "
Where n is the number of G-links in the connectivity graph G. The available capacity on an LCG-node, i, is ( )

⎭ ⎬ ⎫ ⎩ ⎨ ⎧ × - × × = Γ F Q C M i i i i ! β min 3.3.

Asymptotic capacity modeling

Asymptotic capacity analysis helps to determine how the achievable throughput of each node and/or the overall network scales as the number of nodes, n, increases. Such investigation is essential to understand and predict the behavior of large-scale networks. Transition phases from good capacity to poor capacity, or vice versa, may occur when the number of nodes increases. In this case, a threshold determination becomes a necessity.

Usually, upper and lower bounds do match. When this happens (a gap between upper and lower bounds), constructive methods try to lower the upper bounds and/or raise the lower bounds until they match. Consequently, algorithms are used to compute one of the bounds (the most simple) and the other is obtained by construction for a maximal matching. This section investigates the capacity bounds modeling of large random SISO and MIMO wireless multi-hop networks. For the upper bound, critical constraints are applied. Each of them is used to obtain a related bound on the network capacity, and the minimum value between the obtained bounds determines the upper bound. For the lower bound, a constructive scheme is used to match the upper bound. It is based on several steps varying from network partitioning to scheduling and routing. After the model networks have been trained, we describe the critical constraints and the steps of the constructive scheme.

Random wireless multi-hop networks modeling

We assume that n nodes are randomly located on the surface of sphere of unit area (S 2 ) or torus of unit area (T 2 ). These geometric topologies without borders are used to avoid edge effects, which otherwise complicates the analysis. Each node selects a destination randomly and so a node may be the destination of multiple data streams. Each single data stream can support a fixed data rate of W bits/sec. The per-node throughput λ(n) bits/sec is defined as the minimum data rate that can be sent from each source to its destination via multi-hop routing. We use slotted time for transmissions. All transmissions employ the same nominal range or power. For the interference model, two models are proposed: • Protocol model: Let X i denote the location of a node i, and r(n) the common range. A transmission from node i to node j is successful if for any other node k that is transmitting simultaneously,

⎪ ⎩ ⎪ ⎨ ⎧ × Δ + ≥ - ≤ - ) ( ) 1 ( ) ( n r X X n r X X j k j i
• Physical model: Let T be a subset of nodes simultaneously transmitting, and P be the common power level.

A transmission from node i to node j is successful if

β α α ≥ - + - ∑ ∈ ≠ T k i k j k j i X X P W X X P
where β is the minimum signal-to-interference ratio (SIR), W is the ambient noise power level and α (α>2) is the attenuation factor.

Critical constraints and constructive scheme

The upper bound on random wireless multi-hop networks is generally limited by three constraints: 1) connectivity constraint to ensure that the network is connected, so that every source destination pair can successfully communicate, 2) interference constraint to compute the maximum number of simultaneous transmissions on the channel according to the interference model, and 3) destination bottleneck constraint to determine the amount of what can be received by a destination node.

The most common method [START_REF] Gupta | The capacity of wireless networks[END_REF][START_REF] De Moraes | Many-to-many communication: A new approach for collaboration in manets[END_REF][START_REF] Grossglauser | Mobility increases the capacity of ad hoc wireless networks[END_REF][START_REF] Jiang | On the asymptotic capacity of multi-hop mimo ad hoc networks[END_REF][START_REF] Kyasanur | Capacity of multi-channel wireless networks: Impact of number of channels and interfaces[END_REF][START_REF] Ozgur | Hierarchical cooperation achieves linear capacity scaling in ad hoc networks[END_REF][START_REF] Zhang | Capacity improvement of wireless ad hoc networks with directional antennas[END_REF][START_REF] Sharma | Delay and Capacity Trade-Offs in Mobile Ad Hoc Networks: A Global Perspective[END_REF][START_REF] Guo | On the capacity of κ-MPR wireless networks[END_REF] used in literature to determine the lower bounds on the capacity of largescale random wireless multi-hop networks is based on a constructive scheme. It consists of several steps and uses mathematical modeling. The first step is called network partitioning. It consists in dividing the unit sphere area into small polygons, called cells. Each cell can be a square, hexagon, regular polygon or irregular polygon as in the Voronoi tessellation. The shape of cells is important to control and capture the spatial node distribution. The size of each small cell should be cleverly designed so that the maximum data rate that can be received by the nodes inside the small cell can be computed exactly. Indeed, if the size of each small cell is set too large, then the maximum number of data streams that can be received by the nodes inside the square cannot be computed exactly. On the other hand, if the size of each cell is set too small, then the maximum number of data streams that can be received by the nodes inside the square is likely to be over-estimated, leading to a loose upper bound.

The second step is called interference management. It consists in bounding the number of interfering neighbors of each cell. This step allows traffic measurement on each cell and interference-free scheduling. Two cells are interfering neighbors if there is a point in one cell which is within the interference distance of some point in the other cells.

The third step is to define the scheduling method to avoid potential interference among active links. Most research work in this area considers the TDMA scheme due to its simplicity. Each cell becomes active, i.e., the nodes in the given cell can transmit successfully to nodes in the cell or in neighboring cells, at regularly scheduled cell time slots. The fourth step is to define the routes of a packet on the polygon tessellation. Generally, packets are routed through the cells that lie along the straight line joining the source and the destination node.

The last step is to calculate the expected routes that pass through a cell and infer the expected traffic of each node.

Throughput Capacity with SISO

In their seminal paper [START_REF] Gupta | The capacity of wireless networks[END_REF], Gupta and Kumar introduced a fixed random network model to study the throughput capacity of ad hoc networks. The capacity upper bound is determined using the three critical constraints (connectivity, interference and destination bottleneck). The capacity lower bound is by the following constructive scheme:

• Define the Voronoi tessellation (see figure 17); • Bound the number of interfering neighbors of a Voronoi cell. Two cells are interfering neighbors if there is a point in one cell which is within a distance of (2+∆).r(n) from some point in the other cell; • Bound the length of an all-cell transmission schedule. In the protocol model, there is a schedule for transmitting packets such that in every (1+c 1 ) slots, each cell in V n gets one slot in which to transmit; • Define the routes of a packet on the Voronoi tessellation;

• Prove that each cell contains at least one node; • Bound the mean number of routes that pass through a cell and infer the expected traffic of each node. Considerable attention has been devoted to improve Gupta-Kumar results by adopting the same modeling method. Grossglauser and Tse [START_REF] Grossglauser | Mobility increases the capacity of ad hoc wireless networks[END_REF] showed that under mobility constraints (uniform stationary distribution) a constant throughput scaling (Θ(1)) per source-destination pair is feasible. In [START_REF] Sharma | Delay and Capacity Trade-Offs in Mobile Ad Hoc Networks: A Global Perspective[END_REF] the authors study the throughput and delay trade-off. They use a unit torus area and square cells instead of a unit sphere area and Voronoi tessellation respectively. Other studies have examined the impact of multiple channels [START_REF] Kyasanur | Capacity of multi-channel wireless networks: Impact of number of channels and interfaces[END_REF], senderreceiver cooperation [START_REF] De Moraes | Many-to-many communication: A new approach for collaboration in manets[END_REF], K-MPRs [START_REF] Guo | On the capacity of κ-MPR wireless networks[END_REF], directional antennas [START_REF] Zhang | Capacity improvement of wireless ad hoc networks with directional antennas[END_REF], etc.

Throughput Capacity with MIMO

To determine the throughput capacity scaling laws for MIMO wireless multi-hop networks, the same modeling method developed for SISO systems can be extended by adding the MIMO physical layer capabilities (see section 2.2.2). Indeed, the amount of traffic in the network increases under the impact of spatial multiplexing and interference cancellation. A transmitter can send multiple independent data streams simultaneously on a link and multiple conflicting links can be cancelled out. Thus, the critical constraints and the corresponding constructive scheme need to be enriched, which is not a simple task. Due to this difficulty, only a few papers [START_REF] Bolcskei | Capacity scaling laws in MIMO relay networks[END_REF][START_REF] Chen | MIMO communications in ad hoc networks[END_REF][START_REF] Jiang | On the Asymptotic Capacity of Multi-Hop MIMO Ad Hoc Networks[END_REF] in literature analyze the asymptotic capacity lower and upper bounds of MIMO wireless multi-hop networks. In [START_REF] Bolcskei | Capacity scaling laws in MIMO relay networks[END_REF], the authors give a first study on how the capacity scales from a source node to a destination node over a sequence of intermediate relay nodes. In [START_REF] Chen | MIMO communications in ad hoc networks[END_REF], Jiang et al. extended the study to random multi-hop networks.

In [START_REF] Chen | MIMO communications in ad hoc networks[END_REF] authors have given an interesting study. To compute the lower bound on capacity of MIMO wireless multi-hop networks, they assume that all degrees of freedom resource at a transmitter node is allocated for spatial multiplexing. This means that the transmitting and receiving end of the conflicting links cannot cancel interference. For the upper bound, both spatial multiplexing and interference cancellation are considered to increase the overall capacity of the network. The main result obtained in [START_REF] Chen | MIMO communications in ad hoc networks[END_REF] is that MIMO systems can have a constant improvement M on asymptotic capacity compared to the results of Gupta and Kumar: where M is the number of antennas at each node. To validate the obtained results, figure 18 shows the capacity upper bound behavior. The capacity upper bound increases when the number of antennas increases and decreases when the number of nodes increases. There are still issues that remain unaddressed in capacity scaling laws for MIMO wireless multi-hop. Indeed, the impact of beamforming, spatial diversity, mobility, etc., remains unexplored. Critical constraints and constructive scheme should consider these new constraints.

Conclusion

In this chapter, performance models designed for wireless multi-hop networks are considered. We highlight and discuss the different aspects of multi-hop communication, and its introduction in next generation wireless networks. Two physical communication systems are studied: Single-Input Signle-Output (SISO) and Multi-Input Multi-Output (MIMO). In order to evaluate the performance of these systems, we have presented three modeling tools: i) stochastic modeling based on Markov-chain, ii) Conflict Graph particularly graph coloring, and cliques, iii) Asymptotic approaches for large-scale networks. Stochastic modeling based on Markov-Chain is mainly used to evaluate the performance of MAC protocol in terms of throughput, and delay. Conflict Graph is used to assess the network capacity in the case of multiple interference domains. Finally, asymptotic study for large-scale networks is presented and discussed in order to assess the upper and lower bands network capacity.

Figure 1 .

 1 Figure 1. An example of one hop communication versus multi-hop communication

Figure 2 .

 2 Figure 2. An Example of a VANET

Figure 3 .

 3 Figure 3. An Example of a WSN

Figure 4 .

 4 Figure 4. An Example of a MCN

Figure 5 .

 5 Figure 5. SISO system

Figure 8 .

 8 Figure 8. Beamforming

Fig. 9 .

 9 Fig.9. Markov Chain model for backoff algorithm (case of SISO)[START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]

  P] is the average packet payload size, T S is the average time the channel is sensed busy, T C is the average time the channel is sensed busy by each station during collision, and σ is the duration of one empty time slot.

  Fig. 10. Collision area in both cases: one-hop and multi-hop network

Figure 11 .

 11 Figure 11. Three-dimensional Markov chain for backoff algorithm (case MIMO)

Figure 12 .

 12 Figure 12. An example of a connectivity graph We use the conflict graph to model the interference relationships between links and called it the Links Conflict Graph LCG. Every link in connectivity graph G is represented by a node in conflict graph LCG. Two nodes in G are connected by an edge if the nodes corresponding to links in G cannot have simultaneous transmissions according to the protocol's interference model. For this purpose and as explained in [53], we use the following interference model: any link within distance H from (i,j) is a potential interfering link. This rule is called the distance-H interference model.

Figure 13 .

 13 Figure 13. LCGs for network topology Figures 13.a and 13.b show distance-2 and distance-4 LCGs for the network topology presented in figure 12.In the mathematical area of graph theory, a clique is a complete subgraph. A clique is maximal if it is not contained in another larger clique. In other words, a maximal clique cannot be extended by including one or more adjacent nodes. Determining maximal cliques in the clique graph will allow to determine the set of links

Figure 14 .

 14 Figure 14. Perfect and imperfect LCGs

Figure 15 .Figure 16 .

 1516 Figure 15. Sufficient conditions based on a perfect graph clique constraints

Figure 17 .

 17 Figure 17. A Voronoi tessellation of S 2

Figure 18 .

 18 Figure 18. Capacity upper bound of random wireless multi-hop networks

  for the study to illustrate the new performance model design. The SPACE-MAC protocol is a MAC layer asynchronous protocol design. It combines beamforming with spatial multiplexing and nulling as a multiuser technology. The basic idea is that all transmitter nodes that want to initiate a new transmission and all potential receivers must handle interference to or from already ongoing transmissions. To extend the Bianchi's model to the SPACE-MAC protocol, a new dimension should be added to express the spatial dimension of MIMO communication link. In this regard, two options are available: -Adding to each state of the Markov chain a new stochastic process, DoF j (t), representing the used DoFs for a node j at time t, where DoF j (t)∈[1,M], and M is the j's number of antennas; -Markov chain for each DoF. Figure11shows the incremental Bianchi's model. When a link is active, it can allocate all its DoFs for spatial multiplexing. Therefore, M data streams can be simultaneously transmitted on that link. Consequently, the normalized per-node throughput for MIMO networks S MIMO can be scaled at most by a factor of the maximum number of multiplexed data streams (M).

	We obtain
	S	MIMO	≤	M	×	1 (	-	tr P	) σ	+	tr S P P	S T tr S P E P [	P +	tr P ]	( 1	-	S P	) C T

Table 1

 1 summarizes the notation used for the link capacity estimation.

	Symbol	Definition
	G	the connectivity graph
	G-node	node in the connectivity graph
	G-link	link in the connectivity graph
	LCG	the link conflict graph
	LCG-node	node in the link conflict graph
	LCG-link	link in the link conflict graph
	Ci	the capacity of a link i within a SISO single-hop network
	Fi (t)	the instantaneous flow rate utilization on link i at time t
	Β	the scaling factor
	Qi	the incidence matrix of link i
	Γi	the available capacity on link i

Table 1 .

 1 Notation

  Gupta and Kumar have shown two main results:-Under the Protocol Model, the order of the throughput capacity is

	λ	(	) n Θ ⎜ ⎜ ⎝ ⎛ =	log W n	n	⎟ ⎟ ⎠ ⎞	bit/sec
	-Under the Physical Model,
	⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ λ λ	) ) n n ( (	= =	⎜ ⎝ ⎛ Θ ⎜ ⎜ ⎝ ⎛ Θ	⎟ ⎠ ⎞ log W n W n	bit/sec ⎟ ⎟ ⎠ ⎞ bit/sec n	otherwise feasible if

* Corresponding author. Tel.: +33-016-095-7737; fax: +33-016-095-7551.[START_REF]Mobile Ad hoc Networking (MANET) : Routing Protocol Performance Issues and Evaluation Considerations[END_REF] E-mail address: rachedi@u-pem.fr.


Steve Tonneau

Nicolas Mansard

Chonhyon Park
email: chpark@cs.unc.edu

Dinesh Manocha

Franck Multon
email: fmulton@irisa.fr

Julien Pettré
email: julien.pettre@inria.fr

A Reachability-based planner for sequences of acyclic contacts in cluttered environments

Multiped locomotion in cluttered environments is addressed as the problem of planning acyclic sequences of contacts, that characterize the motion. In order to overcome the inherent combinatorial difficulty of the problem, we separate it in two subproblems: first, planning a guide trajectory for the root of the robot and then, generating relevant contacts along this trajectory. This paper proposes theoretical contributions to these two subproblems. We propose a theoretical characterization of the guide trajectory, named "true feasibility", which guarantee that a guide can be mapped into the contact manifold of the robot. As opposed to previous approaches, this property makes it possible to assert the relevance of a guide trajectory without explicitly computing contact configurations. This property can be efficiently checked by a sample-based planner (e.g. we implemented a visibility PRM). Since the guide trajectories that we characterized are easily mapped to a valid sequence of contacts, we then focused on how to select a particular sequence with desirable properties, such as robustness, efficiency and naturalness, only considered for cyclic locomotion so far. Based on these novel theoretical developments, we implemented a complete acyclic contact planner and demonstrate its efficiency by producing a large variety of movements with three very different robots (humanoid, insectoid, dexterous hand) in five challenging scenarios. The planner is very efficient in quality of the produced movements and in computation time: given a computed RB-PRM, a legged figure or a dexterous hand can generate its motion in real time. This result outperforms any previous acyclic contact planner.

1 Introduction

State of the art

We consider the problem of planning the acyclic sequence of contacts describing the motion of a multiped robot in a cluttered environment. Acyclic contact planning is a particular class of motion planning where every configuration of the resulting trajectory must be in contact with the environment in order to support the balance of the system. The difficulty of the problem comes both in practice from the proximity to the obstacles (that tends to make the sampling of valid configuration tedious) and in theory from the foliation of the configuration space, where zero-measure manifolds intersect in a combinatorial manner [START_REF] Siméon | Manipulation planning with probabilistic roadmaps[END_REF]. Acyclic motion planning is a problem of interest in robotics, neurosciences and biomechanics. It is also interesting for virtual character animation, from where come early contributions were proposed. The first successful implementations come from local adaptation of motion graphs [START_REF] Kovar | Motion graphs[END_REF] and ad-hoc construction of locomotion controllers [START_REF] Pettré | A 2-stages locomotion planner for digital actors[END_REF]. These approaches can intrinsically not adapt to new situations or discover complex behaviors in unforeseen contexts. In robotics, the attention of the community first focused on the generation of cyclic locomotion patterns, in particular for bipedal walking on flat terrains [START_REF] Kajita | Biped Walking Pattern Generation by using Preview Control of Zero-Moment Point[END_REF]. While planning cyclic bipedal contacts is now mature, with existing real-time solutions [START_REF] Baudouin | Real-time replanning using 3D environment for humanoid robot[END_REF], the problem is mostly open for more generic acyclic contacts.

The issue of planning acyclic contacts was first completely described in [START_REF] Bretl | Free-climbing with a multiuse robot[END_REF], where it is proven to require the handling of two simultaneous problems: P 1 : a relevant guide trajectory for the root of the robot in SE(3); and P 2 : the planning of a discrete sequence of acyclic, balanced contact configurations along the trajectory. A key issue is to avoid combinatorial explosion when considering at the same time the possible contact configurations and the potential trajectories. This seminal paper proposes a first effective algorithm, able to handle simple situations (such as climbing scenarios), but not scalable to arbitrary environments. Following it, several papers have proposed practical contributions to apply this approach in particular situations, typically limiting the combinatorial by imposing a fixed set of possible contacts ( [START_REF] Hauser | Using motion primitives in probabilistic sample-based planning for humanoid robots[END_REF], [START_REF] Stilman | Global Manipulation Planning in Robot Joint Space With Task Constraints[END_REF]).

After [START_REF] Bretl | Free-climbing with a multiuse robot[END_REF], most of the papers have explored alternative formulations to handle the combinatorial issue. Two main directions have been explored. On one hand, local optimization of both the root trajectory P 1 and the contact positions P 2 has been used, to trade the combinatorial of the complete problem for a differential complexity, at the cost of local convergence. A complete example of the potential offered by such approaches is given in [START_REF] Mordatch | Discovery of complex behaviors through contactinvariant optimization[END_REF], with a successful adaptation to a real robot in [START_REF] Mordatch | Ensemble-CIO: Full-Body Dynamic Motion Planning that Transfers to Physical Humanoids[END_REF]. To keep reasonable computation times, the method uses a simplified dynamic model for the avatar. Still, the computation time is far from interactive (about 1 minute of computation for a sequence of 20 contacts). In [START_REF] Deits | Footstep planning on uneven terrain with mixed-integer convex optimization[END_REF] contact planning is formulated as a mixed integer problem, with computation costs similar to [START_REF] Mordatch | Discovery of complex behaviors through contactinvariant optimization[END_REF]. Aside from the computation cost, a major drawback of these optimization based approaches is that they only offer local convergence.

On the other hand, the two problems P 1 and P 2 might be decoupled to reduce the complexity. The feasibility and interest of the decoupling is shown in [START_REF] Escande | Planning Support Contact-Points for Acyclic Motions and Experiments on HRP-2[END_REF], by manually setting up a rough guide trajectory (i.e. an ad-hoc solution to P 1 ). P 2 is then addressed as the combinatorial computation of a feasible contact sequence in the neighborhood of the guide. A solution can then be found, at the cost of prohibitive computation times (several hours). Furthermore, this approach is suboptimal because the quality of the motion is conditioned by the relevance of the guide trajectory, which is not evaluated a priori. In [START_REF] Bouyarmane | Potential field guide for humanoid multicontacts acyclic motion planning[END_REF], the authors precisely focus on automatically computing a guide trajectory with guarantees of contact feasibility, by extending key frames of the trajectory into whole-body, balanced contact configurations. Randomly sampled configurations are projected into the contact submanifold using a generalized inverse kinematics solver, a computationally expensive process (about 15 minutes are required to compute a guide trajectory in the examples presented). Moreover this explicit projection is yet an insufficient condition and does not provide strong guarantees on the feasibility of the path between two key positions in the trajectory.

Paper contribution and organization

If the optimization approach is very promising, we are interested in this paper by the sample-based methodology, more able to find complex trajectories in cluttered environment. The theoretical structure of the problem is now well understood, however there is currently no scalable method to solve it. The combinatorial of the original problem (as described in [START_REF] Bretl | Free-climbing with a multiuse robot[END_REF]) is too high to have any hope of tackling it directly. Alternative formulations are necessary to obtain practical solutions. We believe that the separation, proposed in [START_REF] Escande | Planning Support Contact-Points for Acyclic Motions and Experiments on HRP-2[END_REF], between the guide trajectory and the contact sequence is the most promising direction. However, this direction opens two theoretical questions that remain to be solved, or even to be properly formulated:

• The guide trajectory must respect a property that guarantees the existence of a contact sequence to actuate it. 1 This property has not been studied yet; the only way on validating a trajectory was proposed in [START_REF] Escande | Planning Support Contact-Points for Acyclic Motions and Experiments on HRP-2[END_REF], by explicitly computing the contacts, which is computationally not reasonable. • There is in general an infinite combination of possible contact sequences for a given root trajectory. The selection of one particular contact sequence with interesting properties (minimum number of contact change, robustness, efficiency or naturalness) has been studied for cyclic cases, as in [START_REF] Hauser | Using motion primitives in probabilistic sample-based planning for humanoid robots[END_REF], but has not been efficiently applied to cluttered environments (e.g. [START_REF] Bouyarmane | Multi-Contact Stances Planning for Multiple Agents[END_REF] and [START_REF] Escande | Planning Support Contact-Points for Acyclic Motions and Experiments on HRP-2[END_REF] mostly randomly pick one contact sequence corresponding to the guide, obtaining possibly very tedious contact sequences). We claim that the desirable contact properties of a guide trajectory, proposed in [START_REF] Bouyarmane | Potential field guide for humanoid multicontacts acyclic motion planning[END_REF], can be formulated in a space of lower dimension, which we call C reach . This formulation can make the planning of a guide trajectory more efficient computationally, while providing equivalent guarantees than planning directly in the configuration space. Among the particular properties obtained when planning in C reach , we would like to guarantee that any reduced trajectory can actually lead to a feasible sequence of contacts: in which case, we say that the reduced trajectory is truly feasible. It is possible in theory to guarantee that any reduced trajectory is truly feasible, even if it is more efficient in practice to approximate this property. A second positive side effect of the true-feasibility of the guide trajectory is that we can now focus on the selection of one particular sequence of contacts, for example one that minimizes the number of contacts in the sequence or maximizes the robot efficiency or style.

Based on these fundamental observations, we have implemented a very efficient acyclic contact planner. Our method is based on a probabilistic roadmap (PRM), that computes offline guide trajectories that are approximately truly feasible. The planner then resolves online the contact sequence by refining a guide trajectory computed from the PRM. Our planner was able to compute physically-consistent contact sequences for very complex systems (a humanoid, 28 joints; and an insectoid, 48 joints) in a few seconds for classical scenarios like climbing, and less than a minute for very complex problems like egress of a damaged truck. The contact planner also generalizes to planning dexterous manipulation movements, as demonstrated by preliminary results.

The contributions of the paper are twofold. We propose the first theoretical characterization of today's most efficient practical approach to sampled-based planning of acyclic contacts. And based on this characterization, we propose a very efficient and general implementation of a acyclic contact planner, that outperforms all the previously demonstrated planners.

We propose a framework to address the motion planning problem for multiped robots in cluttered environments: given a start and a goal configuration, the objective is to compute a sequence of contact configurations allowing to achieve the motion. For instance, we can consider the task of standing up, illustrated in Figure 1-right. The problem is decoupled into two sequential phases: 1) the computation of a guide trajectory for the root of the robot; 2) the computation of a discrete sequence of contact configurations allowing to achieve the motion along the trajectory. The remain-1)

2) 3) 4) 5)

Fig. 2 Generation of a contact configuration for the right arm of a humanoid robot. 1) Selection of reachable obstacles. 2) A request is performed on a database of configurations. 3) Configurations too far from contact are eliminated. 4) The best candidate according to EFORT is chosen. 5) The final contact is achieved using inverse kinematics.

ing of this section presents the general organization of our method in Section 2. The two following sections 2 and 3 present respectively our answer to problems P 1 and P 2 . Finally, we propose a very complete experimental validation of the planner with three very different kinematic chains (humanoid, insectoid and three-finger manipulator) in various scenarios.

Computation of a guide trajectory

We first consider the problem of planning a relevant guide trajectory. The objective is to compute a trajectory of root placements which will allow contact creation. The stake of this first part is to preserve the completeness of the planner: the planner should be able to explore any possible guide trajectory, but at the same time, any computed guide trajectory must be truly feasible, i.e. must lead to a valid sequence of contacts. An intuitive description of such placements is to see them as "close, but not too close": close, because a contact surface must be partially included in the range of motion of the robot (represented for the right arm in Fig. 2-1); not too close, because the robot must avoid collision (which is represented by the hull including the torso in Fig. 2-1). We define formally C reach , the set of interesting root placements, in which we compute a guide trajectory with a sampling based planner, the reachability PRM (RB-PRM), is used (Figure 1-A). Planning in C reach boils down to planning in SE [START_REF] Baudouin | Real-time replanning using 3D environment for humanoid robot[END_REF], which has an acceptable practical complexity. Details are presented in Section 2.

Generating a discrete sequence of contact configurations

The second stage is to extend the guide trajectory into a sequence of contact configurations (Fig. 1-B). Thanks to the nice property that we manage to obtain for the guide, obtaining a random sequence of contact is an easy problem. The stake ∈ q 1 effector of this part is to select an efficient sequence, in particular by reducing the number of contact in the sequence. To create contacts in an efficient manner, we consider each limb as a manipulator attached to the root, and select the most relevant contact from a database of precomputed configurations (Figure 2). The relevance is defined as the contribution to the quasi static balance of the robot, and as the contribution to the motion of the root. This task efficiency is measured based on the Extended FORce Transmission ratio (EFORT), that we proposed in [START_REF] Tonneau | Using task efficient contact configurations to animate creatures in arbitrary environments[END_REF]. Details are presented in Section 3.

Notation conventions and definitions

A vector x is denoted with a bold lower case letter. A matrix A is denoted with a bold upper case letter. A set C is denoted with a upper case italic letter. Scalar variables and functions are denoted with lower case italic letters, such as r or f (x).

A robot is a kinematic chain R, comprising n + 6 degrees of freedom (DOFs). R is composed of l limbs R k , 1 ≤ k ≤ l, attached to a root. It is described by a configuration q ∈ SE(3) × R n . We define some relevant projections of q:

• q k denotes the configuration (a vector of joint values) of the limb R k (Fig. 3); • q k denotes the vector of joint values of R not related to R k . We define for convenience q = q k ⊕ q k ; • q 0 ∈ SE(3) denotes the position and orientation of the root of the robot R.

The environment O is defined as the union of the obstacles O i it contains. The volume encompassing the trunk of the robot is denoted W 0 (Fig. 3-right: central cylinder). The range of motion of a limb R k is denoted W k (Fig. 3-right: the four ellipses).

W k = x ∈ R 3 : ∃q k , p k (q k ) = x (1)
where p k denotes the end-effector position of R k (translation only) for q 0 the null displacement. We also define W = l k=1 W k . Finally, we define W k (q 0 ), 0 < k ≤ l as the volume W k translated and rotated by the rigid displacement q 0 .

Computation of a guide trajectory in C reach (Stage 1)

We consider the problem of computing a guide trajectory q 0 (t) : [0, 1] -→ SE(3) for the geometrical root of a multiped robot, connecting start and goal configurations. As said in previous section, the stake is to enforce that any configuration q 0 of the guide is truly feasible, i.e. can be mapped into a balanced configuration in contact. We denote by C contact ⊂ SE(3) × R n the contact submanifold of the robot. We say that a root placement q 0 is truly feasible if there exists q 0 such that

q 0 ⊕ q 0 ∈ C contact
The set of all truly-feasible root placements is denoted by C reach . By extension, a trajectory q 0 (t) is truly feasible if ∀t ∈ [0, 1], q 0 (t) ∈ C reach . We denote by π a function that associates to any truly-feasible q 0 a configuration of C contact (π might not be uniquely defined: it is the reciprocal of a projector).

π : q 0 ∈ SE(3) -→ q 0 ⊕ q 0 -→ C contact (2)
For a two-stage acyclic contact planner to be exact and complete, we need the combination of two conditions on a guide trajectory generator: all the generated trajectories must be truly feasible (sufficient condition); the guide planner must be complete, i.e. it must be able to discover any truly feasible trajectory (necessary condition)2 .

Conditions for true feasibility

By default, the true feasibility implies a constructive demonstration by exhibiting a valid q 0 . This is the approach chosen by [START_REF] Bouyarmane | Potential field guide for humanoid multicontacts acyclic motion planning[END_REF]. However, computing a valid q 0 is costly in practice. In this section we rather define a necessary condition and a sufficient condition for true feasibility that do not require this explicit computation.

True feasibility: necessary condition

For a contact to be possible, a volume O i ∈ O necessarily intersects with the range of motion W (q 0 ) (Fig. 2-1). Furthermore, if q 0 is truly feasible, then the trunk of the robot W 0 (q 0 ) is necessarily not colliding with the environment O.

Therefore we can approximate C reach with a set C reach ⊂ C 1 reach with the reachability condition defined as:

C 1 reach = {q 0 : W (q 0 ) ∩ O = / 0 ∧W 0 (q 0 ) ∩ O = / 0} (3)
It is straighforward to prove that C reach ⊂ C 1 reach (by construction of the included set). This inclusion is very important: it directly implies that any motion-planning algorithm with a guaranty of completeness in SE(3) × R n is complete in C reach × R n . This is a strong reduction of the search space, which can be directly applied to any existing method.

The condition C 1 reach is only necessary which means that one such root placement might not be truly feasible: in practice it is not guaranteed to find a valid sequence of contacts for every guide trajectory in C 1 reach .

Sufficient condition for true feasibility

In building C 1 reach , we directly considered the including hull of the root body W 0 , obtaining a necessary condition. A trivial sufficient condition for true feasibility can be constructed as a variation of it, by replacing W 0 with a bounding volume B max encompassing the whole robot in a given pose, except for the effector surfaces to be in contact 3 . We denote by C ∞ reach the set of root placement corresponding to the sufficient condition. Of course C ∞ reach ⊂ C reach . In general, the inclusion is strict, which means that we lose the completeness of the two-stage contact planner (i.e. the planner is not able to discover a trajectory for which the root remains inside C reach \C ∞ reach ). However, the sufficient condition is interesting since we can guarantee that any such trajectories lead to a valid sequence of contact.

Reachability: a compromise condition

The sufficient condition is not interesting in practice since it leads the solver to lose too many interesting trajectories. However, the necessary condition is not perfect neither, since the first stage of the planner would stop on a necessary guide that is not truly feasible in practice. It might be possible to find a shape B that is necessary and sufficient; however, it seems intuitively very unlikely in general (we were not able to find a counter-example). The construction of a shape W 0 ⊂ B ⊂ B max leading to necessary and sufficient condition (or the proof of its inexistence) is out of the scope of this work.

However between W 0 and B max , a trade-off can be found between a necessary and a sufficient condition. We define W 0 s as the volume W 0 subject to a scaling transformation by a factor s ∈ R + . We then consider the spaces C s reach C s reach = {q 0 :

W (q 0 ) ∩ O = / 0 ∧W 0 s (q 0 ) ∩ O = / 0} (4)
The higher s is, the closer the reachability condition is to being sufficient. When s = 1, the reachability condition is equivalent to the necessary condition. In practice, it is easy to adjust s to keep most of the interesting guides without introducing incorrect guides. The chosen s can then be statistically validated, as discussed in Section 4.

2.3

Computing the guide trajectory in C s reach with RB-PRM.

Once a value of s has been fixed, any sampling-based motion planner can be used to plan a trajectory in C s reach . We have chosen to implement RB-PRM as a variation of Visibility-PRM [START_REF] Nissoux | Visibility based probabilistic roadmaps[END_REF], which usually leads to a smaller set of nodes than classical PRM planners. The associated drawback is that the paths returned by the planner might not be the shortest ones, which is typically not an issue in highly cluttered environments.

To sample more efficiently configurations of C s reach , we bias the sampling process to generate near obstacles configurations, similarly to [START_REF] Amato | Choosing good distance metrics and local planners for probabilistic roadmap methods[END_REF] to generate configurations in narrow passages. First, a configuration is randomly set to a random point on the surface of one obstacle. The configurations are then translated and rotated randomly until the reachability condition is satisfied.

3 From a guide trajectory to a discrete sequence of contact configurations (Stage 2)

As an input of this stage, we consider a truly feasible guide trajectory q 0 (t) : [0, 1] -→ SE(3) for the root of the robot R. We now consider the second problem of computing a trajectory q 0 (t) of the limb of the robot. From the true feasibility, we know that such a trajectory exists. On the opposite to previous works [START_REF] Escande | Planning Support Contact-Points for Acyclic Motions and Experiments on HRP-2[END_REF][START_REF] Bouyarmane | Potential field guide for humanoid multicontacts acyclic motion planning[END_REF], the stake here is not to find such a trajectory but rather to select one with particular properties. In particular, we show here how to build a contact sequence with a small number of contact variations and good-efficiency and naturalness of the postures. More precisely, any projector reciprocal π introduced in (2) can be used to expand q 0 (t) into a whole-body trajectory. We propose here a particular construction of π leading to interesting contact sequences.

Extension of the guide trajectory

The guide trajectory q 0 (t) is first discretized into a sequence of j key placements:

1)
2) 3) 4)

Fig. 4 Contacts are maintained unless their position is too far, or the environment prevents it.

Fig. 5 Contacts are generated when the configuration is not balanced.

Q 0 = [q 0 0 ; q 0 i ; ..., q 0 j-1 ]

where q 0 0 and q 0 j-1 respectively correspond to the start and goal configurations. To ensure continuity in the contact transition phases, we rewrite π under the following recursive form for any 0 < i < j:

π : Q 0 -→ C contact q 0 i -→ q 0 i ⊕ g(q i-1 , q 0 i )
We initialize the recurrence with π(q 0 0 ) = q 0 the initial configuration of the robot. The function g is defined independently by g k for each limb R k . In defining g k , two aspects must be considered. Is the limb R k in contact? And which criteria is it optimizing? Maintaining a contact: If possible, a limb in contact at time i-1 remains in contact at i. The contact is broken if a direct projection of the current limb configuration to the nearest contact fails (due to joint limits or collision). Independently of whether R k is in contact or not, the limb configurations are selected to be the closest to the previous configuration (by minimizing p k (q i ) -p k (q i-1 ) ).

Once a first candidate configuration is taken for all limbs, the quasi-static balance is tested by checking that the weight wrench is in the contact friction cone, using the geometric approach described in [START_REF] Qiu | Human motions analysis and simulation based on a general criterion of stability[END_REF]. If the balance is not obtained, new contact are randomly generated using the following procedure.

Creating a contact: Consider a configuration where some limbs are in contact, some are free and the quasi-static balance is not enforced. A new contact configuration is obtained by projecting a random configuration to the nearest contacts. The sampling is biased by selecting configurations so that the limbs previously in contact are already close to contact and at least one additional limb is close to the environment. The random configuration is then projected onto the contact by itera-tively minimizing the distance between the end effectors and the environment, under the constraint of respecting the joint limits and avoiding the collision.

Contribution to the global movement: the EFORT criteria

EFORT criterion: If only relying on the random sampling to select new contacts, the planner would produce inefficient postures. The resulting contact sequence is then poorly efficient and is very unnatural. Moreover, the limbs are not efficiently configured and are not able to efficiently follow the general movement: contacts break very frequently.

When creating additional contacts, we therefore propose to select particular configurations that allow to exert a force compatible with the direction of motion. This task efficiency is measured with the Extended FORce Transmission ratio (EFORT) [START_REF] Tonneau | Using task efficient contact configurations to animate creatures in arbitrary environments[END_REF]. The measure of EFORT is given by

α EFORT (q k , m) = [m T (JJ T )m] -1 2 (ν 0 n T m) (5)
where J is the Jacobian matrix of the limb R k in configuration q k ; ν 0 is the friction coefficient of the contact surface; n is the normal of the contact surface; and m = -(q 0 i+1 -q 0 i ) is the direction opposite to the motion. The first part of the equation optimizes the ratio between the joint torque and the resulting force applied along m. The second part minimizes the odds of slipping while applying a force in the direction m. Optimization at creation: In practice, a database of configurations is stored for each limb, which can be considered as manipulator arm. The database is implemented as an octree data structure, indexed by the end-effector positions of the configurations (and additionally storing J). Upon request, the octree returns a set of configurations which are close to contact (Fig. 23). These candidates are sorted based on their task efficiency, given by α EFORT . The first candidate in this list which satisfies the balance criterion and is collision free is selected and is projected on the contact surface using an inverse kinematics solver.

Results

The main strength of our planner is that it efficiently works for arbitrary robot shapes. We first validate this aspect by producing a large variety of movements with three very different robots (humanoid, insectoid, dexterous hand) in five challenging scenarios. Two evaluations of the method are provided: qualitatively, by displaying the naturalness of the contact sequence in the companion video; and quantitatively by statistically measuring the validity of the compromise condition (Sec. 4.2) and the performances of the algorithms (Sec. 4.3). In all the scenarios considered, the formulation of the problem is always the same: a start and goal configuration are provided as an input of the scenario, and the framework outputs a sequence of statically balanced contact configurations connecting the start and goal configurations. A companion video available at http://youtu.be/LmLAHgGQJGA (anonymous link) displays the complete contact sequence obtained in all these scenarios. The video only renders the contact configuration (not the interpolation between contacts, which is out of the scope of the paper). Truck egress (humanoid and insectoid): The robot must leave a truck the doors of which are blocked: it has to crawl through the front window. Figure 7 presents the sequence of contacts obtained for both robots: RB-PRM can find solutions in highly cluttered environments with narrow passages. Climbing (humanoid and insectoid): The robot has to climb on a wall with several grasps disposed along it. In this scenario, we give stronger conditions for the sampled root placements: We require that more than one range of motion W k collide with obstacles of the environment. Fig. 8 presents the contact sequence obtained for both robots. In this case, the generation of the contact for the insect failed (due to the compromise criterion C s reach ).

Robot models and scenarios

Fig. 8 The computed sequence for the climbing scenario.

Manipulation of a pen (3-finger hand): This scenario is proposed to illustrate the genericity of our approach: we consider a manipulation task for a robotic hand and use our contact planner to compute a guide trajectory for the fingers, considered as effectors (Figure 9). Although we do not address the hard issue of accounting for rolling motions, the planner is able to compute the shown sequences, this in less than 5 seconds.

Other scenarios (humanoids): The standing-up scenario (already presented in Fig. 1) is a setup taken from [START_REF] Escande | Planning Support Contact-Points for Acyclic Motions and Experiments on HRP-2[END_REF]: it corresponds to a long narrow passage in the configuration space. In the crouching scenario, demonstrated in the companion video, the character automatically goes from a standing to a crouching position to crawl under an obstacle.

Parametrization of the reachability condition

To find the appropriate C s reach in which to sample the guide trajectory, we computed the rejection rate for various values of s for each robot in the most cluttered truck scenario. For a given value of s, 10 6 root positions and orientations are computed in C s reach . In each case we try to generate a collision free contact configuration, with a database comprising N = 10 5 sample configurations for each limb. The rejection rate is the ratio of between the number of failures and the number of trials. We can see that this rate decreases as s grows, as shown in Figure 10. For the humanoid, we chose s = 2.2, and for the insect, s = 2.8. Fig. 10 Rejection rates for the humanoid (orange) and the insectoid (blue) depending on s for the truck scenario.

Performance

The number of samples used for generating the contacts of each limb is 10000. Table 1 presents the average time (in seconds) spent in the different phases of the planner, for each phase and each scenario, as well as the number of contact phases of the sequence. We observe that many contacts are required for the insect, which can be explained by its restricted range of motion. The time spent generating the navigation graph can be approximated to one minute. The time spent in generating the graph of the climbing scenario, despite the relatively open environment, is explained by the additional restrictions imposed on the reachability condition. The difficulty to find a balanced configuration essentially influences the time spend generating the contacts.

The number of contact in the sequence gives a rough estimation of its duration in seconds. Except for the humanoids crawling out of the trucks, all the contact gener- ation are real-time: given a computed RB-PRM, a legged figure or a dexterous hand can generate its motion in real time. Aside from the quality of the generated trajectories observed in the video, this computation time is a major practical achievement.

Discussion and future work

In this paper we consider acyclic contact planning in cluttered environments, formulated as two sub problems that we address sequentially: P 1 : the computation of a guide trajectory for the root of the robot that can be extended ; P 2 : the computation of a discrete sequence of contacts along this trajectory. Our contribution to P 1 is a generic characterization of the properties that the guide trajectory must respect, in particular to enforce the completeness of the acyclic contact planner. We introduced a low dimensional space C reach which can be mapped into the contact submanifold of the robot, approximated and efficiently sampled by our Reachability-Based planner. Our contribution to P 2 is an pragmatic contact generation scheme which can take into account criteria to enforce interesting properties on the generated contacts (such as robustness, energy efficiency or naturalness). One such criterion, EFORT, is used to demonstrate the method and optimizes a force exertion compatible with the direction of motion. Aside from the theoretical contributions, we demonstrated that the results of our method outperform the previous approaches, allowing a very interesting compromise on three criteria which are hard to conciliate: genericity, performance, and quality of the solution. Regarding genericity, the reachability condition, coupled with an approach based on limb decomposition, allows the method to address arbitrary multiped robots. The only pre-requisite is the specification of the volumes W 0 which can be rigorously adjusted from a statistical analysis. Regarding performance, our framework outperforms existing methods in addressing either P 1 or P 2 , leading to computation cost close to real-time. Regarding the quality of the trajectories, a parametrization of the reachability condition allows us to compute relevant trajectories in all the scenarios presented, with low rejection rates. As for [START_REF] Bouyarmane | Potential field guide for humanoid multicontacts acyclic motion planning[END_REF], failures can still occur, due to the compromise criterion used in computing the guide trajectory.

Future work will focus on a more accurate formulation of C reach to address this limitation. Additionally, we will work on theoretically characterizing the benefits of using the EFORT criterion when generating the sequence (our understanding is yet only intuitive), and quantifying the reward it term of energetic efficiency or naturalness. Generating the complete motions, by interpolating between the computed contact sequences, is our logic next objective. This is a mandatory steps before going on the real robot. A reasonable approach is to search the optimal trajectory connecting two postures of the sequence, under the constraint of maintaining stability. In particular, we will consider optimization schemes based on reduced dynamic models, possibly extending the preliminary work of [START_REF] Audren | Model preview control in multi-contact motion-application to a humanoid robot[END_REF].

Fig. 1

 1 Fig. 1 Overview of our 2-stage framework. (A) Given a path request between the yellow and blue positions, a guide trajectory is computed in C reach using RB-PRM. (B) The trajectory is extended into a discrete sequence of contact configurations using EFORT.

Fig. 3

 3 Fig. 3 Left: Robot in a rest configuration. The right arm is denoted as the limb R 1 . Each colored dot represents a degree of freedom around an axis. Right: Volumes of the robot. The red geometry denotes W 0 and must remain collision-free. The green spheres are the W k .

Fig. 6

 6 Fig. 6 Robots and associated volumes: in red W 0 s ; in green the range of motion of each limb.

Fig. 6

 6 Fig. 6 describes the robot used in the experiments. The humanoid robot has four limbs, each with 7 DOFs. It has a total of 34 DOFs. The insectoid robot has six limbs, each with 8 DOFs, and a total of 54 DOFs. The hand has three fingers, each with 6 DOFs and a total of 24 DOFs.In all the scenarios considered, the formulation of the problem is always the same: a start and goal configuration are provided as an input of the scenario, and the framework outputs a sequence of statically balanced contact configurations connecting the start and goal configurations. A companion video available at http://youtu.be/LmLAHgGQJGA (anonymous link) displays the complete contact sequence obtained in all these scenarios. The video only renders the contact configuration (not the interpolation between contacts, which is out of the scope of the paper). Truck egress (humanoid and insectoid): The robot must leave a truck the doors of which are blocked: it has to crawl through the front window. Figure7presents the sequence of contacts obtained for both robots: RB-PRM can find solutions in highly cluttered environments with narrow passages.

Fig. 7

 7 Fig. 7 The computed contact sequences for the truck egress scenario. Only selected postures are shown for the insect.

Fig. 9

 9 Fig. 9 Contact sequence found for a pen manipulation in a zero gravity environment.

Table 1

 1 Average time (in seconds) spent in RB-PRM generation, and the online generation of the contact sequence.

		Generate RB-PRM	Generating the	Number of contact
		(offline)	contact sequence	states
	Truck egress (humanoid)	73	15	10
	Truck egress (insectoid)	70	23	48
	Climbing (humanoid)	25	5	15
	Climbing (insectoid)	21	27	51
	Crouching (humanoid)	5	6	22

This property is related to the controllability of the root actuated by the contact forces, but for discrete bounded properties.

The proof is immediate, using a contradiction approach.

This condition is trivial in the sense that the resulting W has a zero measure. Consequently the likelihood of randomly shooting a configuration with W in contact is null. For the need of the proof, the trivial sufficient condition is enough. In practice,the construction of a non-trivial including shape W 0 was possible for all the robot structures we considered, even if we cannot yet systematize the construction procedure.