Mohammad Daoud
email: mohammad.daoud@imag.fr

Christian Boitet
email: christian.boitet@imag.fr

Kyo Kageura

Asanobu Kitamoto
email: kitamoto@nii.ac.jp

Mathieu Mangeot
email: mathieu.mangeot@imag.fr

Daoud Daoud
email: daoud@batelco.jo

Building Specialized Multilingual Lexical Graphs Using Community Resources

We are describing methods for compiling domain-dedicated multilingual terminological data from various resources. We focus on collecting data from online community users as a main source, therefore, our approach depends on acquiring contributions from volunteers (explicit approach), and it depends on analyzing users' behaviors to extract interesting patterns and facts (implicit approach). As a generic repository that can handle the collected multilingual terminological data, we are describing the concept of dedicated Multilingual Preterminological Graphs MPGs, and some automatic approaches for constructing them by analyzing the behavior of online community users. A Multilingual Preterminological Graph is a special lexical resource that contains massive amount of terms related to a special domain. We call it preterminological, because it is a raw material that can be used to build a standardized terminological repository. Building such a graph is difficult using traditional approaches, as it needs huge efforts by domain specialists and terminologists. In our approach, we build such a graph by analyzing the access log files of the website of the community, and by finding the important terms that have been used to search in that website, and their association with each other. We aim at making this graph as a seed repository so multilingual volunteers can contribute. We are experimenting this approach with the Digital Silk Road Project. We have used its access log files since its beginning in 2003, and obtained an initial graph of around 116000 terms. As an application, we used this graph to obtain a preterminological multilingual database that is serving a CLIR system for the DSR project.

Introduction

Discovering and translating domain specific terminology is a very complicated and expensive task, because (1) it depends on human terminologists [START_REF] Cabré | Terminology: Theory, methods, and applications[END_REF], which increases the cost, (2) terminology is dynamic [START_REF] Kageura | The Dynamics of Terminology: A descriptive theory of term formation and terminological growth[END_REF], thousands of terms are coined each year, and

(3) it is difficult to involve subject matter experts in the construction process. That will not only increase the cost, but it will reduce the quality, and the coverage (linguistic and informational) of the produced term base. Databases like [START_REF]Inter-Active Terminology for Europe[END_REF][START_REF]United Nations Multilingual Terminology Database[END_REF][START_REF] Iec | [END_REF] are built by huge organizations, and it is difficult for a new domain with a smaller community to produce its own multilingual terminological database.

There is some work on constructing lexical resources by using Machine-readable dictionaries "MDRs" [START_REF] Gopestake | Acquisition of lexical translation relations from MRDS[END_REF] [START_REF] Helmreich | The use of machine readable dictionaries in the PANGLOSS project[END_REF], however for a domain-specific terminology, the involvement of the community and domain experts is essential, and associating several multilingual repositories into a specialized database may affect the integrity of the data and the domain relevance. TransGraph [START_REF] Etzioni | Lexical translation with application to image searching on the web[END_REF] is another attempt to associate various MDRs into a graph of words and its translations, effective for finding translation equivalences for general purpose lexical units. However, such a graph cannot handle relations between terms for a specific domain. Besides, MDRs do not suffice to determine such relations between lexical units available in the terminological sphere of a domain.

We are trying to analyze various resources in order to replace the traditional way of extracting related terminology. We introduce the concept of multilingual preterminological graphs, which are constructed by analyzing the interaction between domain-related resources on one side, and domain experts on the other side. Basically, we analyze the access log files to find important terms used to access the website, and relations between them. This approach falls under the category of implicit user contribution. reCAPTCHA [START_REF] Anh | Human Computation[END_REF] is an example of using this kind of contribution. After constructing the initial graph, we try to multilingualize it by using online multilingual resources at the beginning, and then by accepting progressive enhancements from community users in an explicit contribution approach.

Multilingual knowledge in a specific domain may not be available in any format (MDRs, printed dictionaries…). But such knowledge might be known and used by specialized multilingual people. We claim that discovering them, and encouraging them to contribute (explicitly and implicitly) is as important as discovering digital resources, or web services…

The remainder of this paper is organized as follows. The second section introduces the MPGs and the implicit and explicit approaches to construct them. The third section describes the extraction and contribution platform and its applications. Then section four reports the experimental results. And finally, section five draws some conclusions.

Multilingual Preterminological Graphs: Construction and Evolution

Definitions

We begin by describing multilingual preterminological graphs in detail, and present the approaches to initialize and multilingualize them. In an MPG the set of nodes N consists of p,l, s, occ, where p is the string of the term, l is the language, s is the code of the first source of the term, and occ is the number of occurrences. Note that l could be undefined. For example: N={[silk road, en, log],[Great Wall of China, en, ,wikipedia, 5], [ ,ا ar, contributorx,6]}, here we have three nodes, 2 of them are English and one in Arabic, each term came from a different source. Note that English and Arabic terms belong to the same N thus, the same MPG.

An Edge e={n, v} is a pair of nodes adjacent in an MPG. An edge represents a relation between two terms represented by their nodes. The nature of the relation varies. However, edges are weighted with several weights (described below) to indicate the possible nature of this relation.

The following are the weights that label the edges on an MPG: Relation Weights rw: For an edge e={[p1,l1,s1], [p2,l2,s2]}, rw indicates that there is a relation between the preterm p1 and p2. The nature of the relation could not be assumed by rw. Translation Weights tw: For an edge e={[p1,l1,s1], [p2,l2,s2]}, tw suggests that p1 in language l1 is a translation of p2 in language l2. Synonym Weights sw: For an edge e={[p1,l1,s1], [p2,l1,s2]}, sw suggests that p1 and p2 are synonyms. Weights are measures calculated based on (1) analyzing log files, (2) terminology extraction, (3) automatic lexical translation, and (4) volunteer contribution, as we will describe in the following subsections. A tedge is an edge where tw is more than zero, tdegree(n) is the number of tedges that connect to n. A redge is an edge where rw is more than zero, rdegree(n) is the number of regdes that connect to n.

Figure 1 shows a simple MPG. The shown nodes represents terms related to the historical Silk Road [START_REF] Ono | Memory of the Silk Road -The Digital Silk Road Project[END_REF]. For example, "inner Asia" and "middle Asia" are synonyms, so rw between them is 3 while tw equals zero. "Route de la soie" is the French equivalent of "Silk Road"; hence tw is more than 1.

Implicit Approach

Access log files constitute a very useful resource that is related to a specific domain, as they register the interactions between a domain-related online community on one side and users (who might include domain experts) on the other side. A server access log file keeps track of the requests that have been made to the server, along with other information like request time, IP address, referred page.

We analyze two kinds of requests that can provide us with information to enrich the MPG: (1) requests made to a local search engine devoted to a website and its documents, and (2) requests with reference from a web-based search engine (like Google, Yahoo!…).

From these requests we can obtain the search terms that visitors have used to access the website. Moreover, we can understand the way users interpret a concept into lexical units. Finding a pattern in their requests may lead to find a relation between the terms used in requests. For example, if we find that five different users send two consecutive search requests t1 and t2, then there is a possibility that t1 and t2 have a lexical relation.

As the pseudo code of "analysing_searchlogfiles()" illustrates we construct the initial MPG from access log files after filtering their records to find the search requests. The graph constructor analyzes the requests to make the initial graph by creating edges between terms available within the same session. The relation weight between x and y, rw(x,y), is set to the number of sessions containing x and y within the log file. For example, rw(x,y) = 10 means that 10 people thought about x and y within the same search session. Figure 2 shows an example of a log file and the produced graph. The proposed method did not discover the kind of relation between the terms. However it discovered that there is a relation, for example, three users requested results for "yang" followed by "yin" within the same session. Hence, edge with weight of 2 was constructed based on this fact.

analysing_searchlogfiles() for each search session of the log file Session n for each term n in Session i

if there is an edge between term i and term j then rw(term i , and term j )++; elseif there is no edge construct edge(term i , term j ); rw(term i , term j )=1;

Explicit Approach

Explicit user interaction is the intentional contribution from the community user. The motive to contribute is initiated by associating the contribution process to an interesting and attractive activity. User contribution C(x,y,s,t) will increase the confidence that x is a translation of y s is the source language and t is the target language. Hence, tw(x,y) (initialized at the multililingualization process) will be increased, accordingly. Accumulating the contributions will result in enlarging the graph and enhancing the confidence in its translation equivalences.

Graph Multilingualization

After constructing the initial MPG, we expand it by translating the terms using multilingual online resources. In the case of terminology, we are using Wikipedia [START_REF]Wikipedia[END_REF], IATE, and Google Translate [START_REF] Google | Google Translate[END_REF]. The choice of Wikipedia comes from the fact that it could be helpful for cultural terminology [START_REF] Jones | Domain-Specific Query Translation for Multilingual Information Access Using Machine Translation Augmented With Dictionaries Mined From Wikipedia[END_REF], as it is rich with proper names.

Each translation into each language is represented as a new node in the graph, an edge between the term and its translation is established, and tw (initially equals 0) is modified accordingly.

The translation weight between x and y equals the number of resources indicating that x is a translation of y.

Therefore, if tw(x,y) > k, where k is a confidence threshold, then x is a direct translation equivalence of y.

More generally, if there is a path p between x and y, where all edges on p have tw > k, then x is an indirect translation (see next subsections) of y.

Based on figure 1, if k=1, then " آ ا

" is an Arabic equivalent of "middle Asia" because tw is larger than 1.

Finding Synonyms

There are two kinds of information to indicate that two terms may be synonym in a graph. The first one is the rw between both of them, and the second is the number of translations overlapping the two terms. The second information was used by TransGraph to resolve word sense inflation. However, in a domain-dedicated terminology, the first information is very important to find that some terms represent the same concept. The following formula computes the new weights:

Where rdegree(x) is the number of edges that connect to x with rw > 0, and tdegree(x) is the number of edges that connect to x with tw > 0. For example, in figure 3, sw(X1, X2)=( 1/1+3/4)=7/4.

