decision_control/slotplanner.cc

   1 /*
   2 This file is part of I am car.
   3
   4 I am car is free software: you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation, either version 3 of the License, or
   7 (at your option) any later version.
   8
   9 I am car is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with I am car. If not, see <http://www.gnu.org/licenses/>.
  16 */
  17
  18 #include <algorithm>
  19 #include <cmath>
  20 #include <list>
  21 #include <queue>
  22 #include "slotplanner.h"
  23
  24 ParallelSlot::ParallelSlot()
  25 {}
  26
  27 // getter
  28 std::vector<std::vector<RRTNode *>> &ParallelSlot::cusp()
  29 {
  30         return this->cusp_;
  31 }
  32
  33 float ParallelSlot::DH() const
  34 {
  35         return this->DH_;
  36 }
  37
  38 PolygonObstacle &ParallelSlot::slot()
  39 {
  40         return this->slot_;
  41 }
  42
  43 float ParallelSlot::slotHeading()
  44 {
  45         float y0 = this->slot().bnodes()[0]->y();
  46         float x0 = this->slot().bnodes()[0]->x();
  47         float y3 = this->slot().bnodes()[3]->y();
  48         float x3 = this->slot().bnodes()[3]->x();
  49         float dy = y0 - y3;
  50         float dx = x0 - x3;
  51         return atan2(dy, dx);
  52 }
  53
  54 SlotSide ParallelSlot::slotSide()
  55 {
  56         if (!this->slotSide_) {
  57                 float y0 = this->slot().bnodes()[0]->y();
  58                 float x0 = this->slot().bnodes()[0]->x();
  59                 float y1 = this->slot().bnodes()[1]->y();
  60                 float x1 = this->slot().bnodes()[1]->x();
  61                 float y3 = this->slot().bnodes()[3]->y();
  62                 float x3 = this->slot().bnodes()[3]->x();
  63                 if (sgn((x1 - x3) * (y0 - y3) - (y1 - y3) * (x0 - x3)) < 0)
  64                         this->slotSide_ = LEFT;
  65                 else
  66                         this->slotSide_ = RIGHT;
  67         }
  68         return this->slotSide_;
  69 }
  70
  71 SlotType ParallelSlot::slotType()
  72 {
  73         if (!this->slotType_) {
  74                 float d1 = EDIST(
  75                         this->slot().bnodes()[0],
  76                         this->slot().bnodes()[1]
  77                 );
  78                 float d2 = EDIST(
  79                         this->slot().bnodes()[1],
  80                         this->slot().bnodes()[2]
  81                 );
  82                 if (d1 > d2)
  83                         this->slotType_ = PERPENDICULAR;
  84                 else
  85                         this->slotType_ = PARALLEL;
  86         }
  87         return this->slotType_;
  88 }
  89
  90 // setter
  91 void ParallelSlot::DH(float dh)
  92 {
  93         this->DH_ = dh;
  94 }
  95
  96 // other
  97 void ParallelSlot::fip()
  98 {
  99         // see https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bfs.html
 100         // RRTNode.s() works as iteration level
 101         std::queue<BicycleCar *, std::list<BicycleCar *>> q;
 102         std::queue<BicycleCar *, std::list<BicycleCar *>> empty;
 103         int di = -1;
 104         // new pose for parallel parking to right slot
 105         float tnx;
 106         float tny;
 107         float nx;
 108         float ny;
 109         // temporary tnx is angle
 110         tnx = this->slotHeading() + M_PI;
 111         if (this->slotSide() == RIGHT)
 112                 tnx -= M_PI / 4;
 113         else
 114                 tnx += M_PI / 4;
 115         nx = this->fposecenter()->x() + 0.01 * cos(tnx);
 116         ny = this->fposecenter()->y() + 0.01 * sin(tnx);
 117         BicycleCar *CC = new BicycleCar(nx, ny, this->slotHeading());
 118         // move left by car width / 2
 119         tnx = CC->x() + CC->width() / 2 * cos(CC->h() + M_PI / 2);
 120         tny = CC->y() + CC->width() / 2 * sin(CC->h() + M_PI / 2);
 121         if (this->slotSide() == LEFT) {
 122                 di = 1;
 123                 // move right by car width / 2
 124                 tnx = CC->x() + CC->width() / 2 * cos(CC->h() - M_PI / 2);
 125                 tny = CC->y() + CC->width() / 2 * sin(CC->h() - M_PI / 2);
 126         }
 127         // move down
 128         nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 129         ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 130         BicycleCar *B = new BicycleCar(nx, ny, CC->h());
 131         this->DH(di * 0.01 / CC->out_radi());
 132         BicycleCar *c;
 133         int i = 0;
 134         c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 135         while (!this->slot().collide(c->frame())) {
 136                 q.push(c);
 137                 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 138                 i += 1;
 139         }
 140         delete c; // not in q and collide
 141         while (!q.empty()) {
 142                 c = q.front();
 143                 q.pop();
 144                 if (this->isInside(c)) {
 145                         goto createcuspandfinish;
 146                 } else if (c->s() < 9) {
 147                         BicycleCar *cc = this->flnc(c);
 148                         cc->s(c->s() + 1);
 149                         cc->bcparent(c);
 150                         q.push(cc);
 151                 } else {
 152                         delete c; // not in q and collide
 153                 }
 154         }
 155         std::swap(q, empty);
 156         return;
 157 createcuspandfinish:
 158         std::vector<RRTNode *> cusp;
 159         while (c) {
 160                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 161                 c = c->bcparent();
 162         }
 163         std::reverse(cusp.begin(), cusp.end());
 164         this->cusp().push_back(cusp);
 165         std::swap(q, empty);
 166 }
 167
 168 void ParallelSlot::fipr(BicycleCar *B)
 169 {
 170         std::vector<RRTNode *> cusp;
 171         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
 172         int di = 1;
 173         if (this->slotSide() == LEFT)
 174                 di = -1;
 175         this->DH(di * 0.01 / B->out_radi());
 176         BicycleCar *c;
 177         c = this->flncr(B);
 178         c->s(B->s() + 1);
 179         while ((
 180                 this->slotSide() == LEFT
 181                 && this->slot().collide(new RRTNode(c->lfx(), c->lfy(), 0))
 182         ) || (
 183                 this->slotSide() == RIGHT
 184                 && this->slot().collide(new RRTNode(c->rfx(), c->rfy(), 0))
 185         )) {
 186                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 187                 BicycleCar *cc = this->flncr(c);
 188                 cc->s(c->s() + 1);
 189                 delete c;
 190                 c = cc;
 191         }
 192         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 193         std::reverse(cusp.begin(), cusp.end());
 194         this->cusp().push_back(cusp);
 195 }
 196
 197 BicycleCar *ParallelSlot::flnc(BicycleCar *B)
 198 {
 199         RRTNode *cc;
 200         if (this->slotSide() == LEFT) {
 201                 if (int(B->s()) % 2 == 0)
 202                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 203                 else
 204                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 205         } else {
 206                 if (int(B->s()) % 2 == 0)
 207                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 208                 else
 209                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 210         }
 211         BicycleCar *p;
 212         int i = 1;
 213         p = B->move(cc, i * this->DH());
 214         while (
 215                 !this->slot().collide(p->frame())
 216                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
 217         ) {
 218                 delete p;
 219                 i += 10;
 220                 p = B->move(cc, i * this->DH());
 221         }
 222         i -= 10;
 223         p = B->move(cc, i * this->DH());
 224         while (
 225                 !this->slot().collide(p->frame())
 226                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
 227         ) {
 228                 if (this->isInside(p)) {
 229                         i += 1;
 230                         break;
 231                 }
 232                 delete p;
 233                 i += 1;
 234                 p = B->move(cc, i * this->DH());
 235         }
 236         delete p;
 237         return B->move(cc, (i - 1) * this->DH());
 238 }
 239
 240 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
 241 {
 242         RRTNode *cc;
 243         if (this->slotSide() == LEFT) {
 244                 if (int(B->s()) % 2 == 0)
 245                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 246                 else
 247                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 248         } else {
 249                 if (int(B->s()) % 2 == 0)
 250                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 251                 else
 252                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 253         }
 254         BicycleCar *p;
 255         int i = 1;
 256         p = B->move(cc, i * this->DH());
 257         while (
 258                 !this->slot().collide(p->frame())
 259                 && ((
 260                         this->slotSide() == LEFT
 261                         && this->slot().collide(new RRTNode(
 262                                 p->lfx(),
 263                                 p->lfy(),
 264                                 0
 265                         ))
 266                 ) || (
 267                         this->slotSide() == RIGHT
 268                         && this->slot().collide(new RRTNode(
 269                                 p->rfx(),
 270                                 p->rfy(),
 271                                 0
 272                         ))
 273                 ))
 274         ) {
 275                 delete p;
 276                 i += 10;
 277                 p = B->move(cc, i * this->DH());
 278         }
 279         i -= 10;
 280         p = B->move(cc, i * this->DH());
 281         while (!this->slot().collide(p->frame())) {
 282                 if(
 283                         this->slotSide() == LEFT
 284                         && !this->slot().collide(new RRTNode(
 285                                 p->lfx(),
 286                                 p->lfy(),
 287                                 0
 288                         ))
 289                 ) {
 290                         i += 1;
 291                         break;
 292                 }
 293                 if(
 294                         this->slotSide() == RIGHT
 295                         && !this->slot().collide(new RRTNode(
 296                                 p->rfx(),
 297                                 p->rfy(),
 298                                 0
 299                         ))
 300                 ) {
 301                         i += 1;
 302                         break;
 303                 }
 304                 i += 1;
 305                 p = B->move(cc, i * this->DH());
 306         }
 307         delete p;
 308         return B->move(cc, (i - 1) * this->DH());
 309 }
 310
 311 RRTNode *ParallelSlot::fposecenter()
 312 {
 313         return this->slot().bnodes().front();
 314 }
 315
 316 bool ParallelSlot::flast(
 317         RRTNode *P,
 318         bool right,
 319         int il,
 320         std::vector<RRTNode *> &cusp
 321 )
 322 {
 323         BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
 324         RRTNode *cc;
 325         if (right)
 326                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 327         else
 328                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 329         BicycleCar *p;
 330         int i = 1;
 331         p = B->move(cc, i * this->DH());
 332         while (!this->slot().collide(p->frame())
 333                         && (
 334                                 (this->DH() > 0 && p->x() <= 0)
 335                                 || (this->DH() < 0 && p->x() >= 0)
 336                         )) {
 337                 delete p;
 338                 i += 10;
 339                 p = B->move(cc, i * this->DH());
 340         }
 341         i -= 10;
 342         p = B->move(cc, i * this->DH());
 343         while (!this->slot().collide(p->frame())
 344                         && (
 345                                 (this->DH() > 0 && p->x() <= 0)
 346                                 || (this->DH() < 0 && p->x() >= 0)
 347                         )) {
 348                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 349                         i += 1;
 350                         break;
 351                 }
 352                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 353                         i += 1;
 354                         break;
 355                 }
 356                 delete p;
 357                 i += 1;
 358                 p = B->move(cc, i * this->DH());
 359         }
 360         delete p;
 361         p = B->move(cc, (i - 1) * this->DH());
 362         if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 363                 cusp.push_back(p);
 364                 return true;
 365         } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 366                 cusp.push_back(p);
 367                 return true;
 368         } else if (il < 8) {
 369                 cusp.push_back(p);
 370                 return this->flast(p, !right, il + 1, cusp);
 371         }
 372         return false;
 373 }
 374
 375 void ParallelSlot::fpose()
 376 {
 377         bool left = false; // right parking slot
 378         float di = -1;
 379         BicycleCar *CC = new BicycleCar(
 380                 this->fposecenter()->x(),
 381                 this->fposecenter()->y() - 0.01,
 382                 this->slotHeading()
 383         );
 384         BicycleCar *B = new BicycleCar(
 385                 CC->x() - CC->width() / 2,
 386                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
 387                 this->slotHeading()
 388         );
 389         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
 390                 left = true;
 391                 di = 1;
 392                 delete B;
 393                 B = new BicycleCar(
 394                         CC->x() + CC->width() / 2,
 395                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
 396                         this->slotHeading()
 397                 );
 398         }
 399         this->DH(di * 0.01 / CC->out_radi());
 400         BicycleCar *p;
 401         int i = 0;
 402         p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 403         while (!this->slot().collide(p->frame())) {
 404                 std::vector<RRTNode *> tmpcusp;
 405                 tmpcusp.push_back(new BicycleCar(p->x(), p->y(), p->h()));
 406                 if (this->flast(p, left, 0, tmpcusp)) {
 407                         this->cusp().push_back(tmpcusp);
 408                         return;
 409                 }
 410                 i += 1;
 411                 delete p;
 412                 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 413         }
 414 }
 415
 416 BicycleCar *ParallelSlot::getFP()
 417 {
 418         float x = this->slot().bnodes()[3]->x();
 419         float y = this->slot().bnodes()[3]->y();
 420         float h = this->slotHeading();
 421         float nx;
 422         float ny;
 423         if (this->slotSide() == LEFT) {
 424                 nx = x + BCAR_WIDTH / 2 * cos(h + M_PI / 2);
 425                 ny = y + BCAR_WIDTH / 2 * sin(h + M_PI / 2);
 426         } else {
 427                 nx = x + BCAR_WIDTH / 2 * cos(h - M_PI / 2);
 428                 ny = y + BCAR_WIDTH / 2 * sin(h - M_PI / 2);
 429         }
 430         x = nx + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * cos(h);
 431         y = ny + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * sin(h);
 432         return new BicycleCar(x, y, h);
 433 }
 434
 435 bool ParallelSlot::isInside(BicycleCar *c)
 436 {
 437         bool inside = true;
 438         RRTNode *tmpn;
 439         tmpn = new RRTNode(c->lfx(), c->lfy(), 0);
 440         if (!this->slot().collide(tmpn))
 441                 inside = false;
 442         delete tmpn;
 443         tmpn = new RRTNode(c->lrx(), c->lry(), 0);
 444         if (!this->slot().collide(tmpn))
 445                 inside = false;
 446         delete tmpn;
 447         tmpn = new RRTNode(c->rrx(), c->rry(), 0);
 448         if (!this->slot().collide(tmpn))
 449                 inside = false;
 450         delete tmpn;
 451         tmpn = new RRTNode(c->rfx(), c->rfy(), 0);
 452         if (!this->slot().collide(tmpn))
 453                 inside = false;
 454         delete tmpn;
 455         return inside;
 456 }
 457
 458 struct SamplingInfo ParallelSlot::getSamplingInfo()
 459 {
 460         struct SamplingInfo si;
 461         BicycleCar *CC = new BicycleCar(
 462                 this->fposecenter()->x(),
 463                 this->fposecenter()->y() - 0.01,
 464                 this->slotHeading()
 465         );
 466         si.x = this->slot().bnodes()[0]->x();
 467         si.y = this->slot().bnodes()[0]->y();
 468         si.r = CC->diag_radi();
 469         si.h = this->slotHeading() - acos(EDIST( // TODO generalize
 470                 this->slot().bnodes()[0],
 471                 this->slot().bnodes()[1]
 472         ) / BCAR_LENGTH);
 473         return si;
 474 }