Abstract-Två former av samarbete i distribuerad problemlösning beaktas: uppgiftsdelning och resultatdelning. I den förra, noder hjälpa varandra genom att dela beräkningsbelastningen för utförandet av deluppgifter av det övergripande problemet. I den senare, noder hjälpa varandra genom att dela partiella resultat som bygger på något olika perspektiv på det övergripande problemet. Olika perspektiv uppstår eftersom noderna använder olika kunskapskällor (KS) (t.ex. syntax kontra akustik när det gäller talförståelsesystem) eller olika data (t.ex. data som uppfattas på olika platser när det gäller ett distribuerat avkänningssystem). Särskild uppmärksamhet ägnas kontroll och internodekommunikation för de två samarbetsformerna. För varje metod presenteras den grundläggande metoden och de system i vilka den har använts beskrivs. De två formulären jämförs sedan och de typer av ansökningar som de är lämpliga för beaktas. Jag. DISTRIBUTERAD PROBLEMSÖVERSKRIDANDE problemlösning är en samarbetslösning av problem genom en decentraliserad och löst sammankopplad insamling av kunskapskällor (KS) (förfaranden, uppsättningar av regler, etc.).), belägen i ett antal olika processornoder. KS samarbetar i den meningen att ingen av dem har tillräcklig information för att lösa hela problemet; ömsesidigt utbyte av information är nödvändigt för att gruppen som helhet ska kunna ta fram ett svar. Med decentraliserad menar vi att både kontroll och data är logiskt och ofta geografiskt fördelade; det finns varken global kontroll eller global datalagring. Löst kopplade innebär att enskilda KS: s tillbringar den stora andelen av sin tid i beräkning snarare än kommunikation. Distribuerade problemlösare erbjuder fördelar som hastighet, tillförlitlighet, extensibilitet, förmåga att hantera tillämpningar med en naturlig rumslig fördelning, och förmåga att tolerera osäkra data och kunskap. Eftersom sådana system är mycket modulära erbjuder de också begreppsmässig klarhet och enkelhet i designen. Även om mycket arbete har gjorts i distribuerad bearbetning, de flesta av ansökningarna har inte behandlat frågor som är viktiga för utformningen av artificiell intelligens (Al) problemlösare. Huvuddelen av manuskriptet mottogs till exempel den 28 januari 1980 och reviderades den 1 september 1980. Detta arbete stöddes av Kanadas försvarsdepartement, forsknings- och utvecklingsavdelningen, och behandlingen sker vanligen på en central plats med fjärrprocessorer som är begränsade till grundläggande datainsamling (t.ex. kreditkortsverifiering). Även om det är vanligt att distribuera data och behandling är det inte vanligt att distribuera kontroll, och bearbetningsföretagen samarbetar inte på ett substantiellt sätt. Forskare inom området distribuerad bearbetning har inte tagit problemlösning som sitt främsta fokus. Det har allmänt antagits, till exempel, att det finns ett väldefinierat och på förhand partitionerat problem och att den största oron ligger i en optimal statisk fördelning av uppgifter, metoder för sammankoppling av processornoder, resursfördelning och förebyggande av dödläge. Fullständig kunskap om timing och företrädesförhållanden mellan uppgifter har i allmänhet antagits, och den främsta orsaken till fördelningen har ansetts vara lastbalansering (se t.ex. [1], [3] ). Distribuerad problemlösning, å andra sidan, inkluderar som en del av sin grundläggande uppgift partitionering av ett problem. Den kanske viktigaste skillnaden mellan distribuerade problemlösningssystem och distribuerade bearbetningssystem kan hittas genom att undersöka systemens ursprung och motiven för sammankoppling av maskiner. Distribuerade bearbetningssystem har ofta sitt ursprung i ett försök att syntetisera ett nätverk av maskiner som kan utföra ett antal vitt skilda uppgifter. Vanligtvis är flera olika tillämpningar tänkta, med varje ansökan koncentrerad till en enda nod (som till exempel i ett trenode system avsett att göra lönekostnader, orderingång och processkontroll). Syftet är att hitta ett sätt att förena eventuella konflikter och nackdelar som uppstår till följd av önskan att utföra olika uppgifter, för att vinna fördelarna med att använda flera maskiner (delning av databaser, graciös nedbrytning, etc.). Tyvärr är de konflikter som uppstår ofta inte bara tekniska (t.ex. ordstorlekar och databasformat) utan inkluderar även sociologiska och politiska problem [6]. Försöket att syntetisera ett antal olika uppgifter leder till en oro med frågor som passerkontroll och skydd, och resulterar i att betrakta samarbete som en form av kompromiss mellan potentiellt motstridiga perspektiv och önskemål på nivå av systemdesign och konfiguration. Vid distribuerad problemlösning å andra sidan förutses en enda uppgift för systemet, och de resurser som ska tillämpas har inga andra fördefinierade roller att utföra. Ett system är konstruerat de novo, och som ett resultat kan hårdvara och programvara väljas med ett mål i 0018-9472/81/0100-0061$00.75 < 1981 IEEE 61 IEEE TRANSAKTIONER PÅ SYSTEM, MAN, OCH CYBERNETICS, VOL. SMC-I 1, NO. 1, JANUARI 1981 sinne: det urval som leder till den mest effektiva miljön för kooperativt beteende. Detta innebär också att samarbete ses i termer av välvilligt problemlösning beteende;-det vill säga, hur kan system som är helt villiga att anpassa sig till varandra agera så att vara ett effektivt team? Vårt bekymmer är därför att utveckla ramar för samarbetsbeteende mellan villiga enheter, snarare än ramar för att genomdriva samarbete som en form av kompromiss mellan potentiellt inkompatibla enheter. Detta leder oss att undersöka strukturen av interaktioner mellan samarbetande noder. Vi är främst intresserade av innehållet i den information som ska förmedlas mellan noder och användningen av informationen av en nod för samarbetsproblemlösning. Vi är mindre intresserade av den specifika form i vilken meddelandet genomförs. I detta dokument behandlas två former av samarbete i distribuerad problemlösning: uppgiftsdelning och resultatdelning. I den förra, noder hjälpa varandra genom att dela beräkningsbelastningen för utförandet av deluppgifter av det övergripande problemet. I den senare, noder hjälpa varandra genom att dela partiella resultat som bygger på något olika perspektiv på det övergripande problemet. Olika perspektiv uppstår eftersom noderna använder olika KS (t.ex. syntax kontra akustik när det gäller talförståelsesystem) eller olika data (t.ex. data som avkänns på olika platser när det gäller ett distribuerat avkänningssystem). För varje form presenteras den grundläggande metoden och de system i vilka den har använts beskrivs. Nyttan av de två formulären undersöks och deras kompletterande karaktär diskuteras. Den fysiska arkitekturen hos problemlösaren är inte av primärt intresse här. Det antas vara ett nätverk av löst kopplade, asynkrona noder. Varje nod innehåller ett antal olika KS. Noderna är sammankopplade så att varje nod kan kommunicera med varje annan nod genom att skicka meddelanden. Inget minne delas av noderna. Andra stycket ska ersättas med följande: MEDARBETANDE EXPERTER En välbekant metafor för en problemlösare som arbetar i en distribuerad processor är en grupp mänskliga experter som har erfarenhet av att arbeta tillsammans och som försöker slutföra en stor uppgift. Denna metafor har använts i flera Al-system [10]- [12], [18]. Av största intresse för oss när det gäller att undersöka hur en grupp mänskliga experter fungerar är hur de interagerar för att lösa det övergripande problemet, hur arbetsbördan fördelas mellan dem och hur resultaten integreras för kommunikation utanför gruppen. Det antas att ingen expert har total kontroll över de andra, även om en expert i slutändan kan vara ansvarig för att kommunicera lösningen av problemet på toppnivå till kunden utanför koncernen. I en sådan situation kan varje expert ägna större delen av sin tid åt att arbeta ensam med olika deluppgifter som har delats upp från huvuduppgiften, och då och då stanna upp för att interagera med andra medlemmar i gruppen. Dessa interaktioner inbegriper i allmänhet begäran om hjälp vid deluppgifter eller utbyte av resultat. Enskilda experter kan bistå varandra på minst två sätt. För det första kan de dela arbetsbördan mellan sig, och varje nod kan självständigt lösa vissa delproblem av det övergripande problemet. Vi kallar denna uppgiftsdelning (som i [11] och [18]). I detta samarbetssätt är vi i första hand intresserade av det sätt på vilket experter bestämmer vem som ska utföra vilken uppgift. Vi postulerar att en intressant metod för att åstadkomma detta avtal är genom förhandlingar. I det här avsnittet presenterar vi en modell för de faser som en distribuerad problemlösare går igenom när den löser ett problem ( Bild. 1).................................................................. Modellen erbjuder en ram för att förankra de två samarbetsformer som är huvudfokus i detta dokument. Det gör det möjligt för oss att se nyttan av de två formerna, de typer av problem för vilka de är bäst lämpade, och det sätt på vilket de kompletterar.2 I den första fasen bryts problemet ned i subproblem. Som Fig. 1 visar, nedbrytningsprocessen kan innebära en hierarki av partitioner. Dessutom kan själva processen distribueras för att undvika flaskhalsar. Dekomposition fortsätter tills kärnan (icke-dekomponerbara) underproblem skapas. Betrakta som ett exempel ett enkelt distribuerat avkänningssystem (DSS). I problem sönderdelningsfasen definieras och fördelas underproblemen med att upptäcka objekt i specifika delar av det totala intresseområdet bland de tillgängliga sensorerna. Den andra fasen innebär en lösning av kärnunderproblemen. Som framgår av figuren kan detta kräva kommunikation och samarbete mellan de noder som försöker lösa de enskilda underproblemen. I DSS-exemplet krävs kommunikation i underproblemlösningsfasen 1) om föremål kan flyttas från ett område till ett annat så att det är till hjälp för sensorer att informera sina grannar om rörelse av objekt som de har upptäckt, eller 2) om det är svårt för en enskild sensor att på ett tillförlitligt sätt detektera föremål utan hjälp från andra sensorer. Svarssyntesen utförs i den tredje fasen, det vill säga integrering av subproblemresultat för att uppnå en lösning på det övergripande problemet. Liksom problem sönderdelning, svar syntes kan vara hierarkisk och distribueras. I DSS 21t kommer att vara uppenbart att modellen också är tillämplig på centraliserad problemlösning. De olika faserna är dock mer uppenbara i en distribuerad problemlösare, främst eftersom kommunikation och samarbete måste behandlas uttryckligen i detta fall. Exempel, den svar syntes fasen innebär generering av en karta över objekten inom det övergripande området av intresse. För varje problem kan de tre faserna variera i fråga om komplexitet och betydelse. Vissa faser kan antingen saknas eller vara triviala. Till exempel, i trafik-ljus kontroll problem som beaktas i [13], problemet nedbrytningsfasen innebär ingen beräkning. Trafikljusstyrningar placeras helt enkelt vid varje korsning. För en DSS, problemet nedbrytning föreslås direkt av den rumsliga fördelningen av problemet.3 Det finns inte heller något svar syntesfas för trafik-ljuskontroll. Lösningen på ett kärnsubproblem är ett smidigt flöde av trafik genom den tillhörande skärningspunkten. Det finns ingen anledning att syntetisera en övergripande karta över trafiken. Lösningen på det övergripande problemet är alltså lösningen på kärnsubproblemen. (Detta gäller i allmänhet kontrollproblem; notera att det inte betyder att kommunikation mellan noderna som löser enskilda subproblem inte krävs.) Många sökproblem (som symbolisk integration [16]) innebär också en minimal svarssyntesfas. När problemet har dekomponerats in i underproblem i kärnan och de har lösts, är den enda svarssyntes som krävs en rekapitulation av listan över steg som har följts för att få fram lösningen. För vissa problem är dock den sammanfattande svarsfasen den dominerande fasen. Ett exempel är CONGEN-programmet [4]. CONGEN används för att förklara molekylstrukturen. Den genererar alla strukturella isomerer som överensstämmer med en given kemisk formel och som innehåller strukturella fragment som man vet förekommer i ämnet (superatomer). I problem sönderdelningsfasen, CONGEN genererar alla strukturer som är förenliga med data (genom att först generera mellanliggande strukturer, sedan sönderdela dessa strukturer, och så vidare, tills endast strukturer som innehåller atomer eller superatomer finns kvar). Vid denna punkt, superatomerna (som atomerna) betraktas endast vid namn och valence. I syntesfasen för svar ersätts superatomerna av de faktiska strukturella fragment som de representerar och är inbäddade i de skapade strukturerna. Eftersom inbäddning ofta kan göras på många sätt, en betydande del av den totala beräkningen redovisas i denna fas. Ett av huvudmålen med en distribuerad strategi är att lösa problem med hög hastighet. För att kunna göra detta måste man undvika situationer där processorer "kommer i vägen för varandra". Detta beror naturligtvis på själva problemet (t.ex., det finns problem för vilka data eller beräkning inte kan delas upp i tillräckligt mestadels oberoende bitar för att ockupera alla processorer). Prestanda beror dock också på problemlösningsarkitekturen. Det är därför lämpligt att överväga ramar för samarbete. 3Observera att problemlösaren fortfarande måste genomföra även en uppenbar nedbrytning. Noder måste fortfarande komma överens om vilken nod som ska hantera vilken del av det totala området. EEE TRANSAKTIONER PÅ SYSTEM, MÄNNISKOR OCH CYBERNETIKER, VOL. SMC-I 1, NO. 1 JANUARI 1981 Det är vanligt i Al problemlösare att dela upp expertis i domänspecifika KS, som var och en är expert på en viss del av det övergripande problemet. KS är typiskt formade empiriskt, baserat på undersökning av olika typer av kunskap som kan fås att bära på ett visst problem. I ett talförståeligt problem, till exempel, finns kunskap tillgänglig från talsignalen själv, från syntaxen av uttalandena, och från semantiken i uppgiftsdomänen [7]. Besluten om vilka KS:s ska bildas fattas ofta i samförstånd med bildandet av en hierarki av nivåer av dataabstraction för ett problem. Till exempel var de nivåer som användes i hierarkin för HEARSAY-II talförståelse systemet parametrisk, segmental, fonetisk, ytfonisk, stavabisk, lexical, Phrasal, och konceptuell [7]. KS:s är vanligtvis valda för att hantera data på en abstraktionsnivå eller för att överbrygga två nivåer (se t.ex. [7] och [15] ). Interaktioner mellan KS i en distribuerad processor är dyrare än i en uniprocessor eftersom kommunikation i en distribuerad arkitektur i allmänhet är mycket långsammare än beräkning. Samarbetsramen måste därför minimera kommunikationen mellan bearbetningsföretagen. Annars, de tillgängliga kommunikationskanalerna kan vara mättad så att noder tvingas att förbli sysslolösa medan meddelanden överförs.4 Som ett enkelt exempel på den svårighet som överdriven kommunikation kan orsaka, överväga en distribuerad processor med 100 noder som är sammankopplade med en enda sändningskanal. Anta att var och en av noderna fungerar på 108 instruktioner per sekund; beräknings- och kommunikationsbelastningen delas lika av alla noder, och problemlösningsarkitekturen är sådan att en bit måste kommuniceras av varje nod för varje tio instruktioner som den utför. Med dessa parametrar är det lätt att visa att kommunikationskanalen måste ha en bandbredd på minst 1 Gbit/s (även ignorera effekten av påstående för kanalen) [18]. Med en mindre bandbredd tvingas processorer stå sysslolösa och vänta på meddelanden. Det finns naturligtvis många arkitekturer som inte leder till kanalbandbredder av samma storlek. Poängen kvarstår dock att särskild uppmärksamhet måste ägnas internoden kommunikation och kontroll i distribuerad problemlösning om ett stort antal snabba processorer ska anslutas. Samarbetsramen måste också fördela bearbetningsbelastningen mellan noderna för att undvika flaskhalsar i beräkning och kommunikation. I annat fall kan den totala prestandan begränsas genom koncentration av oproportionerliga beräknings- eller kommunikationsmängder hos ett litet antal processorer. Det är också så att kontrollen av själva bearbetningen måste fördelas. Annars kan förfrågningar om beslut om vad du ska göra härnäst i tid 4Inriktningen här är på hastighet men de andra skälen till att anta en distribuerad strategi är också relevanta-tillförlitlighet (dvs. förmågan att återhämta sig från misslyckandet av enskilda komponenter, med graciös försämring i prestanda) och extensibilitet (dvs. förmågan att ändra antalet processorer som tillämpas på ett problem). ackumuleras på en "kontrollerande" nod snabbare än de kunde bearbetas.5 Distributionen av kontroll leder dock till svårigheter att uppnå globalt sammanhängande beteende eftersom kontrollbeslut fattas av enskilda noder utan fördelen av en övergripande syn på problemet. Vi kommer att illustrera detta problem i avsnitt VII. V. TASK-SHARING Task-sharing Task-sharing är en form av samarbete där enskilda noder hjälper varandra genom att dela beräkningsbelastningen för utförandet av deluppgifter av det övergripande problemet. Kontroll i system som använder uppgiftsdelning är typiskt målriktad; det vill säga den bearbetning som görs av enskilda noder är riktad för att uppnå delmål vars resultat kan integreras för att lösa det övergripande problemet. Uppgiftsdelning visas schematiskt i bild. 2............................................................... De enskilda noderna representeras av de uppgifter i vilka de utförs. Den viktigaste frågan som ska lösas vid uppgiftsdelning är hur uppgifterna ska fördelas mellan processorns noder. Det måste finnas ett sätt där noder med uppgifter som ska utföras kan hitta de mest lämpliga tomgång noder för att utföra dessa uppgifter. Vi kallar det här för kopplingsproblemet. Att lösa anslutningsproblemen är avgörande för att behålla fokus på problemlösaren. Detta gäller särskilt i Al-tillämpningar eftersom de i allmänhet inte har väldefinierade algoritmer för sin lösning. Den lämpligaste KS att åberopa för utförandet av en viss uppgift i allmänhet inte kan identifieras en priori, och det finns vanligtvis alldeles för många möjligheter att prova dem alla. I resten av detta avsnitt anser vi att förhandlingar är en mekanism som kan användas för att strukturera knutpunktsinteraktioner och lösa anslutningsproblemen i uppgiftsdelade system. Förhandling föreslås av iakttagelsen att anslutningsproblem också kan ses från perspektivet av en sysslolös nod. Den måste hitta en annan nod med en lämplig uppgift som är tillgänglig för utförande. För att maximera systemkonvergens, kan både noder med uppgifter som ska utföras och noder som är redo att utföra uppgifter fortsätta samtidigt, engagera varandra i en process som liknar kontraktsförhandling för att lösa anslutningsproblem. I avtalets nettometod för förhandling [18], [19], är ett avtal ett uttryckligt avtal mellan en nod om att 5Such a nod också skulle vara en risk för tillförlitlighet eftersom dess misslyckande skulle leda till ett totalt misslyckande i systemet. genererar en uppgift (ansvarig) och en nod som är villig att utföra uppgiften (entreprenören). (Fig. 3)............................................................... Tillgängliga noder (potentiella entreprenörer) utvärdera uppgifter meddelanden från flera chefer (Fig. 4) och lämna anbud på dem som de är lämpliga för (Fig. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. En enskild chef utvärderar anbuden och tilldelar kontrakt för utförandet av uppgiften till de noder som den avgör är mest lämpliga (Fig. 6 ) och 6 )............................................................................................................... Chefen och entreprenören är således kopplade till ett kontrakt (Fig. 7) Följande är ett exempel på förhandlingar för en uppgift som innebär insamling av avkännade data och utvinning av signalfunktioner. Det tas från en simulering av ett distribuerat avkänningssystem (DSS) [17]. Avkänningsproblemet är indelat i ett antal uppgifter. Vi kommer att överväga en av dessa uppgifter, signaluppgiften, som uppstår under initieringsfasen av DSS-operationen.6 6DSS i allmänhet är ett exempel på ett system som använder både aktivitetsdelning och resultatdelning. Uppgiftsdelning används för att initiera systemet (problem sönderdelningsfasen av Bild. 1 Cheferna för denna uppgift är noder som inte har avkänningskapacitet men har omfattande bearbetningskapacitet. De försöker hitta en uppsättning sensornoder för att förse dem med signalfunktioner. Sensorn noderna, å andra sidan, har begränsad bearbetningskapacitet och försök att hitta chefer som kan ytterligare bearbeta de signalfunktioner de extraherar från rå sensed data. Kom ihåg att vi ser nodinteraktion som ett avtal mellan en nod med en uppgift som ska utföras och en nod som kan utföra den uppgiften. Ibland skiljer sig perspektivet på avtalets ideala karaktär beroende på deltagarens synvinkel. Till exempel, ur signaluppgiftshanterarens perspektiv, har den bästa uppsättningen entreprenörer en tillräcklig rumslig fördelning kring det omgivande området och en adekvat fördelning av sensortyper. När det gäller potentiella leverantörer av signaluppdrag är däremot de bästa cheferna de närmaste, för att minimera potentiella kommunikationsproblem. Varje meddelandetyp i avtalsnetprotokollet har ankomst- och avgångstider för uppgiftsspecifik information. Slots har valts för att fånga de typer av information som med fördel passerar mellan noder för att bestämma lämpliga anslutningar utan överdriven kommunikation. Till exempel, signaluppgiftsmeddelanden inkluderar följande slots. 1) En task abstraction slot fylls med uppgiftstyp och position som chef. Detta gör det möjligt för en potentiell entreprenör att avgöra vilken chef den ska svara på. 2) I behörighetsspecifikationen anges att anbudsgivarna måste ha avkännande kapacitet och vara belägna i samma område som verksamhetsutövaren. Detta minskar den externa meddelandetrafiken och budhanteringen genom att uttryckligen ange egenskaperna hos en entreprenör som chefen anser vara väsentliga. 3) Innehållet i anbudsspecifikationen anger att en anbudsgivare måste ange sin position samt namn och typ på var och en av sina sensorer. Detta minskar anbudsmeddelandenas längd genom att ange den information som en chef behöver för att välja en lämplig uppsättning entreprenörer. De potentiella entreprenörerna lyssnar på uppdragsmeddelandena från de olika cheferna. Om de är berättigade svarar de till närmaste chef med ett bud som innehåller den information som anges i aktivitetsmeddelandet. Cheferna använder denna information för att välja en uppsättning anbudsgivare och sedan tilldela signalkontrakt. I meddelandena om tilldelning anges de sensorer som en entreprenör måste använda för att tillhandahålla signalfunktioner till sin chef. Användning av avtalsnet protokoll i en DSS gör det möjligt för sensorsystemet att konfigureras dynamiskt, med hänsyn till faktorer som antalet sensor och processor noder tillgängliga, deras platser, och den lätthet med vilken kommunikation kan fastställas. Förhandling erbjuder en mer kraftfull mekanism för anslutning än vad som finns i nuvarande problemlösningssystem. Den anslutning som sker med avtalsnetprotokollet är en förlängning till den mönsterriktade anrop som används på många AI programmeringsspråk (se [5] för en bild. 8............................................................... Resultatdelning. en fördjupad diskussion). Det är mest användbart när uppgifter kräver specialiserade KS, när lämpliga KS för en given uppgift inte är kända a priori och när uppgifterna är tillräckligt stora för att motivera en mer omfattande överföring av information innan åberopande än vad som i allmänhet är tillåtet i problemlösare. Resultatdelning är en form av samarbete där enskilda noder hjälper varandra genom att dela partiella resultat, baserat på något olika perspektiv på det övergripande problemet. I system som använder resultatdelning är kontrollen vanligtvis datariktad, dvs. den beräkning som görs när som helst av en enskild nod beror på de data som den har tillgängliga, antingen lokalt eller från avlägsna noder. En explicit hierarki av uppgift-subtask relationer existerar inte mellan enskilda noder. Resultatdelning visas schematiskt i bild. 8............................................................... De enskilda noderna representeras av KS. Ett enkelt exempel på användning av resultatdelning är utvecklingen av konsekventa märkningar för "blockvärldsbilder" [20]. En blockbild av världen är en linjeteckning som visar kanterna på en samling enkla objekt (t.ex. kuber, kilar och pyramider) i en scen. Varje bild representeras som en graf med noder som motsvarar hörnen på objekten i bilden och bågar som motsvarar kanterna som förbinder hörnen. Målet är att etablera en överensstämmelse mellan noder och bågar i grafen och faktiska objekt. En fysiskt realizable vertex kan ges en uppsättning av en priori möjliga etiketter baserat på antalet linjer som möts vid vertex och vinklarna mellan linjerna (t.ex., "L", "T", "Arrow" och "FORK") [20]. En vertex är ytterligare specialiserad på karaktären av de linjer som utgör den (t.ex., en linje kan definiera en konvex gräns mellan ytor av ett objekt, en gräns mellan ljus och skugga, och så vidare). Dessa märkningar upprättas genom att man undersöker hörnen isolerat. Ambitibilitet uppstår eftersom i allmänhet mer än en etikett är möjligt för varje vertex. Antalet möjliga etiketter kan dock minskas (ofta till en enda etikett) genom att man tar hänsyn till de begränsningar som uppstår genom samspelet mellan hörn som delar kanter i ett objekt. Mycket få av det stora antalet kombinatoriskt möjliga vertex typer kan dela en kant i ett fysiskt realizable objekt. Således nyckeln till att uppnå konsekvent bildmärkning är att jämföra etiketten uppsättningen av varje vertex med de av sina grannar och kassera inkonsekvent etiketter. Om vi partitionerar problemet så att en processor nod är ansvarig för en vertex i bilden, då den grundläggande resultatdelningsprocessen är uppenbar. Noder kommunicerar sina lokala etiketter med sina grannar. Varje nod använder dessa fjärretiketter tillsammans med konsekventa villkor för att beskära sin egen etikettuppsättning. Den sänder sedan den nya etiketten till sina grannar. Processen fortsätter tills unika etiketter har etablerats för alla noder eller ingen ytterligare beskärning är möjlig. (Denna process av iterativ förfining av etikettuppsättningar kallas avkoppling, begränsning förökning, eller räckvidd begränsning.)7 Bilda 9 visar en enkel bild av Waltz. Siffrorna visas i parenteser bredvid varje vertex indikerar antalet en priori märkningar möjligt för att vertex, i avsaknad av några intervertex begränsningar.8 Förutom den tvetydighet som uppstår i bilder från block världen, verkliga bilder lider också av tvetydighet som uppstår som ett resultat av bullriga data och felaktiga funktionsdetektorer. Bilden betraktas återigen som en graf, men i detta fall motsvarar noderna små regioner av bilden [2], [22]. Exempel på etiketter i detta sammanhang är linjesegment med angiven orientering eller objekt (t.ex. dörrar, stolar och papperskorgar). Liksom med blocken världsproblem, är målet att skapa unika etiketter för varje nod genom att överväga kontextuell information från angränsande noder. I detta fall är inga absoluta begränsningar möjliga. I stället ger begränsningarna (eller kompatibiliteterna som de också har kallats) uttryck för en viss grad av säkerhet om att de etiketter som är förknippade med angränsande noder är konsekventa (t.ex. har ett linjesegment med en viss inriktning som upptäcks vid en nod en hög grad av kompatibilitet med ett annat linjesegment med samma orientering som detekteras vid en angränsande nod). Metoden initieras genom att en uppsättning etiketter associeras med varje nod på grundval av lokal funktionsdetektering. Varje etikett tilldelas också en numerisk säkerhetsåtgärd. Eftersom uppdatering görs på grundval av de interaktioner mellan etiketter som beskrivs ovan, och stärker eller försvagar säkerhetsåtgärder för varje etikett.9 Denna process fortsätter tills unika etiketter har fastställts för alla noder (dvs. en etikett vid varje nod har en stor säkerhetsåtgärd med avseende på de som är förknippade med de andra etiketterna för den noden) eller ingen ytterligare uppdatering är möjlig. Bilda. 10 visar en urvalssamling av regioner av den typ som behandlas av MSYS [2]. För varje region visas möjliga tolkningar och deras sannolikheter på förhand. Dessutom visas de begränsningar som ställs på varje region som ska tolkas som en "stolsstol". Dessa begränsningar ökar säkerheten om att insamlingen av regioner bör tolkas som en ordförande. Lesser och Erman [14] har experimenterat med distributionen av HEARSAY-II talförståelsesystem [12]. Distributionen har utförts genom att dela upp varje uttalande i segment som överlappar varandra i tiden och tilldela varje segment en nod. Bilda. 11 visar den typ av segmentering som har genomförts. Varje nod försöker utveckla en tolkning av de uppgifter som den har tillgång till. Den gör detta genom att skapa partiella tolkningar eller hypoteser och testa dem för rimlighet i varje skede av behandlingen. (Detta är det klassiska Al paradigmet av hypothesize och test.) En lösning är konstruerad genom en stegvis aggregation av partiella lösningar som begränsar eller förstärker varandra, medan inkonsekventa partiella lösningar dör ut. Tentativa beslut är 9Exempel på uppdateringsalgoritmer ges i [23]. som gjorts på grundval av partiell information och sedan omvärderats när ytterligare information blir tillgänglig (antingen i form av mer data eller i form av partiella tolkningar som erhållits från andra noder). Begränsningar inom det talförståeliga området erbjuds av behovet av konsekvens i tolkningen av de överlappande segmenten och av de syntaktiska och semantiska begränsningar som en del av ett uttalande kan innebära för en annan del. De metoder som används av distribuerade HEARSAY-II är ganska lika dem som används i bildmärkningssystemen. Efter varandra följande förfining av hypoteser sker på ett sätt som liknar uppdateringen av etikettuppsättningar. Men bildmärkningssystemen uppnår samarbete enbart genom ömsesidig begränsning eller begränsning av de resultat som uppnås av enskilda noder. Distribuerad hörsay-II tar en mer allmän strategi. Det uppnår samarbete både genom ömsesidig begränsning och genom ömsesidig aggregering av resultat som uppnås av enskilda noder (dvs. partiella tolkningar som uppnås vid angränsande noder kombineras för att bilda mer fullständiga tolkningar). 0 I de första testerna har resultatdelningsmetoden i distribuerad HEARSAY-II visat en intressant förmåga att hantera tvetydighet och osäkerhet i data och kunskap. I en variation på standardsökning kontra kunskapsutbyte föreslår resultatdelning en aggregering kontra kunskapsavräkning: att samla partiella, inexakta lösningar kan ibland vara mycket lättare än att försöka; att producera en enda, komplett och exakt lösning, och kan i själva verket resultera i nästan ingen förlust av noggrannhet. VII. Första stycket ska ersättas med följande: TASK-SHARING OCH RESULTAT-SHARING: EN KOMPARISON Aktivitet-delning används för att organisera problem sönderdelning genom bildandet av explicit uppgift-subtask anslutningar mellan noder. Den resulterande hierarkin är också användbar som ett sätt att strukturera svarssyntesen. Aktivitetsdelning förutsätter att kärnans underproblem kan lösas av enskilda noder som arbetar självständigt med minimal internodkommunikation och att den största oron är effektiv matchning av noder och uppgifter för snabb problemlösning. Det är mest användbart för problemområden där det är lämpligt att definiera en hierarki av uppgifter (t.ex. heuristisk sökning) eller nivåer av data abstraktion (t.ex. ljud- eller videosignaltolkning). Sådana problem lämpar sig för att brytas ned i en uppsättning relativt oberoende deluppgifter "0Noder i ett resultatdelningssystem står inför ett anslutningsproblem som liknar det som beskrivs för uppgiftsdelningssystem. I resultatdelningsfallet måste en nod, bland alla resultat som genereras, välja de särskilda resultat som ska överföras samt de andra noder till vilka de ska överföras. På samma sätt måste en nod vid mottagandet av ett resultat avgöra om den ska godtas eller inte, och vilka åtgärder som ska vidtas på grundval av det erhållna resultatet. Dessutom kan vi i allmänhet inte anta att en nod bara kommer att kommunicera med sina grannar. Detta skulle utesluta möjligheten att lösa problem som innebär icke-lokala interaktioner mellan subproblem (t.ex. även om skuggregioner i block världen bilder kanske inte är intilliggande, måste de vara förenliga med sitt förhållande till källan till belysning). Problemet är att vi måste skilja mellan fysisk adjacency i kommunikationsnätet och kausal eller informations-irnpact adjacency. med litet behov av global information eller synkronisering. Enskilda deluppgifter kan tilldelas separata processornoder; dessa noder kan sedan utföra subtasks med lite behov av kommunikation med andra noder. Om så är fallet, då uppgiftsdelning är en tillräckligt kraftfull form av samarbete för att hantera alla tre faser av distribuerad problemlösning. Resultatdelning används för att underlätta subproblemlösning när kärnunderproblem är sådana att de inte kan lösas av enskilda noder självständigt utan betydande kommunikation med andra noder. Resultatdelning erbjuder ingen mekanism för problem sönderdelning. Därför kan det endast användas som en form av samarbete för problem där problem sönderdelning och distribution av subproblem till enskilda noder hanteras av en extern agent till den distribuerade problemlösaren. Resultatdelning erbjuder en minimal mekanism för svarssyntes. Det är lämpligt i detta avseende i den utsträckning som samma mekanism för fördelning av resultat kan användas för övergripande svarssyntes och underproblemlösning.'l Resultatdelning är mest användbar inom problemområden där 1) resultat som uppnås av en nod påverkar eller begränsar de som kan uppnås av en annan nod (dvs. resultaten är relevanta för varandra), 2) delning av resultat driver systemet att konvergera till en lösning på problemet (dvs. resultat som mottagits från avlägsna noder orsakar inte svängning), och 3) delning av resultat driver systemet till en korrekt lösning på problemet. Minimering av internoden kommunikation är viktigt för både uppgiftsdelning och resultatdelning former av samarbete på grund av beräkning / kommunikation hastighet obalans i distribuerade processorer. I avtalsnet protokollet används mekanismer som behörighetsspecifikation slot i uppgiftsmeddelanden för att minska främmande bud meddelanden, medan distribuerade HEARSAY-IT använder en rad intressanta mekanismer för att begränsa antalet hypoteser som kommuniceras mellan noder. En strategi är till exempel att endast överväga överföring av resultat för vilka ingen ytterligare förfining eller utvidgning är möjlig genom lokal bearbetning. (Denna typ av resultat har kallats "lokalt komplett" [14].) Det har tidigare sagts [13] att den största fördelen med resultatdelning är dess tolerans mot osäkerhet. Det är dock intressant att notera att uppgiftsdelning också kan användas för att uppnå tolerans mot osäkerhet. Överväg till exempel ett program där tre noder försöker uppnå en konsekvent tolkning av data som tas från överlappande delar av en bild. I en metod för resultatdelning försöker de uppnå samförstånd genom att meddela partiella tolkningar av uppgifterna. I en uppgift-delning strategi, de tre noder varje process sin egen del av Det återstår fortfarande problem med att besluta när man ska avsluta problemlösning aktivitet och besluta vilken nod kommer att meddela svaret till kunden utanför gruppen. I det distribuerade HEARSAY-II-systemet kommer alla noder så småningom att få en tolkning för hela uttalandet. Detta kan vara godtagbart för ett trenodssystem, men kommer att leda till en oacceptabel mängd kommunikation för ett större system. uppgifterna, men i stället för att kommunicera sina partiella tolkningar direkt till varandra, de kommunicerar dem till en fjärde nod (en förvaltare i kontrakt netto termer) som har till uppgift att reda ut inkonsekvenserna. Denna nod upprepar regelbundet de tre andra noderna, med hjälp av de mest aktuella data och partiella tolkningar.'2 Detta korta exempel visar på en stor skillnad mellan de två strategierna, nämligen att resultatdelning är en mer implicit form av samarbete än uppgiftsdelning. Samarbete och konvergens uppnås genom noggrann utformning av enskilda KS så att de kan använda de resultat som erhållits från avlägsna KS:er på ett meningsfullt sätt. Delning av uppgifter, å andra sidan, tydliggör samarbetet genom att upprätta formella kommunikationslinjer och infoga noder vars specifika uppgift är att integrera de partiella tolkningar från noderna som fungerar på de faktiska uppgifterna. Exemplet illustrerar också ett av de stora olösta problemen i distribuerade problemlösning-hur man uppnår sammanhängande beteende med ett system där kontrollen fördelas mellan ett antal autonoma noder. När antalet uppgifter eller resultat som kan behandlas överstiger antalet tillgängliga noder, då noder med uppgifter eller resultat att dela måste konkurrera om gruppens uppmärksamhet och resurser. När det gäller uppgiftsdelning måste mekanismer utformas som ger viss säkerhet om att enskilda underproblem faktiskt behandlas, att processorer inte hamnar i underproblem som inte leder till lösningar. Vi har föreslagit förhandlingar som en mekanism för att hantera dessa svårigheter och har utformat avtalsprotokollet med dem i åtanke [19]. Det är emellertid uppenbart att mycket arbete återstår att göra. In försvann i sändning. I vissa fall, systemets prestanda faktiskt förbättras, en indikation på att noder ibland distraherar sina grannar. Än en gång återstår mycket arbete på detta område. - Vad är det för fel på dig? SLUTSATSER Två kompletterande samarbetsformer för distribuerad problemlösning har diskuterats: uppgiftsdelning och resultatdelning. Dessa formulär är användbara för olika typer av problem och för olika faser av distribuerad problemlösning. Uppgiftsdelning är användbart i problem sönderdelningen och besvara syntesfaserna av distribuerad problemlösning. Den antar att subproblemlösning kan uppnås med minimal kommunikation mellan noder. Resultatdelning är användbart i underproblemlösningsfasen när underproblem i kärnan inte kan lösas av noder som arbetar självständigt utan kommunikation med andra noder. Det är också till viss del till hjälp i den sammanfattande svarsfasen, särskilt när det gäller problem där den sammanfattande svarsfasen i huvudsak är en fortsättning på underproblemlösningsfasen. Vi förväntar oss till slut att se system där båda samarbetsformerna används, med hjälp av sina individuella styrkor för att angripa problem för vilka ingen form är tillräckligt kraftfull av sig själv. Dessa idéer har utvecklats till följd av många diskussioner med våra kolleger. Bidragen från Victor Lesser, Rick Hayes-Roth och Steve Zucker har varit till särskilt stor hjälp. [1] J. L. Baer, "En undersökning av några teoretiska aspekter av multibearbetning", Comput. Undersökningar, vol. 5, s. 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; svensk specialutgåva, område 5; s. 31–80 år, dvs. från och med den 1 januari 2015 till och med den 31 december 2015. Det är 1973. [Detta beslut riktar sig till medlemsstaterna.]
Teoretiskt arbete i DAI avseende samarbetsvilliga experter har varit i två huvudriktningar, nämligen uppgiftsdelning och resultatdelning REF.
Frameworks for Cooperation in Distributed Problem Solving
{'venue': 'IEEE Transactions on Systems, Man, and Cybernetics', 'journal': 'IEEE Transactions on Systems, Man, and Cybernetics', 'mag_field_of_study': ['Computer Science']}