Indirect Translations

If the graph has a term t1 and its synonym t2, then edges with high tw can connect t1 to t2 and vice versa. In other words, t1 and t2 correspond to the same concept and it is possible that they have the same translations. We call this indirect translation because there is no direct edge between the term and translationally equivalent terms.

Therefore, x is an indirect translation of y, if x connects to x1, and there is a path p from x1 to y, where tw(x1,x) > k, k being a confidence threshold, and where all edges of p have sw > k1, k1 being a synonymy confidence threshold. For example, in figure 4, " ا "آ is considered as an Arabic translation of "central Asia" if k=1, and k1=1. This is because tw(" ا ,"آ middle Asia)=2, and sw(central Asia, middle Asia)=5/1+1=6, based on formula 1.

Platform

As figure 5 shows, the terminological lexical sphere for a domain, is constructed from different resources. And it is represented as an MPG, the MPG is used as it is for several applications that will serve the online community and the same applications are capable of attracting contribution.

The produced graph is represented as a GraphML file (graphml.graphdrawing.org). GraphML offers a structure that is compatible with MPG, and it can be easily produced by the system, adopting this format is important to make the graph more scalable and useful for other applications, beside many systems and tools have been developed to manipulate and visualize graphs in GraphML format.

The Case of the Digital Silk Road

The Digital Silk Road project [14] is an initiative started by the National Institute of Informatics (Tokyo) in 2002, to archive cultural historical resources along the Silk Road, by digitizing them and making them available and accessible online.

One of the most important sub-projects is the Digital Archive of Toyo Bunko Rare Books [15] where tens of old rare books available at Toyo Bunko library have been digitized using OCR (Optical Character Recognition) technology. The digitized collection contains books from different languages (English, French, Russian…), all of them related to the historical Silk Road, like the 2 volumes of the Ancient Khotan by Marc Aurel Stein.

We are trying to build a collaborative multilingual terminological database dedicated to the DSR project and its resources [START_REF] Daoud | A CLIR-Based Collaborative Construction of Multilingual Terminological Dictionary for Cultural Resources[END_REF]. To conduct such a study, there are two approaches, implicit and explicit, as described in [START_REF] Stermsek | A User Profile Derivation Approach based on Log-File Analysis[END_REF]. We used the implicit approach as we have the access log files of the website since 2003, which contain many interesting facts.

DSR-MPG is synchronized with a multilingual pre-terminological database pTMDB that interacts with users who search the data base and contribute.

Each term represented as a node in the graph corresponds to a record in the Solrbased index along with some useful term related and concept related information.

For a historical archive like the DSR, we find that reading and searching were the most important for users. Log files since 2003 show that 80% of the project visitors were interested in reading the historical records. Moreover, around 140000 search requests have been sent to the internal search engine. We are trying to derive indirect motivation to the pTMDB through the interesting resources of the DSR itself. So we implemented two applications (1) "contribute-while-reading" and ( 2) "contributewhile-searching", explained in the next subsection. They are available at http://dsr.nii.ac.jp/pTMDB/

Applications

Contribute While Searching

As shown in figure 6, historical physical books have been digitized and indexed into a SOLR-based search engine. Fig. 6. General architecture of the environment [START_REF] Daoud | A CLIR-Based Collaborative Construction of Multilingual Terminological Dictionary for Cultural Resources[END_REF] We expect users to send monolingual search requests in any language supported by our system to get multilingual answers. Having a term base of multilingual equivalences could achieve this [START_REF] Chen | Cross-Language Retrieval Experiments at CLEF[END_REF] [START_REF] Oard | Global Access to Multilingual Information[END_REF]. A bilingual user who could send a bilingual search request could be a valid candidate to contribute. In fact, the same bilingual request could be a valid MPG contribution, and also multilingual requests. We plan that users who use our search engine will use the DSR-pTMDB to translate their requests and will contribute to the graph spontaneously. During the searching process, the user can ask to add new translation if s/he was not happy with the suggested translation, by clicking on "Add Suggestions" to view the page showed at figure 9.

Contribute While Reading

The other interesting application is trying to help users from different linguistic backgrounds to translate some of the difficult terms into their languages while they are reading, simply by selecting a term from the screen.

As shown in figure 10, readers will see a page from a book as an image, with its OCR text. Important terms will be presented with yellow background. Once a term is clicked, a small child contribution/lookup window will be open, similar to the one in figure 9. Also user can lookup/translate any term from the screen by selecting it.

Experiment

To build the initial DSR-MPG, we used the access log files of the DSR website (dsr.nii.ac.jp) from December 2003 to January 2009. The initial graph after normalization contained 89,076 nodes; most of them being for English terms, we filtered the logs (semi automatically) to analyze only access requests with search queries, the initial graph was produced in less than 5 hours, using a PC with Intel Pentium 4 processor. We also sent the OCR text of the archived books of Toyo Bunko library to a term extraction engine, in this experiment Yahoo! Terms. We extracted 81,204 terms. 27,500 of them were new terms that were not discovered from the access log files. So, the total number of nodes in the initial graph was 116,576 nodes, see figure 11 for sample nodes. The important languages are the languages of the majority of the visitors, the languages of the archived books, and representative languages a long the Silk Road. DSR-MPG achieved high linguistic coverage as 20 languages have more than 1000 nodes on the graph.

To evaluate the produced graph, we extracted 350 English terms manually from the index pages of the following books:

• Ancient Khotan, vol. http://dsr.nii.ac.jp/toyobunko/VIII-5-B2-11/V-1 We assume that the terms available in these books are strongly related to the DSR. Hence, we tried to translate them into Arabic and French.

Figure 12 compares between DSR-MPG, and various general purpose dictionaries. Out of the 350 terms, we found 189 correct direct translations into Arabic. However, the number reached 214 using indirect translations.

On the other hand, the closest to our result was PanImages, which uses Wikitionaries [START_REF] Wikitionary | [END_REF] and various dictionaries, with only 83 correct translations. A comparison between DSR-MPG, and other dictionaries. The En-Ar bi-dictionary is Babylon [START_REF] Babylon | Babylon Dictionary[END_REF], and the En-Fr bi-dictionary was IATE DSR-MPG1 is the translations obtained from formula 1, DSR-MPG2 represents the translations obtained from indirect translations, which increased the amount of correct translation by 25 terms in the case of En-Ar.

The result can be progressively enhanced by accepting contributions from volunteers through the applications we described in the section three and the generic nature of MPG makes it easy to accept contributions from any dictionary or terminological database.

Conclusions and Perspectives

We described the explicit and implicit approaches that we are using to extract and discover domain dedicated terminology from human interaction with a related webcommunity. We presented a new lexical resource that can handle multilingual terms for a specialized domain. Multilingual Preterminological Graphs are constructed based on domain dedicated resources, and based on volunteer contributions. We described the approach for using access log files to initialize such graphs by finding the trends in the search requests used to access the resources of an online community.

Aiming at a standardized multilingual repository is very expensive and difficult. Instead of that, MPGs tries to use all available contributions. This way will enhance the linguistic and informational coverage, and tuning the weights (tw, rw, and sw) will give indications for the confidence of the translation equivalences, as the tedges accumulate the agreements of the contributors and MDRs (online resources).

We experimented the concept of MPGs on the domain of the historical Silk Road. We used the resources of the Digital Silk Road Project to construct a DSR-MPG and some applications that attract further contribution to the MPG. DSR-MPG achieved high linguistic and informational coverage compared to other general purpose dictionaries. Furthermore, the generic structure of the MPG makes it possible to accept volunteer contributions, and it facilitates further study of computing more lexical functions and ontological relations between the terms.

We are packaging the platform for constructing the DSR-MPG to be used in other domains as a tool for "Multilingual Terminology Elicitation" this platform will construct an MPG for a set of textual resources to collect its preterminology. Currently we are working on constructing an MPG for the domain of Arabic dreams interpretation, this MPG will serve a service for interpreting dreams (in Arabic), a beta version is available at this website [START_REF] Daoud | [END_REF]. Furthermore, we are investigating more scenarios of contribution to enrich the graph; one of them is based on playful methods using a game with a purpose (GWAP) [START_REF] Ahn | Games With A Purpose[END_REF] where users contribute to a knowledge repository while playing an online game, the knowledge repository in our case is a lexical graph.

Fig. 1 .

 1 Fig. 1. A small MPG A multilingual preterminological graph MPG(N,E) is a finite nonempty set N={n1,n2, …} of objects called Nodes together with a set E={e1,e2, …} of unordered pairs of distinct nodes of MPG called edges. MPG of domain X, contains possible multilingual terms related to that domain connected to each other with relations. A multilingual lexical unit and its translations in different languages are represented as connected nodes with labels.In an MPG the set of nodes N consists of p,l, s, occ, where p is the string of the term, l is the language, s is the code of the first source of the term, and occ is the number of occurrences. Note that l could be undefined. For example: N={[silk road, en,

Fig. 2 .

 2 Fig. 2. Example of constructing an MPG from an access log file

Fig. 3 .

 3 Fig. 3. An MPG where there is a possibility that X1 and X2 are synonyms

Figure 3

 3 Figure3shows that X1 and X2 have a relation rw and they have three shared translations. The probability that X1 and X2 are synonym increases if the number of translation overlaps is high, based on[START_REF] Etzioni | Lexical translation with application to image searching on the web[END_REF], and if the rw(X1,X2) is high, therefore we need to find a modified weight for synonyms.The following formula computes the new weights:

Fig. 4 .

 4 Fig. 4. An MPG with indirect translation

Fig. 5 .

 5 Fig. 5. Platform for constructing MPG

Fig. 7 .

 7 Fig. 7. A Japanese user translating his request As figure 7 shows, a Japanese user would translate the search request, to receive the results, as shown in figure 8.

Fig. 8 .

 8 Fig. 8. Search results

Fig. 9 .

 9 Fig. 9. Contribution page

Fig. 10 .

 10 Fig. 10. Translate while readingThis application helps covering all the important terms of each book.

Fig. 11 .

 11 Fig. 11. Sample nodes from DSR-MPG After the multilingualization process described in section 3, the graph has 210,781 nodes containing terms from the most important languages. The graph has now 779,765 edges with tw > 0.The important languages are the languages of the majority of the visitors, the languages of the archived books, and representative languages a long the Silk Road. DSR-MPG achieved high linguistic coverage as 20 languages have more than 1000 nodes on the graph.To evaluate the produced graph, we extracted 350 English terms manually from the index pages of the following books:• Ancient Khotan, vol.1: http://dsr.nii.ac.jp/toyobunko/VIII-5-B2-7/V-1/ • On Ancient Central-Asian Tracks, vol.1: http://dsr.nii.ac.jp/toyobunko/VIII-5-B2-19/V-1 • Memoir on Maps of Chinese Turkistan and Kansu, vol.1:http://dsr.nii.ac.jp/toyobunko/VIII-5-B2-11/V-1 We assume that the terms available in these books are strongly related to the DSR. Hence, we tried to translate them into Arabic and French.Figure12compares between DSR-MPG, and various general purpose dictionaries. Out of the 350 terms, we found 189 correct direct translations into Arabic. However, the number reached 214 using indirect translations.On the other hand, the closest to our result was PanImages, which uses Wikitionaries[START_REF] Wikitionary | [END_REF] and various dictionaries, with only 83 correct translations.

  1: http://dsr.nii.ac.jp/toyobunko/VIII-5-B2-7/V-1/ • On Ancient Central-Asian Tracks, vol.1: http://dsr.nii.ac.jp/toyobunko/VIII-5-B2-19/V-1 • Memoir on Maps of Chinese Turkistan and Kansu, vol.1:

  Fig. 12.A comparison between DSR-MPG, and other dictionaries. The En-Ar bi-dictionary is Babylon[START_REF] Babylon | Babylon Dictionary[END_REF], and the En-Fr bi-dictionary was IATE

Appendix: MPG as a GraphML

The following is a sample MPG in GraphML format:

-----XML STARTS--------------<?xml version="1.0″ encoding="UTF-8″?> <GraphML> <key id="d0″ for="node" attr.name="preterm" attr.type="string"></key> <key id="d1″ for="node" attr.name="language_code" attr.type="string"> <default>eng</default></key> <key id="d2″ for="node" attr.name="source" attr.type="string"> <default>unknown</default></key> <key id="d3″ for="node" attr.name="occ" attr.type="string"> <default>1</default></key> <key id="d4″ for="edge" attr.name="rw" attr.type="double"> <default>0</default></key> <key id="d5″ for="edge" attr.name="sw" attr.type="double"> <default>0</default></key> <key id="d6″ for="edge" attr.name="tw" attr.type="double"> <default>0</default></key> <graph isAcyclic="true" id="dsr" > <node id="2353″ > <data key="d0″>great wall of China</data> <data key="d1″>eng</data> <data key="d2″>dsr_log</data> <data key="d3″>11</data> </node> <node id="2354″ > <data key="d0″> ا ا ر </data> <data key="d1″>ara</data> <data key="d2″>wikipedia</data> <data key="d3″>3</data> </node> <node id="2355″ > <data key="d0″>万里の長城</data> <data key="d1″>jpn</data> <data key="d2″>dsr_log</data> <data key="d3″>4</data> </node> <node id="2356″ > <data key="d0″>Grande Muraille de Chine</data> <data key="d1″>fra</data> <data key="d2″>wikipedia</data> <data key="d3″>3</data> </node> <edge source="2353″ target="2354″> <data key="d4″>0</data> <data key="d5″>0</data> <data key="d6″>3</data> </edge> <edge source="2353″ target="2355″> <data key="d4″>1</data> <data key="d5″>0</data> <data key="d6″>2</data> </edge> <edge source="2353″ target="2356″> <data key="d4″>0</data> <data key="d5″>0</data> <data key="d6″>2</data> </edge> </graph> </GraphML> ---------XML ENDS------

The above XML graph corresponds to the graph in Figure 13.


Osman Akin

Kazakci

Thomas Gillier

Gerald Piat

Armand Hatchuel

Brainstorming versus creative design reasoning: a theory-driven experimental investigation of novelty, feasibility and value of ideas

In industrial settings, brainstorming is seen as an effective technique for creativity in innovation processes. However, bulk of research on brainstorming is based on an oversimplified view of the creativity process. Participants are seen as idea generators and the process aims at maximizing the quantity of ideas produced, and the evaluation occurs post-process based on some originality and feasibility criteria. Design theories can help enrich this simplistic process model. The present study reports an experimental investigation of creativity process within the context of real-life design ideation task. Results lead to the rejection of the classical 'quantity breeds quality' hypothesis. Rather, we observe that successful groups are the ones who produce a few original propositions that hold great value for users while looking for ways to make those propositions feasible.

Research problem: creativity beyond idea generation

Considering current economical and social challenges at the global scale, innovation is widely considered as a vital component of today's industry.

It is generally assumed that creativity is a main component in innovation processes. Based on these premises, an astounding amount of research has been undertaken on creativity techniques and processes since 1950's [START_REF] Diehl | Productivity loss in brainstorming groups: Toward the solution of a riddle[END_REF][START_REF] Stroebe | The illusion of group effectivity[END_REF][START_REF] Osborn | Applied Imagination, principles and procedures of creative thinking[END_REF][START_REF] Paulus | Enhancing ideational creativity in groups[END_REF][START_REF] Paulus | Group creativity: Innovation through collaboration[END_REF][START_REF] Mannix | [END_REF][START_REF] Summers | Creativity techniques: Toward improvement of the decision process[END_REF][START_REF] De Bono | The mechanism of mind[END_REF].

A technique that has received particular attention and acknowledgement is brainstorming [START_REF] Osborn | Applied Imagination, principles and procedures of creative thinking[END_REF]. Brainstorming is considered as an effective technique by professionals in overcoming particularly hard tasks that require creative insights [START_REF] Hurt | Better brainstorming[END_REF]. There is a large room for debates on this issue considering the conflicting results from research [START_REF] Diehl | Productivity loss in brainstorming groups: Toward the solution of a riddle[END_REF][START_REF] Stroebe | The illusion of group effectivity[END_REF] Since the pioneering work of Osborn [START_REF] Osborn | Applied Imagination, principles and procedures of creative thinking[END_REF], a significant amount of work has been undertaken to decipher this creative process and to provide control parameters and various extensions [START_REF] Paulus | Enhancing ideational creativity in groups[END_REF][START_REF] Paulus | Group creativity: Innovation through collaboration[END_REF][START_REF] Mannix | [END_REF]. Our main claim of about the existing research work is that they are working with an oversimplified (and implicit) process model for creativity process. Not only they lack rich definitions of creative behavior, thus reducing the phenomenon mainly to a simple idea generation phase, they also implicitly assume that the evaluation process can be dissected from the generation phase. Under such hypotheses, naturally, brainstorming research tends to evaluate output of a creative process by the quantity of ideas produced, making the assumption that quantity breed quality (Osborn, 1963).

Compared to brainstorming research, design research has focused in understanding the dynamics of creativity within design processes [START_REF] Goldschmidt | The dialectics of sketching[END_REF][START_REF] Gero | Modeling Creativity and Knowledge-Based Creative Design[END_REF][START_REF] Logan | Creativity and Design as Exploration, in Modelling creation and knowledge-based design[END_REF][START_REF] Goel | Design, Analogy, and Creativity[END_REF][START_REF] Dorst | Creativity in the design process: co-evolution of problem-solution[END_REF]. Arguably, design processes are most significant creative processes driving economic and social innovations [START_REF] Le Masson | Strategic management of innovation and design[END_REF]. As design research progresses towards maturity, several formal models and theories has been produced describing design reasoning leading to creativity [START_REF] Yoshikawa | General design theory and a CAD system[END_REF][START_REF] Takeda | Modeling design processes[END_REF][START_REF] Salustri | A formal theory for knowledge-based product model representation[END_REF][START_REF] Hendriks | Kazakci Imagining Future Knowledge, Logic and Interactive Rationality, The Institute for Logic, Language and Computation[END_REF][START_REF] Hatchuel | C-K design theory: an advanced formulation[END_REF][START_REF] Maimon | A Mathematical Theory of Design[END_REF][START_REF] Braha | Topological structures for modelling engineering design processes[END_REF][START_REF] Gero | Design prototypes: a knowledge representation schema for design[END_REF][START_REF] Kazakci | On the imaginative constructivist nature of design: a theoretical approach[END_REF]. The paper defends the thesis that such models would enable better-designed experiments to understand creative processes and would allow new predictions to be tested.

To demonstrate this concept, the current work reports an on-going exploratory investigation of a real-world design experiment. Ten teams of three people have been given an innovative design task (the design of an Antarctica-like museum) within the context of an industrial setting. Their reasoning processes have been analyzed using verbal protocol analysis. Two hypotheses, regarding the quantity of properties produced and the quantity of novel properties produced have been tested -both of which have been rejected, as predicted based on a particular model of design, namely, C-K theory. After reviewing brainstorming research in section 2, we introduce a creative design process description based on C-K design theory in section 3. Section 4 discusses methodology and data collection. Section 5 presents results, before concluding in section 6.

Brainstorming research

Overview

Focus of brainstorming research has been to increase number of ideas generated by groups [START_REF] Rietzschel | What are we talking about, when we talk about creativity? Group creativity as a multifaceted, multistage phenomenon[END_REF][START_REF] Reinig | On the relationship between idea-quantity and idea-quality during ideation[END_REF]. Initial research wanted to show that group creativity is better then same number of individuals (called nominal groups) working separately. Experiments have shown that nominal groups are much productive. A second episode of research on brainstorming tried thus to identify causes for this phenomenon. A number of factors such as the production loss, blocking, free riding, fear of evaluation have been identified [START_REF] Rietzschel | What are we talking about, when we talk about creativity? Group creativity as a multifaceted, multistage phenomenon[END_REF]. The natural tendency followed was to rectify this situation by eliminating these factors. Numerous techniques such brainwriting and anonymous evaluation has been proposed.

Evaluation of a creativity in brainstorming literature

Brainstorming research has accepted, often unquestioningly, a major hypothesis initially introduced by Osborn himself:

(QBQ) Quantity breed quality hypothesis: "It is almost axiomatic that quantity breeds quality in ideation. Logic and mathematics are on the side of the truth that the more ideas we produce, the more likely we are to think up some that are good. " (Osborn 1963, p. 131).

In the literature, this hypothesis has manifested itself as an evaluation process that is based essentially on the number of ideas. Literature often discusses criteria introduced early on [START_REF] Torrance | Guiding creative talent[END_REF][START_REF] Guilford | Creativity: Yesterday, today and tomorrow[END_REF] such as fluency, originality, and flexibility. Fluency is a quantity of the number of non-redundant ideas generated during the process Originality represents the uncommonness of an idea, given a problem, sometimes measured as the relative rarity of an idea given the pool of ideas produced by several participants for the same task [START_REF] Guilford | Creativity: Yesterday, today and tomorrow[END_REF][START_REF] Amabile | Creativity and innovation in organizations[END_REF]. Flexibility measures the ability to produce ideas that belong to uncommon categories of solutions given to the task at hand [START_REF] Torrance | Guiding creative talent[END_REF][START_REF] Guilford | Creativity: Yesterday, today and tomorrow[END_REF]. Research indicates that these dimensions can be co-related but it is not always the case. Some studies indeed report that fluency and originality are co-related (i.e. that QBQ is valid [START_REF] Diehl | Productivity loss in brainstorming groups: Toward the solution of a riddle[END_REF] but this is not always the case [START_REF] Förster | Temporal construal effects on abstract and concrete thinking: consequences for insight and creative cognition[END_REF] reports that previous work where both flexibility (number of categories used) and within-category fluency were present, no systematic correlation between the two was found [START_REF] Nijstad | Production blocking and idea generation: Does blocking interfere with cognitive processes[END_REF] indicating these measures might be inde-pendent. Although the literature consistently argues that total production is correlated with high-quality output

Feasibility vs. originality

Despite the previously mentioned criteria, in experiments, the production of an ideation process is usually measured based on a dichotomy of originality and feasibility. Rietschel et al. [START_REF] Rietzschel | What are we talking about, when we talk about creativity? Group creativity as a multifaceted, multistage phenomenon[END_REF] state that "individuals or groups that generate the most ideas, also generate the highest number of good ideas (with good ideas usually defined as ideas that score high on both originality and feasibility). As Rietschel and colleagues [START_REF] Rietzschel | Relative accessibility of domain knowledge and creativity: The effects of knowledge activation on the quantity and originality of generated ideas[END_REF] puts it there is a general agreement among brainstorming researchers that quality in creativity tasks is some combination of originality and feasibility. Measuring idea quality by having external judges rating the originality and the feasibility of the generated ideas, it is claimed that QBQ has been verified [START_REF] Diehl | Productivity loss in brainstorming groups: Toward the solution of a riddle[END_REF][START_REF] Rietzschel | Relative accessibility of domain knowledge and creativity: The effects of knowledge activation on the quantity and originality of generated ideas[END_REF].

Critics of idea evaluation in brainstorming

Contrary to mainstream brainstorming research, concerns have been raised in various research projects regarding the QBQ hypothesis and the evaluation process used in ideation tasks. After a comprehensive review of brainstorming research, [START_REF] Reinig | On the relationship between idea-quantity and idea-quality during ideation[END_REF] concludes that evidence on QBQ is not conclusive, or even conflicting.

Quantity is not the issue in real-life innovation processes

Williams and Sternberg [START_REF] Williams | Group intelligence: why some groups are better than others[END_REF] instructed teams of participants to produce a best idea ratter than as many ideas as possible. Contrary to usual work comparing nominal groups and interactive groups, they found out that teams were more successful in generating an overall superior idea than individuals. Their instruction clearly violated the QBQ hypothesis, while approaching a more realistic setting. As we shall argue later on, the objective of finding a best idea enforces the evaluation of ideas while they are being generated, rather than a pure generative process, the activity becomes a reasoned process. Rowatt et al. [START_REF] Rowatt | Perceptions of brainstorming in groups: The quality over quantity hypothesis[END_REF] demonstrated with a series of experiments that people have indeed a preference for quality over quantity. They interpreted their finding as a reason for revising brainstorming instructions to downplay the importance of quantity and emphasize the importance of quality. Paulus [START_REF]Paul Paulus on Group Creativity[END_REF] interpret this preference as fear for novelty and judging somewhat unfortunate that people tend to focus more on usefulness and validity.

Phased separation between idea generation and evaluation

Rietschel et al. [START_REF] Rietzschel | What are we talking about, when we talk about creativity? Group creativity as a multifaceted, multistage phenomenon[END_REF] acknowledge that idea generation is only a part of the creative process and not a goal in itself. However, their diagnostic for situating the dynamics of idea generation within the broader process share the same flaw many other brainstorming researchers: they make an implicit assumption that idea generation and evaluation are two separate processes: A question largely unaddressed by brainstorming research thus is how exactly the production of ideas contributes to creative solutions or innovations after the idea generation stage. [START_REF] Rietzschel | What are we talking about, when we talk about creativity? Group creativity as a multifaceted, multistage phenomenon[END_REF] Paulus [START_REF]Paul Paulus on Group Creativity[END_REF] argues that a lot of potential that is built up during the idea generation phase is wasted because people do not know how to evaluate ideas. Citing Rietzschel and colleagues [START_REF] Rietzschel | The selection of creative ideas after individual idea generation: Choosing between creativity and impact[END_REF], he states that idea generation is still an elusive issue for brainstorming research. Typically it is suggested that generation and selection should be two separate phases, but evidence thus far is not clear on this issue. Alternatively, it might be best to mix short idea generation sessions with evaluation sessions. This will be a puzzle for future research to resolve. As we shall see, this is far from being a puzzle but an elementary property of creative processes in design research.

Design theory and models: rich descriptions of creativity

Contrary to brainstorming research having strong relationship with experimental psychology literature, design research combined several methodological approaches to understand complex and real-life creativity situations that are design processes. One of the methodologies that have been used is theoretical modeling ( [START_REF] Yoshikawa | General design theory and a CAD system[END_REF][START_REF] Takeda | Modeling design processes[END_REF][START_REF] Salustri | A formal theory for knowledge-based product model representation[END_REF][START_REF] Hendriks | Kazakci Imagining Future Knowledge, Logic and Interactive Rationality, The Institute for Logic, Language and Computation[END_REF][START_REF] Hatchuel | C-K design theory: an advanced formulation[END_REF][START_REF] Maimon | A Mathematical Theory of Design[END_REF][START_REF] Braha | Topological structures for modelling engineering design processes[END_REF][START_REF] Gero | Design prototypes: a knowledge representation schema for design[END_REF][START_REF] Kazakci | On the imaginative constructivist nature of design: a theoretical approach[END_REF]. In the present work, we are going to consider a particular theory of design, namely the C-K theory [START_REF] Hatchuel | C-K design theory: an advanced formulation[END_REF]-and contrast it with the brainstorming underlying process model.

An overview of value, feasibility and originality in C-K theory

C-K theory describes design based on the interaction between two spaces. In the knowledge space, propositions about the known world exist. They are either true or false. In the concept space, there exist definitions for classes of objects. The theory claims that, in innovative design processes, those definitions are undecidable: it cannot be stated that corresponding objects can or cannot exist -until the end of design. In C-K theory creative propositions (and thus, originality) stems from a particular type of operation a designer applies in order to elaborate an undecidable propositions. This kind of operation, called expansive partitions or conceptual expansions, adds to a concept an unusual or unknown property in order to build new and unprecedented object definitions (e.g. an Antarctica-like mobile museum). A second type of operation, called restrictive partitions, adds to a concept a usual and known property (e.g. a history museum). Restrictive partitions does not necessarily create easy-to-realize object definitions, since creative design already starts with a conceptual expansionand the known property added by the restriction stills need to be connected with the unusual properties within the concept (e.g. an Antarctica-like mobile history museum). Although not explicitly stated by the theory, in practice it is often assumed that concepts hold value. Value is constructed progressively, extended if necessary, using partitioning (expansion or restrictions). Thus, conceptual expansions create or add new values to a type of object (e.g. an Antarctica-like mobile museum provides opportunity for children to be immersed into an Antarctica-like universe, not far from where they live).

There is no guarantee that a creative concept is going to be validated (i.e. acknowledged as feasible): concepts are validated if, during the process, knowledge warranting the existence of such an object is produced, activated or found. Expansive partitions, by definition, introduce originality into a design, but makes more difficult to validate a concept (i.e. to make it feasible).

Thus, in design, separation between the originality and the feasibility of a concept is not a problem; it is an opportunity to achieve both: a concept is unfeasible by nature (it contains creative expansions that makes it unfeasible). It is by the process of design that those concepts are made to exist. Thus, unfeasible yet original ideas cannot be discarded as invaluable or of poor quality. They allow the exploration of both value and feasibility.

Theory-driven predictions about brainstorming hypotheses

Based on the dynamics described by C-K theory, it is possible to produce and predict the outcome for a myriad of hypotheses about the dynamics of a design process and its impact on performance in terms of feasibility (F), originality (O) and value (V) of ideas. To demonstrate the approach, we shall introduce a second hypothesis. As mentioned earlier, the conceptual separation between idea generation and evaluation is a simplistic model that is bound to induce interpretation problems regarding the creative processes. Paulus [START_REF]Paul Paulus on Group Creativity[END_REF] states: People tend to focus more on usefulness and validity. There is clearly fear of novelty. This seems to assume that originality should prime over feasibility and value of ideas. We might formulate this hypothesis as quantity of novel (unknown) properties breeds quality:

(QNOQ) Higher the number of novel properties, higher the team performance C-K theories and more generally, work on design research goes clearly against this hypothesis. For instance, Girorta et al. [START_REF] Girorta | Idea Generation and the Quality of the Best Idea by girorta[END_REF] argue that organizations prefer a single outstanding idea to several good ideas. In design processes, the objective of finding a best idea enforces the evaluation of ideas while they are being generated -but the evaluation steps do not necessarily eliminates ideas. As C-K theory points out, new knowledge allowing further elaboration and improvement of those ideas are generated as well. As can be expected from such process, designers tend to generate sufficient number of original ideas that embodies value but they also need to make sure the feasibility of those ideas by elaboration. Brainstorming research, seeing the creative process as the generation of a sequence of unconnected ideas, misses this crucial insight. Thus, based on C-K theory's description of design process, QNOQ should prove to be false.

Research design and methodology

Overview

In order to address our research problem, we realized verbal protocol analyses of several design teams' creativity sessions. Our groups were composed of three designers with experiences in R&D activities. The creativity sessions were part of an innovative real-life project, supported by a French cross industry innovation partnership: In 2012, MINATEC IDEAs Labora-tory® decided to organize a series of innovative workshops involving multiple external professional designers. The sessions took place in a laboratory setting. Data were recorded and analyzed following the principles of verbal protocol analysis [START_REF] Dunbar | The in vivo/in vitro approach to cognition: the case of analogy[END_REF][START_REF] Ericsson | Protocol analysis[END_REF].

Our research question was to explore how design teams ideate when they need to elaborate breakthrough concepts. Contrary to research that mostly used case-study methodologies for understanding group creativity at the firm level, verbal protocol analysis permits tracking the team cognitive process in a more fine-grained level. More details about our protocol are being presented elsewhere [40]

Data collection

Research protocol of the innovative sessions

A. Participants and formation of design teams

The 30 participants were all either engineering designers or industrial designers with an average of 12 years of professional experience in R&D and innovation. Participants came from various industrial sectors and held different positions at the moment of the experiments: 10 were innovation managers, 11 engineering designers, 4 industrial designers, 3 industrial buyers and 2 B-to-B marketers. Not any participant had previous experience in the design of museum or in the creation of important public social events.

B. Presentation of the design brief

The ten design teams were assigned to elaborate a breakthrough museum concept that gives the visitor an immersive experience in an Antarcticalike world. The participants were asked to elaborate both the form and the functions of the museum, the architectural aspects and the possible museum activities. Additional requirements were the following:

-The museum aims to make people sensible to the imperative of protecting Antarctica. -The museum is mobile -it is a touring museum that could be deployed everywhere in the world whatever the conditions. -Practical and easy to install and transport.

-Eco-friendly as much as possible (ecological materials; energy harvesting solutions…) -The museum size is approximately 3600 m 2 . The topic of museum is simple and easily appropriable for the subjects. Because museums are a commonplace, all participants have some experience with them. The design brief is sufficiently open-ended; it offers the opportunity to investigate how design teams think in very different ways about different domains. Also, the object to be designed, by its very definition, is outside the scope of any known instance of its category.

C. Organization of the design sessions

At the start of each session, the design task was given to the design team. They were informed that they had one hour and thirty minutes to formulate one single concept of innovative museum. The design teams were asked to summarize their final proposal on an A3 sheet of paper with Design Computing and Cognition DCC'14. J.S. Gero (ed), pp. xx-yy. © Springer 2014 sketches, user scenarios, texts and motto. All experiments were launched in the same large room; table, white papers/papers, pencils were provided. Participants did not have any access to external documents (no computer, no internet connections, no books, no phone…).

At the end of each session, the participants were given 10 minutes to present their final product concept to the organizers. In order to cover all the aspects of the design proposals and to provide reliable and comparable qualitative data between the ten designs, a semi-structured guide was used to question them about their designs. All the experiments and interviews were video and audio recorded.

Research protocol of the ratings of the final designs

A panel of 14 professionals assessed the ten final designs -6 of them were experts in museum (2 directors of museum, 2 curators, 1 public programmer and 1 exhibition designer) and 8 of them were specialized in the organization of public events (1 director and 7 project managers). Judges were asked to rate the 10 final designs with 3 criteria according to a five level Likert scale:

novelty of the product concept compared to the existing museums -all kinds of museum could be considered (from traditional museums to innovative ones (planetarium, 3D-relief movies…)); -feasibility of the product concept in terms of how it can be implemented -economical and technical feasibility were ered ; -value for users; value of the product concept for potential visitors.

All judges were blind to the research. In order to increase the reliability of judges, the evaluation process was divided into 3 steps according to an adapted version of Delphi technique. In the first step, the rating criteria were presented and discussed by the judges. This aims to reduce the possible differences in the interpretation of the 3 criteria. Then, the final sketches of the 10 final design concepts were presented and each judge was asked to rate independently. Finally, the results of ratings were discussed in an unstructured form by the judges who could modify (or not) their initial ratings. Inter-rater reliability between the judges was measured. We use the inter-judge agreement reliability formula, called the Proportional Reduction Loss (PRL) of Rust and Cooil's [START_REF] Rust | Reliability measures for qualitative data: Theory and implications[END_REF]. PRL is proved to be of superior performance of several other reliability approaches for qualitative or quantitative data since it does not allow reliability to appear inflated. The inter-rater reliability was calculated for each of the criteria during both the first and second round of evaluation: PRL-originality (2 nd =.74;1 st =.71); PRL-feasibility (2 nd =.74;1 st =.71); PRL-value (2 nd =0.70;1 st = .71). All statistics show PRL ≥ 0.7 and so the internal consistency is largely acceptable.

Data analysis

Coding and analysis of the verbal protocols: processmeasures metrics

Verbal protocol analysis has been used to study the conversations and the different interactions between the participants. Teams activities were recorded and transcribed. Information regarding the identification of the speaker and the specific actions and reactions of participants (drawing, handling objects, jokes, laughing, mime…) were integrated into the transcripts. In total, the ten transcripts covering 15 hours of audiovisual data were used in the present analysis. The degree of verbalization varies between teams, number of words ranges from 12.500 to 23.000.

A. Coding of design properties: classic versus novel properties

Utterances from design teams have been used to capture various design properties they dealt with. All the design properties were then either coded as "known" or "unknown" by two experts. Known properties refer to classical properties of museums (i.e. restrictive partitions). Unknown properties are properties imagined by designers that do not correspond to any traditional properties of museums. During coding, a design property was considered to be known if it could be trivially observed in existing or past museums. Several documents about various types of museums (scientific, artistic, cultural, or historical) were considered -a specific attention was given to the website of the major museums dedicated to Antarctica, the museum of Artic and Antarctic in St Petersburg (Russia). In the case where an uttered design property was not usually encountered in museum, it was coded as an unknown property. For instance, the design properties "a museum that is a zeppelin" or "museum with ice footsteps sound effects" fall in this category.

B. Inter-rater reliability measures: Identification of properties

Two of the authors completed the coding of all the data independently and without communicating. Design properties were identified by highlighting each time they appeared in the transcribed data; the two coders individually named each design property, with its timestamp and the name of the designers. For coding, the software Atlas Ti (version 6.2, www.atlasti.com) was used. Afterwards, the two coders analyze and com-pare their coding segments side-by-side in order to validate (or not) their identification. The Percentage Agreement (PA) between the two coders for identifying the design properties was calculated for each team. While this method does not exclude agreements occurred by chance, it is simple and appropriate for exploratory conditions. For each transcript, the PA was calculated. The naming of design properties was discussed by the two coders. All the differences in the interpretations were resolved between the two coders. The overall average PA is 0.77. Such level shows that the identification of design properties can thus be considered fully acceptable and satisfactory (PA > .7). Inter-rater reliability between the two authors was measured for the full set of design properties. The PRL for each team reach a satisfactory level (> 0,7), in overall, the PRL was 0.75.

An overview of team performances

Table 1 and Figure 1 give insights into the nature of team performances.

Here, we can observe that there are four distinct categories of team performances. Teams #3 and #6 are the best teams overall. In particular, they have performed well both on criteria O and F. Teams #1 and #10 are the worst performing teams on both criteria compared to others. The remaining teams let appear two contrasted profiles. Teams #2, #8 and #5 are teams that have performed reasonably well (worst than the bests, better than the worsts). Their performance profiles are similar; they are all rather better on the feasibility criterion compared to originality. By contrast, teams #9, #7 and #4 (again worst than the bests, better than the worsts) did perform better on originality than on feasibility. When we consider the performances of these four categories of teams on the value criteria (Fig1b), we see that the bests and the worsts remain stable. Between the two remaining groups, the feasibility oriented group has performed slightly better with respect to value criteria than the originality oriented group. Different hypotheses that we are going to test give us a better understanding of these performances.

QBQ: Bigger the #Ps, better the team performance. In total, the ten design teams have generated 822 design properties (S.D. = 20.61). Table 1 gives the evaluation of experts for each group and table 2 gives three metrics (number of properties #Ps, number of unknown properties #UPs and number of known properties #KPs) and. There are several interesting consequences that can be drawn from this information. First, we see that the relationship between the number of (non-reduntant) properties and team performance is questionable. The top three generating teams are team #6, #5 and #8. Team #6 generated the highest number of design properties (125 design properties), well above the average (>82,2). Its performance appears to be well on originality and value criteria (3 rd in both).

Design Computing and

On feasibility criteria it's ranked 5 th . Its average ranks are rather good (2 nd on both O+F and O+F+V). This might tempt us to think that H1 is correct: the group that has generated the most ideas is a good group overall. Looking at the top 2 nd and 3 rd most generating teams (respectively, team #5 and #8), however, gives a clearer picture. Both have generated 95 ideas (again, well above the average). Team #5 has an unsteady performance profile (6 th on O, 2 nd on F and 5 th on V). This team has achieved particularly well on the feasibility criterion; however, its overall rank on O+F is just above average (4 th ). Team #8 has also an irregular performance (8 th on O, 4 nd on F and 2 th on V). This team has achieved particularly bad on the originality, but surprisingly, it has one of the best ranks in value criterion (2 nd ). However, both of its overall ranks are average at best (6 th on O+F and 5 th on O+F+V). Looking to the sporadic performances of these top-generating teams, QBQ cannot be confirmed clearly.

The least generative teams shed further light on QBQ. In fact, one of the two least generative teams, namely team #2, is the team with the highest performance on all criteria, thus, arguably the best team. They have only generated 60 ideas. This goes clearly against the QBQ. Let us remark that the opposite of the QBQ (the less the number of ideas, the better the quality) cannot be stated either. Team #1 and #4, two of the three least generative teams have arguably bad performances. Team #1, which generated 64 properties, has ranked 9 th or 10 th on all criteria. Team #4 has ranked 5 th , 7 th and 8 th on O, F and V. In sum, according to our dataset, there is no relationship between the number of generated Ps and the quality of Ps. Thus, we reject QBQ.

QNOQ: Bigger the #UPs, better the team performance. Let us consider QNOQ and the number of unknown properties (UPs) generated by the teams. The team that generated the most UPs is team #6, which is the same as the team that generated most Ps. It is indeed one of the best teams (2 nd both on O+F and O+F+V) 1 . The second best group on UPs ranking is team #5, which is also a good team in overall performance (4 th on O+F and 3 rd on O+F+V). Going to the opposite side, the two teams that generated the least UPs (team #4 and team #1) have poor performances overall (team #1 being the least good team in the experiment, and team #4 being 7 th on O+F and 8 th on O+F+V). Considering these, it is tempting to suspect a positive relationship between the number of UPs generated and the team performance. However, if we consider the third most and third least generative teams, the argument breaks down. In fact, once again team #1 who is the uncontested best on performance criteria is one of the least UPs generating team (ranked 3 rd ). Likewise, one of the worst teams, team #9 (8 th on O+F and 7 th on O+F+V), has ranked 3 rd according to the number of UPs generated, again going against the QNOQ.

Much as it is hard to confirm QNOQ with the available data, some variations of QNOQ deserve some attention. Let us consider:

-QNOQ': if a group's generation of UPs is below some threshold with respect to the average, it will have a bad performance. -QNOQ": if a group's generation of UPs is above some threshold with respect to the average, it will have a good performance. Although not conclusive from the current data, there is some evidence supporting these hypotheses. If we consider that the average UPs production is 51.20, we see that both most and least productive teams are beyond the edges of standard deviation (±16.25). Team #5 and #6 have both produced above 67.45 UPs and both have good performance. Team #4 and #1 have both produced below 40 UPs (slightly above μ-σ) have performed poorly. Considering the size of our sample and the performance of team #3 (which has also produced slightly above μ-σ but has best performance), this is still inconclusive. However, there is reason to check for QNOQ' and QNOQ" in future iterations.

Another way to consider QNOQ is from the performance charts (Fig 2). Here, we see that the top-performing group (Team #3 and #6) has a significant difference in terms of number of UPs produced. Likewise, the difference between the worst performing teams is considerable (Teams # 1 and #10). This variability in terms of number of UPs is also valid for the middle performance groups. Both the feasibility and the originality groups span widely along the number of UPs axis. In the light of these observations, it cannot be stated that QNOQ is a direct predictor of team performance.

Conclusions

The full set of results from our experiment is still being processed. The major result presented in the current work is the invalidity of QBQ hypothesis of brainstorming in our experimental setup based on a design creativity task. We also demonstrated that the number of original (unknown) propositions generated by a team is not predictor of high performance. An inspiring observation is that, groups that have achieved high on feasibility (from among the middle performance groups) are also better on value than the groups that have achieved better on originality. A possible explanation is that the groups that tend to have a few original UPs and that managed to ascertain feasibility of those outperformed groups that have only searched for originality. In our data, it would seem that a more balanced UPs and KPs generation allows higher originality. All the teams that ranked close to average (Teams #3, #7, #6, #9 and #4) have high originality scores. By contrast, teams that have ranked well on feasibility criterion are either a low or high ratio of UPs/KPs. It would seem, that having high originality with a balanced unknown generation strategy is not sufficient to obtain a high value or feasibility score. In future work, we shall analyze whether successful teams identify and work on the valuable and original ideas to guarantee their feasibility. This will require going beyond quantity-based metrics by introducing and analyzing process based metrics and their relationship with output proposals.

Fig1. 1

 1 Fig1. Comparison of team performances, on the left, feasibility vs. originality criteria; on the right, value vs. average of originality and feasibility Table1Team performances on O, F and VTeamOriginality (O) Feasibility (F) Value (V) Team #1 2.69 2.92 2.62 Team #2 3 4.08 3.31 Team #3 4.31 4.31 4.31 Team #4 3.62 3.15 2.77 Team #5 3.08 4.15 3.15 Team #6 3.92 3.92 3.31 Team #7 4.15 3.15 2.85 Team #8 2.77 4.08 3.46 Team #9 3.92 2.77 3.00 Team #10 2.54 3.15 2.69

Fig2.

  Fig2. Comparison of team performances based on #UPs, on the left, feasibility vs. originality criteria; on the right, value vs. average of originality and feasibility

Table 2

 2 Number of properties, unknown properties, known properties and their rations per teams

				# of	UPs/KPs Ra-	UPs/Ps Ra-
	Team	# of Ps	# of UPs	KPs	tio	tio
	Team #1	64	31	33	0.94	0.48
	Team #2	68	39	29	1.34	0.57
	Team #3	60	39	21	1.86	0.65
	Team #4	57	36	21	1.71	0.63
	Team #5	95	75	20	3.75	0.79
	Team #6	125	79	46	1.72	0.63
	Team #7	88	56	32	1.75	0.64
	Team #8	95	51	44	1.16	0.54
	Team #9	85	59	26	2.27	0.69
	Team #10	85	47	38	1.24	0.55

It should be noted, however, that their score on feasibility is average (5 th ) and thus, their being second in overall is mostly due to the compensatory nature of the averages (e.g. a bad score can be compensated by a good one, and vice versa).


R R Negenborn
email: r.r.negenborn@tudelft.nl

A G Beccuti
email: beccuti@control.ee.ethz.ch.

T Demiray
email: demiray@eeh.ee.ethz.ch.

S Leirens

G Damm

B De Schutter

M Morari
email: morari@control.ee.ethz.ch.

Supervisory hybrid model predictive control for voltage stability of power networks

Emergency voltage control problems in electric power networks have stimulated the interest for the implementation of online optimal control techniques. Briefly stated, voltage instability stems from the attempt of load dynamics to restore power consumption beyond the capability of the transmission and generation system. Typically, this situation occurs after the outage of one or more components in the network, such that the system cannot satisfy the load demand with the given inputs at a physically sustainable voltage profile. For a particular network, a supervisory control strategy based on model predictive control is proposed, which provides at discrete time steps inputs and set-points to lower-layer primary controllers based on the predicted behavior of a model featuring hybrid dynamics of the loads and the generation system.

I. INTRODUCTION

Huge problems in the US and Canada [START_REF] Morari | Canada Power System Outage Task Force[END_REF], Italy, and The Netherlands due to power outages have shown the crucial role of a reliable operation of electricity distribution and transmission networks. A reliable and efficient operation of these networks is not only of paramount importance when these electricity systems are pressed to their limits of its performance, but also under regular operating conditions. Due to the deregulation in the European electricity market, the number and variety of actors increases. This number will even further increase as also large-scale industrial suppliers and small-scale individual households (via solar energy or wind energy installations) will start to feed electricity into the network [START_REF] Jenkins | Embedded Generation[END_REF]. With this increasing complexity faults and disturbances causing voltage instabilities are likely to occur more frequently.

In general, the behavior of power systems is characterized by complex interactions between continuous dynamics and discrete events, i.e., power systems exhibit hybrid behavior. Components such as generators and loads drive the continuous dynamic behavior. They obey physical laws, and are usually represented by coupled differential and algebraic equations. Discrete events or discrete inputs cause discrete behavior through, e.g., breaking down or connecting of a transmission line, saturation effects in automatic voltage regulators and power system stabilizers, on or off switching of generators, connecting or disconnecting of loads, changing of transformer ratio settings, and connecting or disconnecting of capacitor banks; seasonal variations can also cause changes in power production capabilities as well as consumption and can modify the direction of power flows and thus cause switching behavior. The networks moreover typically span a wide range of time scales and large geographical areas.

To control such complex systems, hierarchical control in which control takes place at different layers based on space and/or time division is necessary [START_REF] Bernussou | Interconnected Dynamical Systems: Stability, Decomposition and Decentralisation[END_REF]. The controllers at the lowest layer act directly on the actuators of the physical system, employing faster and more localized control. Higherlayer controllers supervise controllers of lower layers by providing set-points or specifying constraints, employing slower and more overall control. The task of a higher layer is to steer the underlying layer in such a way that the performance of the physical system is optimal in some sense. Traditionally in hierarchical control, a layer either only provides continuous or only discrete values to a different layer. In the approach we propose, both continuous and discrete values are dealt with in an integrated way, i.e., we consider a hybrid approach.

The particular control problem we are dealing with is voltage stability after disturbances. After a disturbance, e.g., breaking of a transmission line, the generation and transmission network may not have sufficient capacity to provide the loads with power; voltage instability may be the result. Control actions have to be chosen that minimize negative effects of this voltage instability. Traditionally, offline static stability studies are carried out in order to avert the occurrence of voltage instability. The approach we propose is an application of online control that takes into account both the inherent temporal dynamics and that determines the most appropriate control sequence required to reach an acceptable and secure operating point. We consider a scheme used by a higher-layer controller that controls a power network to determine both discrete and continuous set-points for lower-layer controllers in such a way that negative effects due to voltage instability after disturbances are minimized. We hereby assume that a lower layer that accepts set-points at discrete time steps is already present. This paper is organized as follows. In Section II we introduce the power network and the lowest layer of control that we consider. In Section III we introduce the voltage control problem and the objectives. In Section IV we present a control strategy for the higher layer based on model predictive control. Section V contains simulation results obtained on the considered power network.

II. POWER NETWORK SYSTEM

A. Physical network

The case study under consideration is the 9 bus Anderson-Farmer network [START_REF] Farmer | Series Compensation of Power Systems[END_REF], depicted in Fig. 1, taken from the Dynamical Systems Benchmark Library1 , whereto the reader is referred for an exhaustive description.

B. Components of the network

The considered network consists of 4 generators G 1 , G 2 , G 3 and G 4 (shown with their nominal apparent power ratings) feeding the static loads at buses 5 through 9, where G 1 and G 4 and the loads connected to buses 5 and 9 are the aggregate representations for neighboring generators and loads. The synchronous machines are connected to the grid via lossless step-up transformers featuring a fixed turns ratio; a capacitor bank at node 7 provides additional reactive power to the system. The following list contains more details:

• Generators: Generators G 2 and G 3 represent single physical machines, whereas G 1 and G 4 denote the aggregate generators comprising several physical units. Therefore, G 2 and G 3 are described by a detailed sixthorder model [START_REF] Kundur | Power System Stability and Control[END_REF] including the mechanical equations and the electrical transient and sub-transient dynamics, whereas G 1 and G 4 are described by second-order mechanical dynamics [START_REF] Kundur | Power System Stability and Control[END_REF].

• Loads: The employed static loads comprise voltage dependent and constant impedance types [START_REF] Karlsson | Modelling and identification of nonlinear dynamic loads in power systems[END_REF]. The loads are described with following classical formulation in terms of active and reactive power

P h = s h P 0h v α h (1a) Q h = s h Q 0h v α h , (1b)
where h ∈ {5, 6, 7, 8, 9}, v h is the voltage of bus h, P 0h (Q 0h ) is the active (reactive) power steady-state value at node h, and s h ∈ {0, 0.02, . . . , 0.98, 1} per unit (p.u.) represents the discrete load shedding factor applied to a load to relieve the strain of the power demand on the

• Capacitor bank: The capacitor bank locally stabilizes bus voltages by injecting additional reactive power into the grid. It is represented as a (negative) purely reactive load of type (1b) with α = 2 and thus describes a switched shunt capacitor.

• Transmission lines: The transmission lines between the buses and components transfer the power from one location to another. The lines are represented by the π model for transmission lines [START_REF] Kundur | Power System Stability and Control[END_REF].

C. Primary control layer

In the network there is a primary, lower-layer, control layer that locally regulates power flows and voltage levels at the bus terminals of generators. Fig. 2 shows a schematic representation of the local controllers' principle of operation. Feedback variables and corrective actions are depicted for each component [START_REF] Kundur | Power System Stability and Control[END_REF]. The primary control layer consists of the following:

• Turbine governors: All generators feature a turbine governor (TG) controlling the mechanical power P m acting on the shaft of the machine in order to satisfy the active power demand of the network and maintain the desired frequency ω ref = 60 Hz. The TGs act on a time scale of tens of seconds.

• Automatic voltage regulators: All generators feature an automatic voltage regulator (AVR) maintaining the level of the excitation field E fd in the rotor windings at the value required to keep the bus (stator) voltage close to the desired set-point. Saturation is included in the AVR to account for the maximum allowable current in the excitation system, i.e., E fd has an upper limit value E max and a lower limit value E min . Once a machine has reached its saturation limit it cannot produce additional reactive power and can therefore no longer participate in sustaining the voltages in the network [START_REF] Kundur | Power System Stability and Control[END_REF]. The AVR voltage reference r i of generator i, i ∈ {1, 2, 3, 4}, can be set in the range 0.9 -1.1 p.u. with steps of 0.01 p.u. The AVRs act on a time scale of seconds.

Power System Stabilizer

Fig. 2. Scheme of primary controllers at a generator.

• Power system stabilizers: Generators G 2 and G 3 feature a power system stabilizer (PSS) eliminating the presence of unwanted rotor oscillations by measuring the rotational speed ω and adding a corrective factor v ref,PSS to the bus terminals' voltage reference v ref .

Generators G 1 and G 4 feature no power system stabilizer since the faster dynamics related to the rotor oscillations are not present in the related model equations. The PSSs act on a time scale of tenths of seconds.

D. Controls available to a higher control layer

Given the description of the network and the primary control layer, there is a number of controls available to a higher control layer in the form of set-point and reference settings. In particular the following can be adjusted:

• the voltage references for the AVRs;

• the mechanical power set-point for the TGs;

• the reference frequency for the TGs and PSSs;

• the amount of load to shed;

• the amount of capacitor banks to connect to the grid. Depending on the particular control problem a higher-layer controller will adjust the values of these controls. In particular for the problem at hand the amount of load shed (defined by the variables s h ) and the set-points of the AVRs (defined by the variables r i ) will be taken as the available controls.

III. EMERGENCY VOLTAGE CONTROL

A major source of power outages is voltage instability [START_REF] Cutsem | Voltage Stability of Electric Power Systems[END_REF]. Voltage instability in general stems from the attempt of load dynamics to restore power consumption beyond the capability of the combined transmission and generation system. Typically, the capability is exceeded following the outage of one or more components in the network, such that the system cannot satisfy the load demand with the given inputs at a physically sustainable voltage profile in the network.

The control problem involves the case of emergency voltage regulation, in which the power system is initially in steady-state operation and subsequently subjected to a fault, modeled as the partial or total outage of a line. Due to the reduced transmission capacity of the network the requested load demand together with the given system configuration place the grid under an excessive amount of strain, so that corrective actions are required to avoid that the induced transients drive the system to collapse or cause unwanted and hazardous sustained oscillations. More specifically, the control objectives are:

1) Maintain the voltages between 0.9 and 1.1 p.u., i.e., sufficiently close to nominal values to ensure a safe operation of the system by keeping it sufficiently distant from low voltages, which may lead to a collapse. 2) Effectively achieve a steady-state point of operation, while minimizing switching of the control inputs so that a constant and appropriate set of input values is ultimately applied to the power grid. For this second objective, in particular the option of shedding load is to be avoided unless absolutely necessary in order to fulfill the primary objective, as load shedding is the most disruptive countermeasure available.

IV. MODEL PREDICTIVE CONTROL

Model Predictive Control (MPC) [START_REF] Maciejowski | Predictive Control with Constraints[END_REF], [START_REF] Camacho | Model Predictive Control in the Process Industry[END_REF] has been traditionally employed in the process industry and has shown promising performance also for a variety of other control problems [START_REF] Morari | Model predictive control: past, present and future[END_REF]. The control action is obtained at each time step by minimizing an objective function over a finite horizon subject to the equations of the employed prediction model and the operational constraints, e.g., on inputs. The control problem is solved in a receding horizon fashion. The major advantage of MPC is its straight-forward design procedure. Given a model of the system, hard constraints can be incorporated directly as inequalities and one only needs to set up an objective function reflecting the control aim; soft constraints can also be accounted for in the objective by using penalties for violations.

A. Derivation of the prediction model

The performance of a predictive controller relies for a large part on the accuracy of the prediction model of the system. The prediction model has to describe well how the inputs affect the system behavior. Ideally a perfect model of the system would be used; however, such a perfect model can be very complex, thus making the optimization procedure in the controller slow. Instead, an approximation is used. If this approximation fits in a suitable form, relatively efficient optimization techniques can be used to determine the controls (e.g., linear or mixed-integer linear programming).

In order for the higher-layer controller that we are designing to meet its control objectives, it has to be able to predict how set-point changes influence the dynamics of the network. Therefore, the controller uses a model that includes both a representation of the physical network and a representation of the primary control layer.

The network, including the primary control layer, is expressed [START_REF] Kundur | Power System Stability and Control[END_REF] as a system of differential-algebraic equations (DAE)

ẋ = f (x, u, v) (2a) 0 = g(x, u, v) (2b)
where the state variables x are the generator dynamic variables, u denotes the system inputs, and the algebraic output variables v are the bus voltage magnitudes. The differential equations (2a) describe the synchronous machines and related primary controllers; the algebraic equations (2b) describe the classic load flow equations. See for the technical details on the power system models used the location specified in footnote 1.

Determining the evolution of the network given an initial state and input trajectory over the horizon thus requires the solution of this DAE. Solving DAEs in general is a complex task, in particular when dynamics of different time scales are present, as is the case for the power systems. Variable step size methods, e.g., DASSL [START_REF] Petzold | A description of DASSL -A differential/algebraic system solver[END_REF], are suitable for these cases, since they automatically choose a larger step size when no fast dynamics are present, and a smaller step size when they are [START_REF] Brenan | Numerical Solution of Initial-Value Problems in Differential-Algebraic Equations[END_REF]. However, using these methods inside the optimization procedure of the MPC controller could be very time-consuming and could thus result in very slow control. Therefore, such a DAE model is not directly suitable as prediction model.

Instead of taking the continuous-time DAE as prediction model, we consider a discrete-time linearized model derived from this DAE. At each discrete sampling instant kT s the continuous-time linearization of (2a) and (2b) around x 0 = x(k), u 0 = u(k -1), can be written as

ẋ = A c x + B c u + F c v = C c x + D c u + G c , where
A c = ∂f ∂x + ∂f ∂v (-∂g ∂v ) -1 ( ∂g ∂x ), B c = ∂f ∂u + ∂f ∂v (-∂g ∂v ) -1 ∂g ∂u C c = (-∂g ∂v ) -1 ∂g ∂x , D c = (-∂g ∂v ) -1 ∂g ∂u F c = - ∂f ∂v (- ∂g ∂v ) -1 ( ∂g ∂x x 0 + ∂g ∂u u 0 + ∂g ∂v v 0 -g(x 0 , u 0 , v 0 )) -( ∂f ∂x x 0 + ∂f ∂u u 0 + ∂f ∂v v 0 -f (x 0 , u 0 , v 0 )) G c = -(- ∂g ∂v ) -1 ( ∂g ∂x x 0 + ∂g ∂u u 0 + ∂g ∂v v 0 -g(x 0 , u 0 , v 0 ))
when ∂g ∂v is invertible, which is typically the case for power networks. The required Jacobians can either be derived analytically [START_REF] Leirens | A hybrid approach for voltage stability of power systems[END_REF] or computed numerically. For the sake of simplicity we use the latter approach.

We assume small variations of the variables around which the model is linearized. If the variations are not small, mode changes have to be considered in the model, e.g., by using piecewise affine or similar models [START_REF] Leirens | A hybrid approach for voltage stability of power systems[END_REF].

The continuous-time linearization is discretized with the sampling interval T s , to obtain the following control model in the affine expressions of x(k), u(k) and v(k)

x(k + 1) = Ax(k) + Bu(k) + F v(k) = Cx(k) + Du(k) + G (3)
wherein k denotes the discrete time step, and where

A = e AcTs B = Ts 0 e Acτ dτ B c F = Ts 0 e Acτ dτ F c C = C c D = D c G = G c .
The simulation sampling time T s is not necessarily equal to the controller sampling time, although in the following we will take these equal. The value of T s has to be chosen such that the discrete-time approximation adequately reflects the dynamics of the continuous-time linearized model.

The obtained discrete-time approximation is employed as a prediction model in the optimal control problem formulation. In this regard, the optimal control formulation must be augmented with the appropriate hard constraints on the inputs u(k) = [r(k) T s(k) T ] T , with r(k) = [r 1 (k), . . . , r 4 (k)] T and s(k) = [s 5 (k), . . . , s 9 (k)] T ), which are physically bounded. For r(k) the admissible range is simply taken to be the continuous relaxation of the discrete physical values, since adjusting AVR set-points is not invasive. However, load shedding is more invasive and since it is an extremely expensive control action such an approximation might not be adequate. Therefore, for s(k) the control constraints are taken as the actual discrete physically feasible values, at the cost of introducing a set of integer variables in the model; the employed control model is therefore by necessity hybrid in nature.

B. Optimal control problem

To account for the control objectives mentioned in Section III with their related order of importance a cost function is formulated similarly as in [START_REF] Geyer | Hybrid emergency voltage control in power systems[END_REF]. To maintain the voltages v 1 , . . . , v 9 between 0.9 and 1.1, let the auxiliary variables t j , j = 1, . . . , 9 defined by

   0.9 -v j (k) ≤ t j (k) -1.1 + v j (k) ≤ t j (k) 0 ≤ t j (k) (4)
denote upper bounds on the amount of violation of the voltage conditions. These upper bounds will be minimized. This formulation leads to nine variables at each sampling instant k, grouped in the vector t(k) = [t 1 (k), . . . , t 9 (k)] T .

To minimize the switching between control actions, define the variation of the manipulated variables as

∆u(k) = u(k) -u(k -1) = [∆r T (k), ∆s T (k)] T
and the diagonal penalty matrices

Q t = diag(q t1 , . . . , q t9 ), Q ∆u = diag(q ∆u1 , . . . , q ∆u9 )
with all penalty weights in R + and where the entries in Q t and Q ∆u are correlated to the corresponding ordering in t(k) and ∆u(k). Consider now the expression for the stage cost, penalizing the worst voltage violation and input change,

S(k) = Q t t(k) ∞ + Q ∆u ∆u(k) ∞
and the formulation of the cost function

J(x(k), u(k -1), U (k)) = N -1 ℓ=0 S(k + ℓ|k) (5)
which penalizes the predicted evolution S(k + ℓ|k) of S(k) at step k + ℓ using information available at step k over the interval

[k, k + N ].
The control action at each time instant k is obtained by minimizing the objective function (5) over the sequence of control inputs U (k) = [u T (k), . . . , u T (k + N -1)] T subject to the aforementioned input constraints and to inequalities (4) for the selected prediction model [START_REF] Bernussou | Interconnected Dynamical Systems: Stability, Decomposition and Decentralisation[END_REF]. Moreover, to reduce computational complexity, the load shedding control for the first prediction step only is computed, after which it is taken constant throughout the prediction horizon. The first step of the optimal sequence u * (k) thus obtained is then applied to the physical network after having rounded the AVR references to the nearest feasible value. The procedure is then repeated at the successive sampling instant k + 1.

Since we have a linear objective function with linear equality and inequality constraints, and since the decision variables are both continuous and discrete, the control law is the result of a mixed-integer linear programming problem, for which there exist good commercial and free solvers (such as, e.g, CPLEX, Xpress-MP, GLPK, lp solve, etc. [START_REF] Atamtürk | Integer-programming software systems[END_REF], [START_REF] Linderoth | Noncommercial software for mixedinteger linear programming[END_REF]).

V. SIMULATION RESULTS

A. Scenarios

We study two scenarios. Scenario 1 starts out from the system in steady state. At 0.7 seconds the line connecting G 4 , representing the largest generation capacity in the considered grid, to bus 9 changes (possibly due to a partial fault) so that its impedance increases to 150%. Fig. 3 shows the resulting open-loop evolution of the most important bus voltages. If no action is taken, voltages initially tend to progressively drift from the nominal region of operation until a series of sustained oscillations arises.

Scenario 2 involves a similar situation, only now the impedance increases to 400%, e.g., due to a forest fire. Fig. 5 shows the open-loop evolution if the higher-layer controller does not provide updated set-points to the lowerlayer primary controllers. As can be seen the voltages quickly reach a series of fast oscillations.

B. Controller setup

For our network the penalty matrices are chosen such that a weight of 200 is placed on the violation of each soft constraint; the inputs are weighted with the penalty coefficients 1 and 20 respectively for r(k) and s(k). The prediction horizon is N = 8. At each sampling instant, the linearization point is chosen by taking the current state x(k) and the input applied at the preceding time instant u(k -1). The sampling interval is taken to be T s = 0.25 seconds.

C. Results

Fig. 4 depicts for scenario 1 the evolution of the system when the proposed higher-layer MPC scheme is inserted in feedback. As shown the controller prevents the voltages from exceeding the upper and lower bounds by acting on the reference settings of all the AVRs. No load shedding is necessary. The system subsequently enters an acceptable steady-state condition with a constant input profile.

Fig. 6 depicts for scenario 2 the evolution of the system with the MPC controller installed. Although the fault is significantly larger, the control prevents the voltages from crossing their limits, by providing set-points for the AVRs and shedding a minimal amount of load at node 7. After about 20 seconds the system enters a new steady-state with constant input profile.

D. Discussion

The proposed controller works well for the studied cases, in which a rather high sampling rate of T s = 0.25 seconds was taken; indeed, this rate might have to be decreased in a more realistic setting, since the system is composed of large high-power components that may not allow for such a high actuation frequency. For the type of faults considered the simulations indicate that the predictions made with the linearized model are sufficiently accurate and that possible faults introduced due to saturation of the real system which are not modeled in the linearized system can be neglected. In fact, with a smaller fault, the sampling rate may be decreased, resulting in less frequent set-point updates to the

VI. CONCLUSIONS AND FUTURE RESEARCH

In this paper we have considered layered control of voltage instability in a particular power network. In this particular network a single higher-layer controller provides set-points to lower-layer controllers at discrete time steps such that the negative effects of voltage instabilities in the underlying physical system are minimized. The higher-layer controller uses a model predictive control strategy to determine its actions. It uses a model based on a discrete-time linearized model of the continuous-time nonlinear dynamics given by a system of differential-algebraic equations (DAE). Simulations illustrate the potential of this supervisory approach.

Future research will focus on investigating the region of validity of the linearized model and if necessary replacing this with piecewise affine models; performing simulations on a network in which the neighboring loads and generators are not aggregated, whereas the supervisory controller uses an aggregated model; comparing the proposed approach with an approach that uses variable time steps to make the predictions, instead of the fixed time steps used currently; assessing the real-time technical viability of the method; and, investigating decentralized control schemes where the local controllers of several subnetworks negotiate among themselves on how they should determine their actions to obtain system-wide optimal performance.

7

 7

Fig. 1 .

 1 Fig. 1.Graphical representation of the IEEE 9-bus Anderson-Farmer network.

Fig. 3 .

 3 Fig. 3. Evolution of voltages in open loop for scenario 1.

Fig. 4 .

 4 Fig. 4. Simulation results for scenario 1 in closed-loop control with the proposed MPC supervisor.

Fig. 5 .

 5 Fig. 5. Evolution of voltages in open loop for scenario 2.

  Evolution of voltages in closed loop.

Fig. 6 .

 6 Fig. 6. Simulation results for scenario 2 in closed-loop control with the proposed MPC supervisor.

URL: http://psdyn.ece.wisc.edu/IEEEbenchmarks/ system. Voltage dependent loads correspond to α = 1 and constant impedance loads to α =

ACKNOWLEDGMENTS

This research was supported by the project "HYbrid CONtrol: Taming Heterogeneity and Complexity of Networked Embedded Systems (HYCON)", contract number FP6-IST-511368, the project "Multi-agent control of large-scale hybrid systems" (DWV.6188) of the Dutch Technology Foundation STW, an NWO Van Gogh grant (VGP79-99), and the BSIK project "Next Generation Infrastructures (NGI)". We thank G. Hug-Glanzmann for her useful comments.